路线长度
找到的最短
步数
可能的路线数
  • 路线
  • 找到的最短
  • 起点

方法 长度 超出最短 步数
- - -
- - -
- - -
- - -
- - -

更多关于旅行商问题

旅行商问题

一位推销员要把每座城市都访问一次,然后回到家中。按什么顺序走,旅程最短?这个问题很容易提出,但随着城市数量增加,靠尝试所有顺序来回答就毫无希望:30 个城市就已有约 4.4 × 10³⁰ 条环游路线。在地图上撒下城市或自己点击放置,然后观看快速的经验法则、巧妙的改进方法和一种精确方法一步步构建路线,看看快速方法能有多接近最优。 选择城市的布局和数量,再选一种方法,按“求解”即可看它一步步构建一条环游路线,或按“单步”每次只走一步。点击地图可添加城市,点击某个城市可将其删除。“全部比较”会在同一组城市上运行每种方法,并显示每条路线与找到的最短路线相差多少。红色城市是旅程的起点。

它是如何运作的

  1. 选择一种布局和城市数量,或点击地图自己放置城市,点击某个城市可将其删除。
  2. 选择一种方法,按“求解”一步步观看,或按“单步”每次只走一步。
  3. 按“全部比较”在同一组城市上运行每种方法,并查看每条路线比找到的最短路线长多少。

为什么难

有 n 个城市时,共有 (n − 1)! / 2 条不同的环游路线,因为从哪里出发、朝哪个方向走都无关紧要。5 个城市有 12 条,10 个城市有 181,440 条,20 个城市约有 6 × 10¹⁶ 条。目前还不知道有哪种方法能对每张地图都在只按 n 的幂增长的时间内找到最短路线;这个问题是 NP 困难的。本应用中最好的精确方法——1962 年提出的 Held–Karp 动态规划——仍需要约 n² · 2ⁿ 步,因此这里最多只能用于 12 个城市。

快速找到好路线

在实践中,接近最短的路线可以很快找到。最近邻法总是开往最近的未访问城市,结果通常比最优路线长约 25%。最小代价插入法让一个回路逐渐增长,每次加入使回路拉长最少的城市。2-opt 从任意路线出发,不断把两条边换成两条更短的边,从而消除所有交叉,通常能把差距缩小到约 5% 以内。模拟退火做随机的 2-opt 移动,并在仍然“热”的时候接受一些使路线变长的移动,因此能在稳定下来之前爬出死胡同。

常见问题

最短路线有公式吗?

没有。最短路线取决于所有城市的确切位置,而已知的方法都无法在最坏情况下不付出指数级增长的工作量就对每张地图找到它。对于几百或几千个城市,Concorde 等专门的精确求解器仍能结合线性规划与巧妙的剪枝来证明最优路线,迄今精确求解的最大实例有 85,900 个点。

为什么 2-opt 能消除所有交叉?

如果路线中的两条边相交,它们连接的四个城市构成一个四边形,这两条边就是它的对角线。根据三角不等式,把它们换成四边形的一组对边总会更短,同时中间那段路线的方向会反转。2-opt 不断进行这样的交换,直到再也没有改进,所以它最终的路线绝不会自相交。

模拟退火中的温度是什么?

它控制该方法有多愿意接受使路线变长的移动。一次使长度增加 d 的移动以概率 e^(−d/T) 被接受。温度 T 高时几乎什么都会被接受,这让路线能摆脱糟糕的排列;随着 T 降低,方法变得贪心并逐渐稳定。这个名字来自让金属缓慢冷却、使其原子找到低能量排列的做法。

为什么精确方法限于 12 个城市?

Held–Karp 为每个城市子集和每个可能的最后城市存储最短路径,大约是 n · 2ⁿ 个数,每个数要通过 n 次比较来填入。12 个城市时这是几十万步;25 个城市时将达到数十亿步。但这仍比尝试全部 (n − 1)! / 2 条路线快得多:12 个城市时那将近 2000 万条。

会向服务器发送任何内容吗?

不会。城市和全部五种方法都在你的浏览器中运行。你点击放置的城市保存在此浏览器的本地存储中。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

前往编辑器