如何能在A *算法应用于旅行商问题？ [英] How can the A* algorithm be applied to the traveling salesman problem?

问题描述

可能重复：
  使用A *解决旅行商问题

我最近了解到，在 A * 算法可以应用到旅行商问题。博特我们究竟如何定义的开始和这里的目标，以及我们如何运用权重节点（什么是启发式）？

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)?

会有人向我解释如何A *可以在这里应用？

Would someone explain to me how A* can be applied here?

推荐答案

A *是Dijsktra的衍生物，我不认为可以以这种方式使用。首先，对TSP通常开始从任何节点。更重要的是，这些算法寻求找到两个点之间的最短路径，而不管节点的数量的访问的。事实上，它们依赖于一个事实，即从S的最短路径，通过一些节点A到T，从S到一个路径是不相关的，如果是相同的成本。

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.

我看到这个功能的唯一方法是，如果你重新产生访问presenting节点的新图。例如，在你的优先队列，你将集访问过的节点和当前节点。这将导致可能检查$ N2 ^ n $的节点（这是不是coindientally动态规划解决方案的TSP <一的运行时间href="http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE49.HTM">http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE49.HTM).到目前为止，不是很大，但是通过使用*代替Dijsktra，你也许可以找到一个运行在合理的时间量启发式。

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.

要实现这一点，您的出发点是（1，{}）和你的结束点是（1，{1..N}）。您会模仿原图形的边缘的权重。至于启发式的建议，你对你自己的。

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 *算法应用于旅行商问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！