我有一个无向图，其中有大约 100 个节点和大约 200 条边。一个节点标记为“开始”，一个节点标记为“结束”，还有大约十几个标记为“必须通过”。我需要找到通过的最短路径...
我有一个无向图，其中有大约 100 个节点和大约 200 条边。一个节点标记为“开始”，一个节点标记为“结束”，还有大约十几个标记为“必须通过”。
我需要找到该图中最短的路径，该路径始于“开始”，终于“结束”， 并经过所有“必须通过”节点（以任何顺序）。
（ http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt 是所讨论的图表 - 它代表了宾夕法尼亚州兰开斯特的一个玉米迷宫）
实际上，您发布的问题类似于旅行商问题，但我认为更接近于简单的寻路问题。您不需要访问每个节点，而只需在尽可能短的时间（距离）内访问一组特定的节点即可。
原因在于，与旅行商问题不同，玉米迷宫不允许您直接从地图上的任何一个点前往任何其他点，而无需经过其他节点才能到达那里。
我实际上建议考虑使用 A* 寻路技术。通过确定哪些节点可以直接访问哪些其他节点，以及从特定节点每次跳跃的“成本”是多少，可以设置该技术。在这种情况下，由于节点之间的距离相对较近，因此每次“跳跃”的成本似乎相等。A* 可以使用此信息来查找任意两点之间成本最低的路径。由于您需要从 A 点到达 B 点，并在其间访问大约 12 个节点，因此即使使用寻路的蛮力方法也不会有任何损失。
只是一种可供选择的方案。它确实看起来 非常 像旅行商问题，而且这些都是值得一读的好论文，但仔细看看，你会发现它只会让事情变得过于复杂。^_^ 这来自一位曾经处理过这类事情的视频游戏程序员的想法。
