我有一个无向图，其中有大约 100 个节点和大约 200 条边。一个节点标记为“开始”，一个节点标记为“结束”，还有大约十几个标记为“必须通过”。我需要找到通过的最短路径...
我有一个无向图，其中有大约 100 个节点和大约 200 条边。一个节点标记为“开始”，一个节点标记为“结束”，还有大约十几个标记为“必须通过”。
我需要找到该图中最短的路径，该路径始于“开始”，终于“结束”， 并经过所有“必须通过”节点（以任何顺序）。
（ http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt 是所讨论的图表 - 它代表了宾夕法尼亚州兰开斯特的一个玉米迷宫）
如何对十几个“必须访问”的节点使用强力攻击。您可以轻松覆盖 12 个节点的所有可能组合，这样您就可以遵循最佳电路来覆盖它们。
现在，您的问题就简化为找到从起始节点到电路的最佳路线，然后您沿着该路线走，直到覆盖它们，然后找到从那里到终点的路线。
最终路径由以下部分组成：
开始 -> 电路路径* -> 必须访问节点的电路 -> 结束路径* -> 结束
你可以找到我用 * 标记的路径，如下所示
从起始节点到电路上的每个点进行 A* 搜索，对每个点从电路上的下一个和前一个节点到结束进行 A* 搜索（因为您可以按照任一方向进行电路循环）您最终会得到很多搜索路径，您可以选择成本最低的路径。
通过缓存搜索有很多优化的空间，但我认为这会产生好的解决方案。
但它并没有去寻找最佳解决方案，因为这可能涉及在搜索中离开必须访问的电路。
