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

Question

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

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

Answer 1

Все остальные, сравнивающие это с проблемой коммивояжера, вероятно, не внимательно прочитали ваш вопрос. В 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 ³ ) для части Флойда-Варшалла и O (k! N) для части всех перестановок, и 100 ^ 3 + (12!) (100) - это практически арахис, если у вас нет действительно ограничительных ограничений.]

Answer 2

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

Answer 3

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

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

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

Answer 4

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

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

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

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

Answer 5

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

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

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

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

Answer 6

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

• [Пуск-> a-> b-> c-> конец]
• [Пуск-> a-> c-> b-> конец]
• [Пуск-> b-> а-> C-> конец]
• [Пуск-> b-> c-> a-> конец]
• [Пуск-> c-> a-> b-> конец]
• [Пуск-> c-> b-> a-> конец]

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

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

Answer 7

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

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

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

Answer 8

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

Answer 9

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

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

Answer 10

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

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

Конечный путь состоит из:

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

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

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

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

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