旅行商问题，不受访问次数的限制 [英] Traveling Salesman problem without restriction on the number of visits

问题描述

我遇到了类似于旅行推销员(TSP)的问题.我找到了一些图书馆来解决旅行推销员的问题.但是，我想取消每个城市只能访问一次的限制.如何找到至少一次访问每个城市 的最短路径?

I have a problem similar to Traveling Salesman (TSP). I found some libraries to solve the Traveling Salesman problem. However, I would like to remove the restriction of visiting each city only once. How do I find the shortest path that visits each city at least once?

推荐答案

一种简单的方法是通过预处理.将每个 c(i，j)替换为i和j之间最短路径的长度/成本.现在应用标准茶匙.报告时，请在解决方案中插入这些最短路径.这可能会导致多次访问城市.

One simple way is through preprocessing. Replace each c(i,j) by the length/cost of the shortest path between i and j. Now apply standard tsp. When reporting, insert these shortest paths in the solution. This may result in cities being visited multiple times.

这篇关于旅行商问题，不受访问次数的限制的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！