如何不纯 A* 算法以支持迷宫中的多重搜索
How to impure A* algorithm to support multi-searching in a maze
如果我有一个支持在迷宫中寻找从起点到目标的最佳路径的 A* 函数，我应该如何修改启发式函数以使其可接受，以便在有多个目标时该函数仍然 return最优结果。
假设问题是只访问一个目标：
想到的第一个解决方案是遍历所有可能的目标，为每个目标计算可接受的启发值，然后最后 return 这些值的最小值作为最终的启发值。这样你就可以确定启发式仍然是可接受的（不会高估到任何目标的距离）。
编辑：现在假设问题是访问所有目标：
在这种情况下，A* 甚至不一定是最好的算法。您可以将 A* 与上述启发式方法一起使用，以首先找到到最近目标的最短路径。然后，在到达第一个（最近的）目标后，您可以 运行 以相同的方式再次找到下一个最近的目标，依此类推
但这可能无法给出最佳的整体解决方案。首先访问第二个最近的目标可能是有益的（例如），因为在某些情况下，这可能会启用到第二个目标的更便宜的后续路径。
如果您想要一个最佳的整体解决方案，您可能会想看看不同的整体方法。你的问题会类似Travelling Salesman Problem (though not exactly the same, since I think you're allowed to visit the same point multiple times for example). This link或许也能帮到你
如果我有一个支持在迷宫中寻找从起点到目标的最佳路径的 A* 函数，我应该如何修改启发式函数以使其可接受，以便在有多个目标时该函数仍然 return最优结果。
假设问题是只访问一个目标：
想到的第一个解决方案是遍历所有可能的目标，为每个目标计算可接受的启发值，然后最后 return 这些值的最小值作为最终的启发值。这样你就可以确定启发式仍然是可接受的（不会高估到任何目标的距离）。
编辑：现在假设问题是访问所有目标：
在这种情况下，A* 甚至不一定是最好的算法。您可以将 A* 与上述启发式方法一起使用，以首先找到到最近目标的最短路径。然后，在到达第一个（最近的）目标后，您可以 运行 以相同的方式再次找到下一个最近的目标，依此类推
但这可能无法给出最佳的整体解决方案。首先访问第二个最近的目标可能是有益的（例如），因为在某些情况下，这可能会启用到第二个目标的更便宜的后续路径。
如果您想要一个最佳的整体解决方案，您可能会想看看不同的整体方法。你的问题会类似Travelling Salesman Problem (though not exactly the same, since I think you're allowed to visit the same point multiple times for example). This link或许也能帮到你