实施特定的旅行 - 销售员变化 [英] 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:
- 对于每个
(u,v)
,必须访问,找到d(u,v)
。这可以使用 Floyd-Warshall算法有效地完成,以找到全部 - 所有最短路径。 - 创建一个新图G'仅由那些节点组成,所有边都存在,距离按照(1)计算。
- 运行标准TSP算法以解决简化图表上的问题。
- For each
(u,v)
that "must be visited", find the distanced(u,v)
between them. This can be done efficiently using Floyd-Warshall Algorithm to find all-to-all shortest path. - Create a new graph G' consisting only of those nodes, with all edges existing, with the distances as calculated on (1).
- Run standard TSP algorithm to solve the problem on the reduced graph.
这篇关于实施特定的旅行 - 销售员变化的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!