Вот немного менее математический псевдокод. Я не знаю, объяснит ли это, что происходит, но это может помочь вам прочитать это. Это не функциональный алгоритм (много всего :=), поэтому я собираюсь использовать псевдокод 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
Некоторые заметки:
- Алгоритм источника не завершен. По крайней мере, его форматирование является странным во внутреннем цикле, и оно связывает k во втором argmin. Таким образом, все это, вероятно, неправильно; Я не пытался запустить этот код.
- аргументы
range, вероятно, все должны быть увеличены на 1, так как Python считает от 0, а не от 1. (и вообще считать от 1 - плохая идея).
- Я предполагаю, что G - это словарь типа {from: {to: length}}. Другими словами, представление списка смежности.
- Я сделал вывод, что C - это словарь типа {(set (int), int): int}. Я могу ошибаться.
- Я использую
set в качестве ключей для C. В реальном Python вы должны сначала преобразовать в frozen_set. Преобразование - это просто занятая работа, поэтому я ее оставил.
- Я не могу вспомнить операторы множеств в Python. Кажется, я помню, он использует
| и & вместо + и -.
- Я не писал
subsets_of_size. Это довольно сложно.