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

问题描述

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

我最近了解到 A* 算法可以应用于旅行商问题.Bot 我们如何准确定义开始和目标，以及我们如何将权重应用于节点(启发式是什么)?

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一般从任意节点开始.更重要的是，这些算法寻求找到两点之间的最短路径，而不管访问的节点数量如何.事实上，它们取决于这样一个事实，即通过某个节点 A 从 S 到 T 的最短路径，如果成本相同，从 S 到 A 的路径无关紧要.

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.

我看到此功能的唯一方法是生成一个表示访问过的节点的新图.例如，在您的优先级队列中，您将放置一组访问过的节点和当前节点.这将导致可能检查 $n2^n$ 节点(这与 TSP http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE49.HTM).到目前为止，还不是很好，但是通过使用 A* 而不是 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屋！