实施特定的旅行 - 销售员变化 [英] Implementation of a particular Travelling-Salesman variation

问题描述

我正在寻找一个算法（C / C ++ / Java - 无所谓），这将解决一个问题，其中包括找到一个图的2个节点（A和B）之间的最短路径。抓住的是，路径必须访问某些其他给定的节点（城市）。 一个城市可以多次访问。路径示例（ A -HDCE- 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 和
中的绑定实现访问的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）。这可以使用 Floyd-Warshall算法有效地完成，以找到全部 - 所有最短路径。


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屋！