最近，我尝试了几种不同的邻居选择算法来使用Traveling Salesman Problem来解决Simulated Annealing：
交换两个随机城市（例如abcdefg -> abfdecg）
将路线分成两条，并交换两条次级路线（例如ab|cdefg -> cdefgab）
交换两个随机相邻城市（例如abcdefg -> abdcefg）
交换两条随机子路由（例如a|bc|d|ef|g -> aefdbcg）
反转随机子路线（例如ab|cdef|g -> abfedcg）
结果发现在渐近性能上有很大的不同#结果5个是最好的，2个根本不起作用。
为什么和2和5有这么大的区别？两种算法一次改变两条边在上面的示例中，#2个更改打断bc并附加ga#5用bc替换bf，用fg替换cg。为什么“2”根本不起作用，而“5”是“5”中最好的？
最佳答案
也许我不理解你的问题，但据我所知，旅行商要求所有城市都是闭环访问的，所以你从哪个城市开始并不改变总距离。你的策略2似乎是一个循环排列，即相同的循环但不同的起点，所以难怪它没有任何改进！
Strategy 5运行良好，因为它可能会移除两个交叉边：
a--b f--e a--b--f--e
| X | --> | |
\--g c--d \--g--c--d
注意5只修改2条边。你的策略#4同时修改了4条边，因此这改善路线的可能性可能非常低此外，策略1是4的特例，策略3是5的特例。