|||
最近看了一些如何高效率求解旅行商问题的文章,颇有感慨!有些作者虽然明白旅行商问题是什么,但没有弄清楚计算旅行商问题时国际公约性的要求,其中最为典型的是笼统认为旅行商问题中两点之间的距离计算都是二维欧氏空间的两点之间距离的计算方法,这是个简单而本质性的错误。下面是Concorde求解器给出的对称旅行商问题边权重类型的定义列表:
#define CC_MAXNORM (0 | CC_KD_NORM_TYPE | CC_D2_NORM_SIZE)
#define CC_EUCLIDEAN_CEIL (1 | CC_KD_NORM_TYPE | CC_D2_NORM_SIZE)
#define CC_EUCLIDEAN (2 | CC_KD_NORM_TYPE | CC_D2_NORM_SIZE)
#define CC_EUCLIDEAN_3D (3 | CC_X_NORM_TYPE | CC_D3_NORM_SIZE)
#define CC_USER (4 | CC_JUNK_NORM_TYPE | 0)
#define CC_ATT (5 | CC_KD_NORM_TYPE | CC_D2_NORM_SIZE)
#define CC_GEOGRAPHIC (6 | CC_KD_NORM_TYPE | CC_D2_NORM_SIZE)
#define CC_MATRIXNORM (7 | CC_JUNK_NORM_TYPE | CC_MATRIX_NORM_SIZE)
#define CC_DSJRANDNORM (8 | CC_JUNK_NORM_TYPE | 0)
#define CC_CRYSTAL (9 | CC_X_NORM_TYPE | CC_D3_NORM_SIZE)
#define CC_SPARSE (10 | CC_JUNK_NORM_TYPE | 0)
#define CC_RHMAP1 (11 | CC_JUNK_NORM_TYPE | 0)
#define CC_RHMAP2 (12 | CC_JUNK_NORM_TYPE | 0)
#define CC_RHMAP3 (13 | CC_JUNK_NORM_TYPE | 0)
#define CC_RHMAP4 (14 | CC_JUNK_NORM_TYPE | 0)
#define CC_RHMAP5 (15 | CC_JUNK_NORM_TYPE | 0)
#define CC_EUCTOROIDAL (16 | CC_JUNK_NORM_TYPE | CC_D2_NORM_SIZE)
#define CC_GEOM (17 | CC_KD_NORM_TYPE | CC_D2_NORM_SIZE)
#define CC_MANNORM (18 | CC_KD_NORM_TYPE | CC_D2_NORM_SIZE)
#define CC_SUBDIVISION (99 | CC_JUNK_NORM_TYPE | 0)
从该列表中可以看出,二维欧氏空间权重类型仅是其中的一种。与此同时,对称旅行商问题中,为了统一起见,两点之间的距离通常要求采用取整计算,这一点更是很多作者忽略的问题。下面仍然是Concorde中的部分计算两点之间记录函数的原型定义:
int max_edgelen (int i, int j);
int man_edgelen (int i, int j);
int euclid_edgelen (int i, int j);
int euclid_ceiling_edgelen (int i, int j);
int euclid3d_edgelen (int i, int j);
int geographic_edgelen (int i, int j);
int geom_edgelen (int i, int j);
int att_edgelen (int i, int j);
int dsjrand_edgelen (int i, int j);
int crystal_edgelen (int i, int j);
int matrix_edgelen (int i, int j);
int sparse_edgelen (int i, int j);
int user_edgelen (int i, int j);
int rhmap1_edgelen (int i, int j);
int rhmap2_edgelen (int i, int j);
int rhmap3_edgelen (int i, int j);
int rhmap4_edgelen (int i, int j);
int rhmap5_edgelen (int i, int j);
int toroidal_edgelen (int i, int j);
如果计算出来的环路长度带有小数点后几位的作者应该说没有完全领会问题,偏离了国际惯用的对称旅行商问题的定义本质。实际上在研究中通常会发现,这种取整的做法使问题更为简单化,但求解计算更为复杂化,这也正是该问题的“迷人之处”。在之前曾经看到某作者以浮点方式计算两点之间的距离,结果比世界公认的最短环路还要短,声称自己的方法有效,殊不知自己犯了一个怎样的错误?
本文意在提醒做对称旅行商问题研究的初学者,特别注意上述问题。同时,也抛砖引玉,希望各个领域资深的学者也能把本领域研究中,初学者易犯的错误指出来,使得初学者能更快地认识和领会问题,避免走不必要的弯路。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-27 08:54
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社