308
правок
Изменения
Переписан код на рекурсию
Прежде чем писать код, скажем пару слов о порядке обхода состояний. Обозначим за <tex>|mask|</tex> количество единиц в маске (иначе говоря количество пройденных вершин не считая текущей). Тогда, поскольку при рассмотрении состояния <nowiki><</nowiki><tex>i, mask </tex><nowiki>></nowiki> мы смотрим на состояния
<nowiki><</nowiki><tex>j, mask - 2^j </tex><nowiki>></nowiki>, и <tex>|mask| = |mask - 2^j| + 1</tex>, то состояния с большим <tex>|mask|</tex> должны быть посещены позже, чтобы к моменту вычисления текущего состояния были вычислены все те, которые используются для его подсчёта.Однако если использовать рекурсию, об этом можно не беспокоится (и сэкономить немало кода, времени и памяти)
//Все переменные используются из описания алгоритма, inf = бесконечность
''findCheapest'' (i, mask)
'''if''' d[i][mask] != inf
'''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] = inf
d[0][0] = 0;
== Ссылки ==
