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

84

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

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

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

Даниэль
источник

Ответы:

78

Все остальные, сравнивающие это с проблемой коммивояжера, вероятно, не внимательно прочитали ваш вопрос. В 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) практически пустяки, если только у вас нет действительно ограничивающих ограничений.]

ShreevatsaR
источник
6
Учитывая небольшой размер ввода, я согласен с ответом. Но меня интересует, почему вы отвергаете утверждения других о том, что это TSP. Насколько я понимаю, вы можете извлечь все узлы, которые необходимо пройти, и использовать их для создания подграфа. Ребра между узлами в подграфе имеют веса, соответствующие решению APSP на исходном графе. Тогда не становится ли вопрос примером TSP на подграфе? Ваше решение, похоже, является решением этой проблемы методом перебора (и это нормально).
maditya 05
7
@maditya: Во-первых, я надеюсь, вы согласны с тем, что (цитируя комментарий Стивена Лоу к другому ответу) такой ответ, как «TSP - это сложно, бвахахаха», не является подходящим ответом для тех, у кого есть настоящая проблема, которую нужно решить, особенно очень легко решена на любом компьютере за последние несколько десятилетий. Во-вторых, это не идентично TSP по тривиальным причинам (другой формат ввода): крошечный экземпляр TSP, который он содержит, предназначен для меньшего графа, а не для входного размера N. Таким образом, NP-полнота зависит от того, сколько узлов необходимо передать. есть асимптотически: если всегда 12 или O (log N), это не NP-полный и т. д.
ShreevatsaR 08
1
Я не уверен, что в результате получится путь. Представьте, что вам нужно пройти от одного aдо cдругого b. Может случиться так, что кратчайшие пути от bдо aи cразделяют ребро. В этом случае ребро будет повторяться дважды. Один из двух путей должен быть хуже оптимального, чтобы не генерировать циклы.
Spak
1
@PietroSaccardi Из описания в вопросе кажется, что цель состоит в том, чтобы просто найти кратчайший «путь» прохождения всех этих узлов, и это может быть нормально, если какое-то ребро повторяется. То есть «путь» используется в широком смысле. Фактически, если повторение ребер недопустимо, может даже не быть ответа (например, рассмотрим граф B — A — C, где вас просят перейти от A к C при прохождении через B: нет способа не повторить Б - ребро).
ShreevatsaR
Алгоритм Флойда-Уоршалла здесь реализован некорректно: поскольку все ячейки массива инициализируются с помощью INF, строка d[i][j] = min(d[i][j], d[i][k] + d[k][j])становится d[i][j] = min(INF, INF + INF)равной, а все ячейки всегда остаются равными INF. Вам нужно добавить шаг, чтобы заполнить этот массив длинами ребер из графа.
Стеф
25

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

Стивен А. Лоу
источник
Похоже, что у него есть потенциал быть более эффективным, чем выбранное решение. Бьюсь об заклад, если бы вы расширили его, он бы набрал больше очков. Сначала мне пришлось подумать о том, гарантирует ли кратчайший путь между всеми парами путь между всеми необходимыми узлами ... но я верю, что да (при условии ненаправленного).
galactikuh 03
Я думаю, что это не сработает, если путь не должен повторять края.
тукет
1
Как при обходе в глубину найти кратчайший путь в примере 24-го дня появления кода? adventofcode.com/2016/day/24
Эрвин Ройаккерс
16

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

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

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

Эндрю Топ
источник
14

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

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

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

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

Николас Флинт
источник
2
+1 - это гораздо лучший ответ, чем «проблема коммивояжера - сложная задача, бвахахаха»
Стивен А. Лоу
5

У Эндрю Топа правильная идея:

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

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

На самом деле я не уверен, насколько хорошо это решение будет по сравнению с оптимальным. Вероятно, есть патологические случаи, связанные с коротким замыканием. В конце концов, эта проблема ОЧЕНЬ похожа на Steiner Tree: http://en.wikipedia.org/wiki/Steiner_tree, и вы определенно не можете приблизиться к Steiner Tree, например, просто сжав свой граф и запустив Kruskal's.

Инь Сяо
источник
5

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

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

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

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

Bjorke
источник
Посещение только один раз требуется при условии, что это кратчайший путь.
Азиут, 09
Ага. Минуту назад я был совершенно уверен, но да, ты прав. Очевидно, не в дереве с несколькими ветвями. Но дело в том, что если мы абстрагируем проблему до нового графа, который содержит только полностью связанные узлы mustpass, с узлами, имеющими расстояние кратчайшего пути в исходном графе, мы придем к TSP. Итак, вы уверены, что это не сложно? Я бы предположил, что в общей задаче количество узлов, которые необходимо пройти, зависит от общего количества узлов, и если, например, сумма является полиномом от числа узлов, которые должны пройти, мы получаем NP-жесткость, верно?
Азиут,
Маршрут, скажем, от a-> b может проходить через c. Так что ни один брнач не мешает другому. Это просто перестановка.
bjorke
Да? Но перестановка равна O (n!), Если мы предположим, что количество узлов, которые должны пройти, имеет некоторую связь с количеством общих узлов, например, «общее количество узлов - это многочлен от узлов, которые должны пройти». Вы только что решили TSP грубой силой.
Азиут,
2

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

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

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

Rafe
источник
1

Вопрос говорит о must-pass в ЛЮБОМ порядке . Я пытался найти решение об определенном порядке узлов, которые необходимо пройти. Я нашел свой ответ, но, поскольку ни у одного вопроса о StackOverflow не было аналогичного вопроса, я публикую здесь, чтобы дать людям возможность извлечь из него пользу.

Если порядок или обязательный проход определены, вы можете запустить алгоритм Дейкстры несколько раз. Например , давайте предположим , что вы должны начать с sпрохода через k1, k2и k3(в соответствующем порядке) и остановка на e. Затем вы можете запустить алгоритм Дейкстры между каждой последовательной парой узлов. Стоимость и путь будет по формуле:

dijkstras(s, k1) + dijkstras(k1, k2) + dijkstras(k2, k3) + dijkstras(k3, 3)

Сайед Хиссаан
источник
0

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

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

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

начало -> путь к схеме * -> схема узлов, обязательных к посещению -> путь до конца * -> конец

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

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

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

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

Justinhj
источник
0

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

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

Кирш
источник