Изменения
→Алгоритм нахождения гамильтового пути
В массиве <tex>d[i][mask]</tex> мы хранили расстояния, но сейчас нас не интересует какой длины будет это расстояние, так как главной задачей является нахождение цикла. В этом массиве мы теперь просто храним посещение вершин. И каждый раз, когда при запуске находим непосещенную вершину, то запускаем функцию рекурсивно от нее. Если она возвращает <tex> true</tex>, то есть до вершины можно добраться, то записываем, что мы можем посетить вершину. Проходы так же осуществляются по рёбрам.
==== Алгоритм нахождения гамильтового гамильтонова пути ====Алгоритм нахождения гамильтонова пути легко получить слегка изменив алгоритм нахождения гамильтонова цикла. '''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'''Длину пути можно узнать как path.sizeмы запускаем наш алгоритм поочередно из каждой вершины графа.
== См. также ==
