Из этой статьи в Википедии:

http://en.wikipedia.org/wiki/Hamiltonian_path_problem

Рандомизированный алгоритм для гамильтонова пути, который является быстрым на большинстве графов, следующий: начните со случайной вершины и продолжайте, если сосед не посещался. Если соседей больше нет, а путь не сформированt Гамильтониан, выберите соседа наугад равномерно и вращайте, используя этого соседа в качестве точки поворота. (То есть добавьте ребро к этому соседу и удалите одно из существующих ребер из этого соседа, чтобы не образовывать петлю.) Затем продолжите алгоритм на новом конце пути.

Я неЯ не совсем понимаю, как этот процесс поворота должен работать. Может кто-нибудь объяснить этот алгоритм более подробно? Возможно, в конечном итоге мы сможем обновить статью Wiki с более четким описанием.

Изменить 1: Я думаю, что теперь понимаю алгоритм, но кажется, что он работает только для неориентированных графов. Кто-нибудь может это подтвердить?

Вот'Вот почему я думаю, что это работает только для неориентированных графов:

альтернативный текст http://www.michaelfogleman.com/static/images/graph.png

Представьте, что вершины пронумерованы так:

123
456
789

Позволять'Скажем, мой путь пока таков:9, 5, 4, 7, 8, 8'Соседи все были посещены. Позволять'скажем, я выбрал 5 для удаления ребра. Если я удаляю (9, 5), я просто создаю цикл:5, 4, 7, 8, 5так что, кажется, я должен удалить (5, 4) и создать (8, 5). Если график ненаправленный, тоХорошо, и теперь мой путь 9, 5, 8, 7, 4. Но если вы представите, что эти ребра направлены, тоНе обязательно правильный путь, так как (8, 5) является ребром, но (5, 8) может не быть.

Изменить 2: Я думаю, для ориентированного графа я мог бы создать соединение (8, 5), а затем позволить новому пути быть просто4, 7, 8, 5, но это кажется контрпродуктивным, так как я должен отрубить все, что ранее привело к вершине 5.