A*算法如何应用于旅行商问题？
可能的重复：
使用 A* 解决旅行商问题
我最近了解到A*算法可以应用于旅行商问题。 Bot 我们到底如何定义这里的开始和目标，以及我们如何将权重应用于节点（什么是启发式）？
有人可以向我解释一下如何在这里应用 A* 吗？
Possible Duplicate:
Using A* to solve Travelling Salesman Problem
I have recently learned that the A* algorithm can be applied to the travelling salesman problem. Bot how exactly do we define the start and the goal here, and how do we apply weights to nodes (what is the heuristic)?
Would someone explain to me how A* can be applied here?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
A* 是 Dijsktra 的衍生物，我认为它不能以这种方式使用。首先，TSP一般从任意节点开始。但更重要的是，这些算法寻求找到两点之间的最短路径，而不管访问的节点数量如何。事实上，它们取决于这样一个事实：从 S 到 T 通过某个节点 A 的最短路径，如果成本相同，从 S 到 A 的路径是无关的。
我看到此功能的唯一方法是生成一个表示访问的节点的新图表。例如，在优先级队列中，您将放置访问的节点集和当前节点。这可能会导致检查 $n2^n$ 节点（这与 TSP 的动态规划解决方案的运行时间不同http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE49.HTM）。到目前为止，还不是很好，但是通过使用 A* 而不是 Dijsktra，您也许能够找到在合理时间内运行的启发式方法。
要实现此目的，起始节点为 (1,{})，结束节点为 (1,{1..n})。您将模仿原始图的边权重。至于启发式的建议，你就靠你自己了。
A* is a derivative of Dijsktra, which I don't think can be used in this fashion. First, the TSP generally starts from any node. More importantly though, these algorithms seek to find the shortest path between two points, irrespective of the number of nodes visited. In fact, they depend on the fact that the shortest path from S to T via some node A, the path from S to A is irrelevant if it's the same cost.
The only way I see this functioning is if you generated a new graph representing nodes visited. For example, in your priority queue, you'd place the set of nodes visited and current node. This would lead to possibly examining $n2^n$ nodes (which is not coindientally the running time of the dynamic programming solution to the TSP http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE49.HTM). So far, not great, but by using A* instead of Dijsktra, you might be able to find a heuristic that runs in a reasonable amount of time.
To implement this, your starting node would be (1,{}) and your ending node would be (1,{1..n}). You would mimic the edge weights of the original graph. As for suggestions on the heuristic, you're on your own..
A* 可以在这里应用，尽管它可能不是最好的算法。
您必须远离城市及其之间的道路的图表。相反，定义一个有向图，其中部分路由是节点，并且两个节点 x 和 y 连接起来，当且仅当 y 可以从 构造时x 通过在原始城市图中添加一个“步骤”来实现。起始节点是一个空路径。目标节点是访问所有城市的路径。 （这条路径的最优性由启发式和 A* 算法本身的属性保证。）
[编辑：起初我认为路径应该是城市的有序列表，但我现在相信@ spin_plate 建议用一对（长度、城市集）来表示路径就足够了。]
路径成本是行驶的总距离。启发式必须是对总最小行程长度的某种可接受估计（通常是低估）。
这种估计的一个很好的候选者可能是 TSP 的快速近似（松弛问题的解决方案）。您将在尚未覆盖的城市集上为每个节点（部分路线）运行近似算法。这为算法提供了推销员仍需走的距离的必要上限。
A* can be applied here, though it might not be the best algorithm.
You'll have to step away from the graph of cities and roads between them. Instead, define a directed graph where partial routes are the nodes and two nodes x and y are connected iff y can be constructed from x by adding a single "step" in the original cities graph. The start node is an empty path. The goal node is a path through that visits all cities. (Optimality of this path is guaranteed by the properties of the heuristic and the A* algorithm itself.)
[EDIT: At first I thought a path should be an ordered list of cities, but I now believe @spinning_plate's suggestion of representing the path by a pair (length, set of cities) is enough.]
The path cost is the total distance travelled. The heuristic would have to be some admissible estimate (usually, an underestimate) of the total minimal travel length.
A good candidate for such an estimate might be a fast approximation of the TSP (the solution of a relaxed problem). You'd run the approximation algorithm for each node (partial route), on the set of cities not yet covered. That gives the algorithm the necessary upper bound on the distance the salesman still has to go.
是的，理论上可以将 TSP 问题转换为更大的图并对其使用A* 搜索。但遗憾的是它没有用，因为它无法扩展（请参阅 spin_plate 的评论）。在现代硬件上，即使是小实例也可能需要数年时间才能解决。
TSP 是NP 完整，而寻路则不然。
使用元启发式算法（禁忌搜索、遗传算法、模拟退火等）。有关软件示例，请参阅 Drools Planner、openTS、jgap、cpsolver...
Yes, in theory it's possible to transform the TSP problem into a much bigger graph and use A* search on it. But regrettably it's useless because it won't scale (see spinning_plate's comment). Even small instances might take years to solve that way on modern hardware.
TSP is NP-complete, pathfinding isn't.
Use algorithms such as metaheuristics (tabu search, genetic algorithms, simulated annealing, ...). For software examples, see Drools Planner, openTS, jgap, cpsolver, ...
A* 是 Dijkstra 算法的扩展，其中考虑了遍历有向图的最优解。我不确定这是否适用于 TSP 问题。
TSP 问题指出，您希望在仅访问每个目的地一次的情况下最大程度地减少旅行距离。 A* 算法需要一种启发式方法来引导已知最佳解决方案是一条直线（您必须小心使用 A* 启发式，不要高估到目标的距离）。这不适用于 TSP 问题。
此问题还包含有关 A* 算法和 TSP 问题的信息。
A* is an extension of Dijkstra's algorithm where the optimal solution of traversing a directional graph is taken into account. I'm not sure this applies to the TSP problem.
The TSP problem states that you want to minimize the traveling distance while visiting each destination exactly once. The A* algorithm needs a heuristic to guide it's way where the optimal solution is known to be a straight line (you have to be careful with the A* heuristic to not overestimate the distance to the goal). This dose not apply to the TSP problem.
This question also contains information about the A* algorithm and TSP problem.