我有一个无向图，其中有大约 100 个节点和大约 200 条边。一个节点标记为“开始”，一个节点标记为“结束”，还有大约十几个标记为“必须通过”。我需要找到通过的最短路径...
我有一个无向图，其中有大约 100 个节点和大约 200 条边。一个节点标记为“开始”，一个节点标记为“结束”，还有大约十几个标记为“必须通过”。
我需要找到该图中最短的路径，该路径始于“开始”，终于“结束”， 并经过所有“必须通过”节点（以任何顺序）。
（ http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt 是所讨论的图表 - 它代表了宾夕法尼亚州兰开斯特的一个玉米迷宫）
Andrew Top 有正确的想法：
1) Djikstra 算法2) 一些 TSP 启发式算法。
我推荐 Lin-Kernighan 启发式方法：它是解决 NP 完全问题最著名的方法之一。唯一需要记住的是，在第 2 步之后再次展开图形后，展开的路径中可能会出现循环，因此您应该绕过这些循环（查看路径上顶点的度数）。
我实际上不确定这个解决方案相对于最优方案有多好。可能有一些与短路有关的病态情况。毕竟，这个问题看起来很像 Steiner Tree： http://en.wikipedia.org/wiki/Steiner_tree ，你绝对不能仅通过收缩你的图并运行 Kruskal 来近似 Steiner Tree。
