1

这是 TSP（旅行商问题）的动态编程伪代码。我了解它的最佳子结构，但我无法弄清楚红括号中的代码是做什么的。

我不是要求任何人编写实际代码，我只需要解释正在发生的事情，这样我就可以编写自己的......谢谢:)

这是伪代码的链接，我不能在这里上传。 http://www.imagechicken.com/viewpic.php?p=1266328410025325200&x=jpg

4

1 回答 1

2

这是一些不太数学的伪代码。我不知道这是否会解释正在发生的事情，但它可能会帮助您阅读它。这不是一个函数式算法（很多:=都结束了），所以我将使用 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

一些注意事项：

  1. 源算法不完整。至少，它的格式在内部循环中很奇怪，并且它在第二个argmin 中重新绑定了k 。所以整个事情可能是错的；我没有尝试运行此代码。
  2. to 的参数range可能都应该加 1，因为 Python 从 0 开始计数，而不是 1。（通常从 1 开始计数是个坏主意）。
  3. 我假设 G 是 { from : { to : length } } 类型的字典。换句话说，邻接表表示。
  4. 我推断 C 是类型为 { (set(int),int) : int } 的字典。我可能是错的。
  5. 我使用 aset作为C. 在真正的 Python 中，您必须转换为frozen_set第一个。转换只是忙碌的工作，所以我把它省略了。
  6. 我不记得 Python 中的集合运算符。我似乎记得它使用|and&而不是+and -。
  7. 我没写subsets_of_size。这相当复杂。
于 2010-02-16T15:12:36.580 回答