之前写过一道类似的题目，Uva 1347.
这个题目和TSP问题已经很接近了，只是描述的奇奇怪怪的，从最左边走到最右边。其实和TSP问题，没有区别了。
介绍一下常规的TSP解法：
首先规定一个起点和终点0， d(i,S)表示当前在 i ,还需访问集合 S 中的城市各一次后回到 0 的最短长度。
d(i,S) = min{d(j,S-{j}+dist(i,j))} | j 属于 S;
边界条件 d(i,{}) = dist(0,i); 答案存在 d(0,(1<<n)-1);
本文共 291 字，大约阅读时间需要 1 分钟。
之前写过一道类似的题目，Uva 1347.
这个题目和TSP问题已经很接近了，只是描述的奇奇怪怪的，从最左边走到最右边。其实和TSP问题，没有区别了。
介绍一下常规的TSP解法：
首先规定一个起点和终点0， d(i,S)表示当前在 i ,还需访问集合 S 中的城市各一次后回到 0 的最短长度。
d(i,S) = min{d(j,S-{j}+dist(i,j))} | j 属于 S;
边界条件 d(i,{}) = dist(0,i); 答案存在 d(0,(1<<n)-1);
转载于:https://www.cnblogs.com/TreeDream/p/6011944.html