一个特定的旅行推销员变化的实现 [英] Implementation of a particular Travelling-Salesman variation

问题描述

我在寻找一种算法（C / C ++ / Java的 - 并不重要），这将解决一个问题，其中包括寻找图中的2个节点（A和B）之间的最短路径。美中不足的是，该路径必须访问某些其它特​​定节点（市）。 一个城市可以访问超过一次。的例子path(A-H-D-C-E-F-G-F-B) （其中A是源，B为目标，F，G是城市必须被访问）。

I'm looking for an algorithm(C/C++/Java - doesn't matter) which will resolve a problem which consists of finding the shortest path between 2 nodes (A and B) of a graph. The catch is that the path must visit certain other given nodes(cities). A city can be visited more than once. Example of path(A-H-D-C-E-F-G-F-B) (where A is source, B is destination, F and G are cities which must be visited).

我认为这是旅行商问题的变化，但我无法找到或编写基于我的搜索工作的算法。

I see this as a variation of the Traveling Salesman Problem but I couldn't find or write a working algorithm based on my searches.

我试图找到一个解决方案，从这些话题，但没有任何运气开始： TSP分公司和C语言限制的实施和 <一href="http://stackoverflow.com/questions/1458048/variation-of-tsp-which-visits-multiple-cities">Variation TSP其中访问多个城市

I was trying to find a solution starting from these topics but without any luck: TSP Branch and Bound implementation in C and Variation of TSP which visits multiple cities

推荐答案

这是很容易降低的问题，以TSP将是：

An easy reduction of the problem to TSP would be:

1. 对于每个（U，V）说：一定要参观，发现的距离 D（U，V）之间。这可以通过使用弗洛伊德算法找到所有需要做有效 - 所有最短路径。
2. 创建一个新的图G'仅由这些节点，与现有的所有边缘，以作为计算（1）。
的距离
3. 运行标准TSP算法来解决这一问题上的减少曲线。

1. For each (u,v) that "must be visited", find the distance d(u,v) between them. This can be done efficiently using Floyd-Warshall Algorithm to find all-to-all shortest path.
2. Create a new graph G' consisting only of those nodes, with all edges existing, with the distances as calculated on (1).
3. Run standard TSP algorithm to solve the problem on the reduced graph.

这篇关于一个特定的旅行推销员变化的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！