Изменения
→Алгоритм нахождения гамильтового пути
==Алгоритм нахождения гамильтового пути==
Алгоритм нахождения гамильтонова пути легко получить слегка изменив алгоритм нахождения гамильтонова цикла.
=== Псевдокод ===
'''bool''' findPath(i, mask):
'''if''' d[i][mask]
'''return''' true
'''for''' j = 0 .. n - 1
'''if''' w(i, j) существует '''and''' j-ый бит mask == 1
'''if''' findPath(j, mask - 2 ** j)
d[i][mask] = true
'''return''' d[i][mask]
'''for''' i = 0 .. n - 1
'''for''' mask = 0 .. 2 ** n - 1
d[i][mask] = false
d[0][0] = true;
ans = findPath(0, 2 ** n - 1)
'''if''' ans == false
exit
Дальше ищем сам путь:
i = 0
mask = 2 ** n - 1
'''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] == true
path.push(j)
i = j
mask = mask - 2 ** j
'''continue'''
==Источники информации==
