LINUX.ORG.RU

[алгоритмы]Путь в графе заданной длины

 


0

1

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

Кто-нибудь может посоветовать хороший алгоритм для решения задачи?

★★

Думаю, можно хитро переделать алгоритм Дейкстры — он один фиг ищет путь до вершины на каждом от всех смежных вершин. Если запоминать не только минимальный путь, но и все не превосходящие (L + e)... Памяти только вот будет есть немерено.

helios ★★★★★
()
Ответ на: комментарий от helios

Если я правильно понял, о чем речь, то это по сути перебор с отсечением получается. У него ещё и сложность запредельная будет. :(

gizzka ★★
() автор топика
Ответ на: комментарий от gizzka

В худшем случае - близко к перебору. В лучшем - к сложности алгоритма Дейкстры. ЕМНИП, есть оптимизации до n*log(n). А так - квадратичная.

helios ★★★★★
()
Ответ на: комментарий от gizzka

Ну и ладно — она неправильная была...

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

helios ★★★★★
()

Имитацию отжига что ли попробовать прикрутить. А то слухи ходят, что задача NP-полная.

gizzka ★★
() автор топика

а если параллельно пойти по всем путям из А к B, притормаживая особо «жирные». И конечно распаралелить эти проходы в реализации? А можно дополнить вершины графа своей метаинфой?

pseudo-cat ★★★
()
Ответ на: комментарий от gizzka

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

gizzka ★★
() автор топика
Ответ на: комментарий от pseudo-cat

а если параллельно пойти по всем путям из А к B, притормаживая особо «жирные». И конечно распаралелить эти проходы в реализации? А можно дополнить вершины графа своей метаинфой?

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

Привязать свою метаинформацию можно, была бы необходимость :)

gizzka ★★
() автор топика
Ответ на: комментарий от gizzka

с чего это NP?
явно можно решить за N^4
ищем минимальный путь, сравниваем с заданным, удаляем его из графа, ищем и т.д.

anonymous
()
Ответ на: комментарий от anonymous

явно можно решить за N^4

У описанного метода сложность как у перебора же?

gizzka ★★
() автор топика

этож задача коммивояжера

Может быть вполне. Объясните, пожалуйста, почему?

gizzka ★★
() автор топика
Ответ на: комментарий от anonymous

блджад. этож задача коммивояжера

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

Я бы назвал это «задачей водителя», которому нужно «отмыть» n-е количество топлива :)

В принципе, если поковыряться в каких-нибудь gsl/blas'овских методах поиска минимального пути, можно, наверное, сделать и поиск пути, длина которого наиболее близка к заданной.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

Я бы назвал это «задачей водителя», которому нужно «отмыть» n-е количество топлива :)

Так, актуальность задачи определили... :)

gizzka ★★
() автор топика

задача отлично распараллеливается.

есть такая идея:
Берем erlang. Вершина == процесс + в ets храним матрицу смежности.
Дальше посылаем начальной вершине V1 сообщение с вершиной Vn куда хотим.
Из ets вынимаем все смежные вершины и пересылаем им сообщение:
[{end, Vn}, {path, [V1]}, {index, gb_trees(V1)}], где path — путь текущий, gb_trees — дерево с вершинами путя, для того чтобы быстро понимать, были мы уже в этом узле или нет. Дальше все аналогично.

Соответственно если сообщение приходит процессу Vn и конечный пункт маршрута равен Vn, Он накапливает результат.

В результате будут все пути из V1 в Vn. Единственное, что можно передавать не такие большие сообщения, а некий индекс в ets таблице.

«+» — мы всегда можем у вершины Vn спрашивать промежуточный ответ и бывают ситуации когда, этот промежуточный ответ лучше, чем ждать еще чего-то. можно быстро грохнуть все процессы.
 — все ядра будут загружены

"-" — не совсем понятно, как понять, что процесс поиска завершился. Но это решаемо.

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

arhibot
()
Ответ на: комментарий от gizzka

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

anonymous
()
Ответ на: комментарий от anonymous

есть вообще замечательное средство для работы с огромными графами Phoebus(свободная реализация Pregel на erlang)

arhibot
()
Ответ на: комментарий от gizzka

> А требуется найти путь заданной длины, а не кратчайший.

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

dave ★★★★★
()
Ответ на: комментарий от dave

Кстати, некоторые известные сетевые алгоритмы легко выводятся такими уравнениями.

dave ★★★★★
()
Ответ на: комментарий от dave

> уравнения динамического программирования
Я не автор вопроса, но не смог сообразить, как сформулировать эту задачу в терминах динамического программирования. Так просто, как с задачей кратчайшего пути, не получается сформулировать. Не подскажете, как это сделать? На ум приходят только решения, завязанные так или иначе на перебор всех путей из A в B.

ringill
()
Ответ на: комментарий от anonymous

> ищем минимальный путь, сравниваем с заданным, удаляем его из графа
Весь путь удаляем? А если в нём была вершина, через которую на самом деле проходит искомый путь?

ringill
()
Ответ на: комментарий от Waterlaz

Однако, если все веса целочисленные, то можно решить за.. что-то около O(L*(V+E))

V - количество вершин

E - количество ребер

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

Хотя, нет. Вру. С условием на отсутствие циклов нельзя все равно.

Waterlaz ★★★★★
()
Ответ на: комментарий от dave

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

Ну и похоже, что в бусте реализован алгоритм решения более общей задачи (http://www.boost.org/doc/libs/1_45_0/libs/graph/doc/r_c_shortest_paths.html), но с ним ещё надо разобраться, пока не осилил. Да и статью что-то найти не могу, на которую в доке ссылаются.

gizzka ★★
() автор топика
Ответ на: комментарий от gizzka

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

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от gizzka

> статью что-то найти не могу
Статья есть например тут:
http://online-termine.de/Diplomarbeit/Irnich_or_2004-01.pdf
(найдено через Google Scholar)

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

ringill
()
Ответ на: комментарий от ringill

>> В заданной формулировке задача NP-полная.

Подскажите доказательство?

Ну.. Есть такие рассуждения: Задача комивояжера сводится к задаче поиска максимального пути без циклов, которая в свою очередь сводится к задаче ТС.

Waterlaz ★★★★★
()
Ответ на: комментарий от gizzka

отсечение вы понимаете как что-то типа - выбирать наиболее короткие пути, ведущие к ветвям на n-уровне(n - какой-то числой ряд, выбранный вами), остальные пути нах естессно. Такая «зачистка» и в самом деле может нехило сократить порядок роста в общем случае. Но всё равно это не годная тактика?

pseudo-cat ★★★
()
Ответ на: комментарий от Waterlaz

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

Как я только что понял, можно добавить в граф ещё две вершины и соединить одну из них с A, вторую с B, и тогда «любой простой путь через все вершины» как раз и будет содержать в себе простой путь от A до B.

Выходит что да, задача NP-трудная.

ringill
()

Если уж это алгоритм «водителя», то как вариант нужно знать кратчайший путь и знать какие «петли» дают необходимы прирост по весам. Брать кратчайший путь и прибавляя к нему вершины, смотреть насколько приблизились к L. Всё это смахивает на генетический алгоритм больше. Мутации / отбор. Может и ошибаюсь.

m4n71k0r
()
Ответ на: комментарий от m4n71k0r

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

m4n71k0r
()
Ответ на: комментарий от m4n71k0r

Мыслите в правильном направлении! ТСу курить эвристический поиск. Для построения правильной эвристики много даст струкутра конкретной задачи.

anonymous
()
Ответ на: комментарий от m4n71k0r

Забыл добавить, AIMA ТСу почитать нужно.

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.