алгоритм нахождения порядка посещения узлов графа

Question

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

Answer 1

Похоже на задачу коммивояжера или близкий вариант, хотя и ограниченный, если график неполон.

Answer 2

Возможно, вы можете использовать модифицированный A * Алгоритм .Обычно вы начинаете с X и заканчиваете, когда достигаете Y. В модифицированной версии вы не останавливаетесь, когда достигаете некоторого узла Y, но когда вы посетили все узлы.Также обратите внимание, что если какой-то узел был посещен, переходить на него с другого узла бессмысленно, это должно сработать.

Answer 3

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

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