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

Ответ 1

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

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

Ответ 2

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

Ответ 3

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

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

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

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

Ответ 4

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

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

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

Ответ 5

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

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

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

Ответ 6

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

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

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

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

Ответ 7

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

Ответ 8

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

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

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

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

Ответ 9

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

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

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

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

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

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

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

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

Ответ 10

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

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