现在的位置: 首页 > 综合 > 正文

POJ 3311状压dp+floyd–TSP问题(货郎担问题||旅行商问题)

2014年09月05日 ⁄ 综合 ⁄ 共 272字 ⁄ 字号 评论关闭

对于经典的TSP问题,不想再多说什么了,大致意思就是一个人从某城市出发经过n个城市且只经过一次最后回到出发点走过的最短路程。
这个题目大意就是这样,和经典TSP问题差不多。 大白书上有很详细解释。page63

设f(i,s)表示当前在城市i,访问s中的城市各一次回到起始城市的最短距离,方程为:
f(i,s)=min(f(j,s-{j}+distance(i,j)|j属于s};

边界条件是他经过某个城市时直接到达那个城市,就是从起点直接到那个城市。可以在O(n^2*2^n)内实现。 

本题的话,可以floyd预处理出距离,然后根据上面讲的状压dp即可。

抱歉!评论已关闭.