Это решение использует <tex>O(2^n)</tex> памяти и имеет асимптотику <tex>O(2^nn)</tex>.
== Реализация ==
Прежде чем писать код, скажем пару слов о порядке обхода состояний. Обозначим за <tex>|mask|</tex> количество единиц в маске (иначе говоря количество пройденных вершин не считая текущей). Тогда, поскольку при рассмотрении состояния <tex>\langle i, mask \rangle</tex> мы смотрим на состояния
<tex>\langle j, mask - 2^j \rangle</tex>, и <tex>|mask| = |mask - 2^j| + 1</tex>, то состояния с большим <tex>|mask|</tex> должны быть посещены позже, чтобы к моменту вычисления текущего состояния были вычислены все те, которые используются для его подсчёта.
Однако если использовать рекурсию, об этом можно не беспокоиться (и сэкономить немало кода, времени и памяти).
<span style="color:Green">//Все переменные используются из описания алгоритма, <tex>\infty</tex> = бесконечность</span>
'''function''' findCheapest(i, mask):
'''if''' d[i][mask] != <tex>\infty</tex>
'''return''' d[i][mask]
'''for''' j = 0 .. n - 1
'''if''' w(i, j) существует '''and''' j-ый бит mask == 1
d[i][mask] = '''min'''(d[i][mask], findCheapest(j, mask - 2 ** j) + w(i, j))
'''return''' d[i][mask]
'''for''' i = 0 .. n - 1
'''for''' mask = 0 .. 2 ** n - 1
d[i][mask] = <tex>\infty</tex>
d[0][0] = 0;
ans = findCheapest(0, 2 ** n - 1)
'''if''' ans == <tex>\infty</tex>
exit
Дальше ищем сам путь:
i = 0
mask = 2 ** n - 1
path.push(0)
'''while''' mask != 0
'''for''' j = 0 .. n - 1
'''if''' w(i, j) существует '''and''' j-ый бит mask == 1 '''and''' d[i][mask] == d[j][mask - 2 ** j] + w(i, j)
path.push(j)
i = j
mask = mask - 2 ** j
'''continue'''
== См. также ==
