Найдите кратчайший путь в графе, который посещает определенные узлы.

StackOverflow https://stackoverflow.com/questions/222413

  •  03-07-2019
  •  | 
  •  

Вопрос

У меня есть неориентированный граф примерно со 100 узлами и около 200 ребрами.Один узел помечен как «начало», другой — «конец», и около дюжины имеют пометку «mustpass».

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

( http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt речь идет о графике — он представляет кукурузный лабиринт в Ланкастере, штат Пенсильвания)

Это было полезно?

Решение

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

В вашем случае, учитывая, что у вас есть только около дюжины помеченных как «mustpass», и учитывая, что 12! достаточно маленький (479001600), вы можете просто попробовать все перестановки только узлов 'mustpass' и посмотреть кратчайший путь от 'start' до 'end', который посещает узлы 'mustpass' в этом порядке - он просто быть конкатенацией кратчайших путей между каждыми двумя последовательными узлами в этом списке.

Другими словами, сначала найдите кратчайшее расстояние между каждой парой вершин (вы можете использовать алгоритм Дейкстры или другие, но с этими небольшими числами (100 узлов), даже с самым простым для кодирования алгоритм Флойда-Варшалла будет запущен вовремя). Затем, как только вы получите это в таблице, попробуйте все перестановки ваших узлов 'mustpass' и остальные.

Примерно так: 

//Precomputation: Find all pairs shortest paths, e.g. using Floyd-Warshall
n = number of nodes
for i=1 to n: for j=1 to n: d[i][j]=INF
for k=1 to n:
    for i=1 to n:
        for j=1 to n:
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
//That *really* gives the shortest distance between every pair of nodes! :-)

//Now try all permutations
shortest = INF
for each permutation a[1],a[2],...a[k] of the 'mustpass' nodes:
    shortest = min(shortest, d['start'][a[1]]+d[a[1]][a[2]]+...+d[a[k]]['end'])
print shortest

(Конечно, это не настоящий код, и если вы хотите получить реальный путь, вам придется отслеживать, какая перестановка дает наименьшее расстояние, а также, каковы кратчайшие пути для всех пар, но вы понимаете. )

Он будет работать не более нескольких секунд на любом приемлемом языке :)
[Если у вас есть n узлов и k 'mustpass' узлов, его время выполнения составляет O (n 3 ) для части Флойда-Варшалла и O (k! N) для части всех перестановок, и 100 ^ 3 + (12!) (100) - это практически арахис, если у вас нет действительно ограничительных ограничений.]

Другие советы

запустите алгоритм Джикстры , чтобы найти кратчайшие пути между всеми критическими узлами (начало, конец , и must-pass), тогда обход в глубину должен сказать вам кратчайший путь через результирующий подграф, который касается всех узлов start ... mustpasses ... end

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

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

Я бы порекомендовал A * pathfinding в качестве метода для рассмотрения. Вы настраиваете это, решая, какие узлы имеют доступ к каким другим узлам напрямую, и какова стоимость " стоимости " каждого прыжка от конкретного узла. В этом случае это выглядит как каждый «прыжок» может иметь одинаковую стоимость, так как ваши узлы кажутся относительно близко расположенными * Может использовать эту информацию, чтобы найти путь с наименьшей стоимостью между любыми двумя точками. Поскольку вам нужно добраться из пункта А в пункт Б и посетить около 12 промежуточных точек, даже грубый подход с использованием поиска пути не повредит вообще.

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

Это две проблемы ... Стивен Лоу указал на это, но не уделил достаточного внимания второй половине проблемы.

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

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

Эндрю Топ имеет правильную идею:

1) Алгоритм Джикстры 2) Некоторый TSP эвристический.

Я рекомендую эвристику Лин-Кернигана: она является одной из самых известных для любой задачи NP Complete. Единственное, что нужно помнить, это то, что после того, как вы снова развернули график после шага 2, у вас могут появиться петли в расширенном пути, поэтому вы должны обойти их короткими замыканиями (посмотрите на степень вершин вдоль вашего пути).

Я на самом деле не уверен, насколько хорошо это решение будет относительно оптимального. Вероятно, есть некоторые патологические случаи, связанные с коротким замыканием. В конце концов, эта проблема выглядит очень похоже на дерево Штейнера: http://en.wikipedia.org/wiki/Steiner_tree и вы определенно не можете аппроксимировать дерево Штейнера, просто заключив график и запустив, например, Kruskal.

Это нет проблема TSP, а не NP-сложная, поскольку исходный вопрос не требует, чтобы обязательные узлы посещались только один раз.Это значительно упрощает ответ: просто перебор после составления списка кратчайших путей между всеми узлами, которые необходимо пройти, с помощью алгоритма Дейкстры.Возможно, есть лучший способ, но самый простой — просто обработать двоичное дерево в обратном направлении.Представьте себе список узлов [начало,a,b,c,конец].Суммируйте простые расстояния [start->a->b->c->end], и это будет ваша новая целевая дистанция, которую нужно преодолеть.Теперь попробуйте [start->a->c->b->end] и, если это лучше, установите это в качестве цели (и помните, что оно получено из этого шаблона узлов).Работайте над перестановками в обратном порядке:

  • [начало->a->b->c->конец]
  • [начало->a->c->b->конец]
  • [начало->b->a->c->конец]
  • [начало->b->c->a->конец]
  • [начало->c->a->b->конец]
  • [начало->c->b->a->конец]

Один из них будет самым коротким.

(где находятся узлы «посещенные несколько раз», если таковые имеются?Они просто скрыты на этапе инициализации кратчайшего пути.Кратчайший путь между a и b может содержать c или даже конечную точку.Вас это не должно волновать)

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

Обычно это называется проблемой коммивояжера и имеет недетерминированную полиномиальную среду выполнения независимо от используемого вами алгоритма.

http://en.wikipedia.org/wiki/Traveling_salesman_problem

Как насчет использования грубой силы на дюжине узлов, которые нужно посетить? Вы можете достаточно легко охватить все возможные комбинации из 12 узлов, и это даст вам оптимальную схему, которой вы сможете следовать, чтобы покрыть их.

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

Окончательный путь состоит из:

start - > путь к цепи * - > схема должна посещать узлы - > путь до конца * - > конец

Вы найдете пути, которые я пометил * вот так

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

Существует много возможностей для оптимизации путем кэширования запросов, но я думаю, что это приведет к хорошим решениям.

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

Одна вещь, которая нигде не упоминается, это то, можно ли посещать одну и ту же вершину более одного раза в пути. Большинство ответов здесь предполагают, что можно посещать одно и то же ребро несколько раз, но мой вопрос, учитывая вопрос (путь не должен посещать одну и ту же вершину более одного раза!), Заключается в том, что не нормально посетить одну и ту же вершину дважды.

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top