|

楼主 |
发表于 2020-3-20 15:37
|
显示全部楼层
发现了一种构造数据的办法,以后但凡要检测一种TSP算法的性能便可轻易测试了,而不再需要大费周章,找一些公认的历史数据了。
这个构造办法就是:点子图。
点子图有个特点:每一小格都是正方形,边长为1,对角线长约1.41。
构造公式如下:
=RANDBETWEEN(1,30000)
=INT((ROW()-0.1)/50)+1
=MOD(ROW()-1,50)+1
公式1中的随机大数序列(降低重复性)是为了乱序数据而设计.
且先来看一组:
(1)3*3
以上是乱序效果.
以上是优化效果,从图中可以看出,最优结果应该是:8+1.41=9.41,只有一条斜线,像这样的小规模数据我的附件可以做到.
(2)4*4
一乱一序,最优解是:16.
(3)5*5
最优解是25.41
(4)19*19
最优解应该是:361.41,我没再花时间跑,只得到:363.9,花了近200秒.
(5)20*20
这个又是"偶数点*偶数点",最优解应该是:400,我初步得到了:404.14,花了110秒左右.
这两组数据规模可以用来测试多数TSP算法性能.
(6)50*50
这一组的最优解是:2500
我把参数调为400*400,一次优化时长:1014秒,得到:2564.62的结果.按理说,上图中应该没有斜线的,这种最短路径,人脑也是可以轻松规划出来的,但计算机显然更费劲.我所想到的方法是:反复"凹"字路线,最后像一把梳子.
这些数据的最优解是确定的,可以验证算法性能.
|
|