需要一个想法，与多个目标的星级搜索算法 [英] Need an idea for A star search algorithm with multiple goals

问题描述

的搜星与指定目标的算法是pretty的简单。然而，如果在一个图多重目标。例如;你可能希望找到一条最短路径必须包括previously指定的节点。约束在这里是说，你的路径必须包含A，B和C节点（或以上）不只是找到一个节点A或B套餐或C.和图形包括一个或多​​个A，B，C类型的节点的路径。因此，有一个问题，我怎么能修改作为一个明星搜索算法的多重目标

The algorithm of A star search with a specified goal is pretty straightforward. However, what if there are multiple goals in a graph. For instance; you may want to find a shortest path that must include previously specified nodes. Constraint here is say your path must include A, B and C nodes( or more) not just find a path to node A or B or C. And of course the graph includes one or more A, B, C type nodes. So there is a question how can I adapt the A star search algorithm for multiple goals?

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

edit : we can visit nodes more than one.

推荐答案

您所描述的目标路径上的条件，而不是条件。 A *，像所有的搜索算法 - 是找到一条通向目标[可以在一组，目标，没有问题的。

You are describing conditions on path and not conditions on goal. A*, like all search algorithms - is finding a path to a goal [could be in a set, of goal, no problems with that].

您[对于一般情况]问题是至少硬如旅行商问题 ，因此，这个问题是 NP难。

Your problem [for the general case] is at least as hard as the Traveling Salesman Problem, and thus this problem is NP-Hard.

的减少很简单：给定TSP的instacne - 发现从某个 v 到 v 的最短路径这样的路径正在经历所有顶点[约束]。你可以通过简单地标记每个顶点用不同的标记做到这一点。

The reduction is simple: Given an instacne of TSP - find the shortest path from a certain v to v such that the path is going through all vertices [constraint]. You can do it by simply marking each vertex with a different mark.

请注意但是， A * 算法没有问题，找到最短路径顶点在设置目标顶点的。请记住，A *是基于 Dijkstra算法，这是寻找最短路径为所有的顶点从单一来源。

Note however, that A* algorithm has no problem to find shortest path to a vertex in a set of goal vertices. Remember that A* is based on Dijkstra's Algorithm, which is finding shortest path to all vertices from a single source.

这篇关于需要一个想法，与多个目标的星级搜索算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！