algorithm - 不限制访问次数的旅行商问题

Question

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

标签： algorithmoptimizationtraveling-salesman

Answer 1

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