Может кто-нибудь познакомить меня с гамильтоновым циклом?

Question

У меня есть этот проект, в котором я должен придумать исходный код Java, реализующий цикл Гамильтона.Я искал в Google, и по крайней мере теперь я знаю, что такое гамильтонов цикл, путь, который проходит через все вершины только один раз, кроме начальной, потому что это также последняя вершина (скажите мне, если я ошибаюсь).Проблема в том, что я не знаю, как это реализовать.В основном, мои вопросы:

1. Как, где вы реализуете гамильтонов цикл?
2. Что такое применение гамильтонова цикла (чтобы понять, почему это так важно)

Answer 1

1. Вы не реализуете гамильтонов цикл, вы находите его (или обнаруживаете, что для вашего заданного графа ничего не существует).Поскольку это NP-полная проблема, что означает, что это, вероятно, неэффективное решение, я бы просто реализовал простой алгоритм backtracking .Поскольку вы ищете цикл, не имеет значения, с какого узла вы начинаете.
2. Гамильтоновы циклы могут использоваться в криптографии для доказательств с нулевым знанием .Я не уверен, является ли это все еще просто исследованием или активно используется в каком-либо криптографическом протоколе.

Answer 2

(B) Практическое применение

• Определение наиболее эффективной коммутационной сети для телефонных систем
• Лучшие автобусные маршруты, почтовые маршруты, маршруты проверки счетчиков

Answer 3

Самый простой способ - начать с одного узла, «пометить его», выбрать следующий достижимый «немаркированный» узел, «пометить его» и продолжить до тех пор, пока:

• вы достигнете начального узла, таким образом, вы нашли гамильтонов цикл. Повторите цикл для каждого узла, чтобы найти каждый гамильтонов цикл в этом графе.
• Вы не можете выбрать другой «немаркированный» узел, что означает, что для этого начального узла нет гамильтонова цикла (но вы все равно нашли гамильтоновый путь).

Этот алгоритм может быть оптимизирован несколькими способами, но я позволю вам это вам. Любое решение, которое вы найдете, будет NP-завершенным.

Что касается их использования, я видел их только в теории графов и на занятиях по искусственному интеллекту (это особая проблема путешественника, где каждое ребро стоит 1), и они никогда не говорили мне об этом в реальной жизни.

Answer 4

Это домашняя работа? Если это так, пожалуйста, пометьте его как таковой.

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