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

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

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

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

Так, тогда я не понял идею. :(

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

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

в boost'е есть несколько алгоритмов на эту тему

Например?

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

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

http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/table_of_contents.html

Shortest Paths Algorithms:
dijkstra_shortest_paths,
bellman_ford_shortest_paths,
dag_shortest_paths,
johnson_all_pairs_shortest_paths,
floyd_warshall_all_pairs_shortest_paths

http://www.boost.org/doc/libs/1_45_0/libs/graph/doc/table_of_contents.html актуальнее

Shortest Paths Algorithms

Shortest Paths

Shortest

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

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

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

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

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

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

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

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

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

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

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

совсем не задача коммивояжера

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Да, не подумал. У меня тоже не получилось. Тогда остается перебор?

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

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

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

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

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

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

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

> В заданной формулировке задача NP-полная.
Подскажите доказательство?

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

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

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

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

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

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

А задача комивояжера NP-полная.

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

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

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

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

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

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

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

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