旅行商问题求解器 — 求经过每座城市的最短路线
本旅行商问题求解器在给定城市间距离矩阵的情况下，使用Held-Karp位掩码动态规划算法，求出经过每座城市恰好一次并返回起点城市的精确最小成本路线——由于该问题一般是NP困难的，因此这种精确方法被有意限制在最多12座城市以内。
快速解答
输入城市间的距离矩阵，即可通过Held-Karp动态规划立即求出精确的最短往返路线。
每座城市一行，用逗号分隔距离，例如0,10,15,20，然后10,0,35,25。最多12座城市。
如何使用 旅行商问题求解器 — 在线精确Held-Karp动态规划
- 1
输入距离矩阵，每座城市一行，用逗号分隔距离，例如0,10,15,20，然后10,0,35,25，依此类推。
- 2
矩阵应为方阵，每个元素给出两座城市之间的距离（对角线元素通常为0）。
- 3
点击'计算'以通过Held-Karp动态规划求出精确的最优路线。
为什么使用 旅行商问题求解器 — 在线精确Held-Karp动态规划？
旅行商问题询问经过每座城市恰好一次并返回起点的最短可能路线——这是一个经典的NP困难问题，穷举检查所有(n−1)!/2条可能路线在城市数量稍多时就变得不可行。Held-Karp算法通过对子集使用动态规划极大改进了穷举法：它为每一个已访问城市子集及每个可能的结束城市追踪到达该状态的最便宜方式，从小子集逐步构建到完整集合，时间复杂度为O(n² · 2ⁿ)而非O(n!)。这仍是指数级的，因此此计算器将问题限制在12座城市以内，在此规模下Held-Karp仍能保持舒适的速度，同时找到精确的、可证明最优的路线（而不仅仅是一个好的近似值）。