旅行商的动态规划伪码
旅行商的动态规划伪码
提问于 2010-02-16 12:54:43
这是TSP (旅行推销员问题)的一个动态规划伪码。我理解它的最优子结构，但我不知道红括号中的代码是做什么的。
我不是要任何人写实际的代码，我只需要解释一下正在发生的事情，这样我才能写我自己的代码.谢谢：)
这里有一个伪码的链接，我不能上传到这里。http://www.imagechicken.com/viewpic.php?p=1266328410025325200&x=jpg
回答 1
Stack Overflow用户
发布于 2010-02-16 15:12:36
下面是一些较少数学的伪码。我不知道这是否能解释发生了什么，但它可能会帮助你阅读。这不是一个函数式算法(到处都是:= )，所以我将使用Python伪代码。
# I have no idea where 'i' comes from. It's not defined anywhere
for k in range(2,n):
C[set(i,k), k] = d(1,k)
shortest_path = VERY_LARGE_NUMBER
# I have to assume that n is the number of nodes in the graph G
# other things that are not defined:
# d_i,j -- I will assume it's the distance from i to j in G
for subset_size in range(3,n):
for index_subset in subsets_of_size(subset_size, range(1,n)):
for k in index_subset:
C[S,k] = argmin(lambda m: C[S-k,m] + d(G,m,k), S - k)
shortest_path = argmin(lambda k: C[set(range(1,n)),k] + d(G,1,k), range(2,n))
return shortest_path
# also needed....
def d(G, i, j):
return G[i][j]
def subsets_of_size(n, s): # returns a list of sets
# complicated code goes here
pass
def argmin(f, l):
best = l[0]
bestVal = f(best)
for x in l[1:]:
newVal = f(x)
if newVal < bestVal:
best = x
bestVal = newVal
return best一些注意事项：
- 源算法不完整。至少，它的格式在内部循环中是奇怪的，它在第二个argmin中重新绑定k。所以，整件事可能是错误的；我没有尝试过将这个code.
- arguments运行到
range，可能所有这些都应该增加1，因为Python从0开始计数，而不是1。(通常从1计数是个坏主意)。 - ，我假设G是类型为{ from：{ to : length } }的字典。换句话说，邻接列表representation.
- I推断C是{ (set( int)，int )：int }类型的字典。我可能错了。
- 我用
set作为C的钥匙。在真正的Python中，您必须首先转换为frozen_set。转换很忙，所以我忽略了它。
，
- ，我不记得Python中的set操作符了。我似乎记得它使用的是
|和&，而不是+，而不是subsets_of_size。这是相当complicated.
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2272963
复制相关文章
相似问题
腾讯云开发者
