本文共 727 字,大约阅读时间需要 2 分钟。
我很清楚DP解决旅行商问题;也被称为TSP的Held和Karp算法.
我用bitmask实现了它,它是这样的:
int TSP(int pos, int bitmask) {
if (bitmask == (1<
return dist[pos][0]; // Completing the round trip
if (memo[pos][bitmask] != -1)
return memo[pos][bitmask];
int answer = INF;
for (int i = 0; i <= K; i++) {
if (i != pos && (bitmask & (1 << i)) == 0)
answer = Math.min(answer, dist[pos][i] + TSP(i, bitmask | (1 << i)));
}
return memo[pos][bitmask] = answer; // Storing the best dist for the set of traveled cities and untraveled ones.
}
这个算法很快;计算15个城市的速度相对较快.但是,我注意到它可以进一步改进,以容纳大约20个城市.
1)如果dist矩阵是对称的,也许我们可以利用这个属性来防止重复计算. (例如a-> b-> c-> d-> a == a-> d-> c-> b-> a)
2)使用上限和下限修剪.上述算法能够在很短的时间内获得其第一个可能的最优解,也许能够使用它.
我试图基于前面提到的两个原则来改进算法.但是,我没有得到更好的算法.
我是在徒劳地尝试改善不可能的事情吗?你怎么看?
转载地址:http://fuyms.baihongyu.com/