Посетите все узлы ровно один раз в ориентированном графе
У меня есть ориентированный граф, и я хочу найти путь, который посещает каждый узел ровно один раз. Я хочу сделать это с хорошей сложностью. Это возможно? И если да, то как?
Решение
Вы ищете Гамильтонов путь, который является простым открытым путем, который содержит каждый узел ровно один раз.
Нахождение гамильтонова пути в данном графе NP-полной. Фактически, определение того, содержит ли данный (направленный или ненаправленный) граф гамильтонов путь, уже является NP-полным (доказано путем сокращения, например, из проблема покрытия вершин).
Если вы все еще хотите закодировать это, вот реализация на GitHub. Если вы хотите быстрое решение, возможно, достаточно эвристики (например, вдохновленный молекулами ДНК, или решение, которое работает быстро на подмножестве графиков. Например, если у вас есть группа доступности базы данных, вы можете выполнить топологическую сортировку, а затем проверить, связаны ли последовательные вершины. Если это так, топологическая сортировка дает гамильтонов путь.
Другие решения
Других решений пока нет …
detector