Обход взвешенного графа через все вершины, заканчивающиеся в одной и той же точке

Question

Существует ли алгоритм, который позволит мне проходить взвешенный граф следующим образом?

• Начать с определенного узла
• Пройти все вершины в графе
• Сделайте это за наименьшее количество времени (веса - времена)
• Конец в начальном узле

Answer 1

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

Answer 2

Как сказал Грег Секстон до меня, это классический пример проблемы коммивояжера. Есть много продвинутых алгоритмов для решения этого стиля проблемы, который лучше всего подходит для вашей конкретной ситуации, скорее зависит от графика. Если количество вершин велико, вам понадобится значительная вычислительная мощность, чтобы сделать это в реалистичные сроки.

Answer 3

Я не уверен, существует ли какой-либо эффективный алгоритм, но подход с использованием грубой силы наверняка даст вам ответ.

В любом случае, можете ли вы дать ограничения на количество вершин / ребер.