algorithm - 需要一个具有多个目标的星搜索算法的想法

Question

指定目标的 A 星搜索算法非常简单。但是，如果图中有多个目标怎么办。例如;您可能想要找到必须包含先前指定节点的最短路径。这里的约束是说你的路径必须包括 A、B 和 C 节点(或更多)，而不仅仅是找到到节点 A 或 B 或 C 的路径。当然，该图包括一个或多个 A、B、C 类型的节点。所以有一个问题，我如何适应 A 星搜索算法用于多个目标？

编辑:我们可以访问多个节点。

Answer 1

您描述的是路径条件，而不是目标条件。与所有搜索算法一样，A* 正在寻找通往目标的路径 [可以在一组目标中，没有问题]。

你的问题 [对于一般情况] 至少和 Traveling Salesman Problem 一样难, 因此这个问题是 NP-Hard .

归约很简单:给定一个 TSP 实例 - 找到从某个 v 到 v 的最短路径，使得该路径经过所有顶点 [constraint] .您可以通过简单地用不同的标记标记每个顶点来做到这一点。

但是请注意，A* 算法可以毫无问题地找到到一组目标顶点 中的顶点的最短路径。请记住，A* 基于 Dijkstra's Algorithm ，这是从单一来源寻找到所有顶点的最短路径。