Найдите кратчайший путь в графике, который посещает определенные узлы
8 ответов
Все остальные сравнивающие это с проблемой Коммивояжера, вероятно, не считали Ваш вопрос тщательно. В TSP цель состоит в том, чтобы найти самый короткий цикл, который посещает весь вершины (гамильтонов цикл) - это соответствует наличию каждый , узел маркировал 'mustpass'.
В Вашем случае, учитывая, что у Вас есть только приблизительно дюжина, маркировал 'mustpass', и, учитывая, что 12! довольно маленький (479001600), можно просто попробовать все перестановки только 'mustpass' узлов и посмотреть на кратчайший путь от 'запуска' для 'заканчиваний', который посещает 'mustpass' узлы в том порядке - это просто будет конкатенация кратчайших путей между каждыми двумя последовательными узлами в том списке.
, Другими словами, сначала найдите кратчайшее расстояние между каждой парой вершин (можно использовать алгоритм или других Dijkstra, но с теми небольшими числами (100 узлов), даже самое простое к коду алгоритм Floyd-Warshall будет работать вовремя). Затем как только у Вас есть это в таблице, попробуйте все перестановки своих '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 ) для части Floyd-Warshall и O (k! n) для всей части перестановок, и 100^3 + (12!) (100) практически арахис, если у Вас нет некоторых действительно строгих ограничений.]
выполненный Алгоритм Djikstra для нахождения кратчайших путей между всеми критическими узлами (запускаются закончите, и должен-передача), тогда обход в глубину должен сказать Вам кратчайший путь через получающийся подграф, который затрагивает, все узлы запускаются... mustpasses... заканчиваются
На самом деле проблема, которую Вы отправили, подобна коммивояжеру, но я думаю ближе к простой новаторской проблеме. Вместо того, чтобы должными быть посетить каждый узел, просто необходимо посетить определенный набор узлов в самое короткое время возможное (расстояние).
причина этого состоит в том, что, в отличие от проблемы коммивояжера, лабиринт зерна не позволит Вам путешествовать непосредственно от любой точки до любой другой точки на карте, не будучи должен пройти через другие узлы для получения там.
я на самом деле рекомендовал бы* новаторский как техника рассмотреть. Вы настраиваете это путем решения, какие узлы имеют доступ, к которому другие узлы непосредственно, и что "стоимость" каждого транзитного участка от конкретного узла. В этом случае похоже, что каждый "транзитный участок" мог иметь равную стоимость, так как Ваши узлы кажутся относительно близко расположенными.* может использовать эту информацию для нахождения самого дешевого пути между любыми двумя точками. Так как необходимо заставить от точки указывать на B и посещать приблизительно 12 промежутков, даже метод решения "в лоб", использующий новаторский, не причинил бы боль вообще.
Просто альтернатива для рассмотрения. Это действительно смотрит замечательно как проблема коммивояжера, и те - хорошие бумаги для чтения на, но выглядеть ближе и Вы будете видеть что его единственные сверхусложняющие вещи. ^_^ Это прибытие из ума программиста видеоигр, который имел дело с этими видами вещей прежде.
Andrew Top имеет верное представление:
1) Алгоритм Djikstra 2) Некоторая эвристика TSP.
я рекомендую эвристику Lin-Kernighan: это - один из известных прежде всего любым NP Полная проблема. Единственная другая вещь помнить состоит в том, что после расширения графика снова после шага 2 у Вас могут быть циклы в Вашем разобранном контуре, таким образом, необходимо бродить вокруг, замыкание накоротко тех (посмотрите на степень вершин вдоль пути).
я на самом деле не уверен, насколько хороший это решение будет относительно оптимума. Существуют, вероятно, некоторые патологические случаи, чтобы сделать со срыванием. В конце концов, эта проблема МНОГО походит на Дерево Steiner: http://en.wikipedia.org/wiki/Steiner_tree и Вы определенно не можете приблизить Дерево Steiner, просто сократив Ваш график и выполнив Kruskal, например.
Это - две проблемы... Steven Lowe указал на это, но не дал достаточно уважения к второй половине проблемы.
необходимо сначала обнаружить кратчайшие пути между всеми критическими узлами (запустите, закончитесь, mustpass). Как только эти пути обнаружены, можно создать упрощенный график, где каждый край в новом графике является путем от одного критического узла до другого в исходном графике. Существует много новаторских алгоритмов, которые можно использовать для нахождения кратчайшего пути здесь.
, Как только у Вас есть этот новый график, тем не менее, у Вас есть точно проблема Продавца Перемещения (хорошо, почти... Никакая потребность вернуться к Вашему начальному вопросу). Любое из сообщений относительно этого, упомянутого выше, будет применяться.
Рассмотрение суммы узлов и краев относительно конечно, можно, вероятно, вычислить каждый возможный путь и взять самый короткий.
Обычно известный как проблема коммивояжера, и имеет недетерминированное полиномиальное время выполнения, неважно, что алгоритм Вы используете.
Как насчет применения грубой силы к дюжине узлов, которые должны посетить? Вы можете достаточно легко охватить все возможные комбинации из 12 узлов, и это оставляет вас с оптимальной схемой, по которой вы можете следовать, чтобы покрыть их.
Теперь ваша задача упрощена до одной из поиска оптимальных маршрутов от начального узла до схемы, по которым вы затем следуете, пока не пройдете их, а затем найдите маршрут от этого до конца.
Окончательный путь состоит из:
начало -> путь к цепи * -> цепь узлов, которые необходимо посетить - > путь до конца * -> конец
Вы найдете пути, отмеченные мной знаком *, как это
Выполните поиск A * от начального узла до каждой точки в цепи для каждого из них выполните поиск A * от следующего и предыдущего узла схемы до конца (потому что вы можете следить за обходом схемы в любом направлении) В итоге вы получите множество путей поиска, и вы можете выбрать тот, который стоит меньше всего.
Есть много возможностей для оптимизации за счет кеширования поисковых запросов, но я думаю, что это приведет к хорошим решениям.
Это не идет ни в какое сравнение с поиском оптимального решения, потому что это может включать в себя оставление схемы, которую необходимо посетить в пределах Поиск.
Одна вещь, которая нигде не упоминается, это то, можно ли посещать одну и ту же вершину более одного раза на пути. Большинство ответов здесь предполагают, что можно посещать одно и то же ребро несколько раз, но я считаю, что с учетом вопроса (путь не должен посещать одну и ту же вершину более одного раза!), Это не нормально, чтобы посетить одну и ту же вершину дважды.
Таким образом, подход грубой силы все равно будет применяться, но вам придется удалить уже используемые вершины, когда вы пытаетесь вычислить каждое подмножество пути.