Python, Circular Shortest Path

Question

Я пытаюсь сделать странный метод поиска кратчайшего пути. Но я не знаю, как могу.

Мне нужен алгоритм. Я провел некоторое исследование и нашел некоторый алгоритм поиска кратчайшего пути, как алгоритм Дейкстры, алгоритм Флойда-Варшалла, алгоритм Джонсона. Но я думаю, что они не соответствуют моим ожиданиям.

Я хочу, что: Если начать с красными точками, должны пройти через все синие точки и заканчивается в красной точке.

Есть ли алгоритм для этого?

(Действительно жаль мой английский. Я надеюсь, что вы можете понять меня.)

Answer 1

Вашей проблемой является вариантом Hamiltonian Cycle Problem, который NP-Complete, так что не известно эффективным решения для него (и наиболее что решение не существует, но оно еще не доказано)

Проблема цикла гамильтониана говорит: если задан граф G=(V,E), найдите, есть ли простой цикл (каждая вершина проходит не чаще одного раза), которая проходит через все вершины , и является классической NP-полной проблемой.

Редукция довольно проста, учитывая проблему цикла Гамильтона, покрасьте одну случайную точку в красный цвет, а остальные точки в синем. Существует решение проблемы цикла Гамильтона в том и только в том случае, если решение вашей проблемы является простым путем по «модифицированной» задаче на новом графике.

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