.question | Shortest Path Problem
Пытаюсь наверстать все лекции по «конкретной математике», что когда-то сознательно были прогуляны на первом курсе в универе, а потому интересуют популярные решения одной, довольно банальной проблемы, завязанной вокруг теории графов.
Предположим, что есть у меня таблица с нодами, что-то из серии CREATE TABLE nodes(id INT4, name VARCHAR(255)), далее есть вторая таблица, в которой сохранены все «отношения» между любой пары нод, например: CREATE TABLE paths(parent INT4, child INT4).
![[image]](http://upload.wikimedia.org/wikipedia/commons/5/57/6n-graf.png)
Задача такова – найти самый короткий путь между любыми двумя нодами (например, между нодами 1 и 3 на рисунке). Какие есть алгоритмы, кроме тех, что описаны в википедии? Да и вообще, есть ли они?
amix
автоподстановка ЧПУ? :)
интересно.. жаль, я ничего не понимаю в математике. кроме того, что нажито практикой. ))
13.08.2005 // 18:16 [ ссылка ]
Scout
Привет! Извини, что не по теме, но!
Вижу, что при входе на dull.ru - на главной странице проходят все новости, не важно какой раздел. Вопрос вот в чём! Можно ли блокировать такой вывод и показывать определённые новости только при заходе в раздел?
14.08.2005 // 18:24 [ ссылка ]
Ответ от Автора
да
15.08.2005 // 03:40 [ ссылка ]
Антон Скоробогатов
Один из самых быстрых на сегодняшний день алгоритмов - генетический. Где прочитать не знаю, могу объяснить на пальцах.
15.08.2005 // 21:53 [ ссылка ]
Ответ от Автора
было бы более чем интересно!!! =))
16.08.2005 // 12:31 [ ссылка ]
freex
2 Антон Скоробогатов
Передо мной стоит такая же задача, опишите пожалуйста алгоритм.
16.08.2005 // 07:09 [ ссылка ]
klim
Вполне адекватным решением будет алгоритм Дейкстры [ ссылка ] Работает достаточно быстро. Он ищет кратчайший путь из заданной вершины во все остальные. Алгоритмом Беллмана-Форда пользоваться не стоит т.к. он медленней Дейкстры, но корректно работает в случае отрицательных весов ребер (очевидно, не данный случай).
Если граф меняется редко, то можно воспользоваться алгоритмом Джонсона [ ссылка ] если граф разреженный, что вполне вероятно, если эта задача имеет отношение к веб-программированию. Он ищет кратчайшие пути между всеми парами вершинам. Соответственно, логично запускать его при изменение структуры сайта и сохранять результаты.
Я бы пошел по второму пути.
17.08.2005 // 16:30 [ ссылка ]
Ответ от Автора
второй путь... давайте представим, что у меня будет, например, 50 000 нод. Совершенно не исключено, что будут ноды, которые связаны сразу со всеми нодами. В реальности же, эта цифра будет порядка 200–300 связен на каждую ноду.
Кол-во путей, которые надо будет хранить настолько велико — что мне как-то не очень хочется держать в СУБД столько кеша ;) Так что придётся по первому пути да, если никто ничего лушче не предложит.
17.08.2005 // 18:28 [ ссылка ]
klim
Алгоритм Д. работает примерно O(V^2*E), где V - число вершин, а E - число ребер
А Джонсон O(V^2*log V + VE).
В описанном случае получаем
Дейкстра : 50000^2*(50000*300/2) = 50000^3*150
Джонсон : 50000^2(log50000 + 300/2)
Как видно, быстрого решения данная задача не имеет, ни в каком случае
Чего-то существенно быстрого, чем Дейкстра не существует.
Поэтому я советую смотреть в сторону приближенных алгоритмов. Но в любом случае, быстрее чем O(E) они работать не будут. Хранить в кеше матрицу 50000х50000 -- тоже медленно. Поэтому единственный выход -- сочитать кеширование и поиск, что является весьме непростой и интересной задачей.
17.08.2005 // 18:52 [ ссылка ]
Сергей Петров
Я прошу прощения, но тут люди ерунду какую-то говорят.
Во-первых, граф у тебя невзвешенный. На кой черт нужны Дейсктры и Джонсоны - неясно.
Ты должен использовать простейший поиск в ширину. Алгоритм:
1. Берем вершину-источник
2. В конец очереди заносим всех ее соседей
3. Берем из начала очереди вершину
4. Проверяем - не та ли, что нам нужна. Если та - заканчиваем.
5. Заносим соседей в конец очереди.
6. Идем на третий шаг.
Производительность должна быть вполне нормальная. Памяти тоже сильно много не сожрет.
В общем-то, все зависит от связности графа. Какой будет самый далекий путь, если прикидывать? Если небольшой - все фигня. Если порядка тысяч - возникнут проблемы с хранением собственно пути.
25.08.2005 // 05:05 [ ссылка ]
Ответ от Автора
максимуму 5 шагов, правда нод могут быть сотни тысячь — предлагаете хранить все пути? просто интересует, как работает проект http://openbс.com/ — хочется сделать похожую шнягу для приватного сектора
26.08.2005 // 21:43 [ ссылка ]
Сергей Петров
Да, обычный рекурсивный поиск в ширину. Скорость с максимальным путем в 5 нод будет нормальная, а память... Что пямять.. Ее нынче много...
26.08.2005 // 23:31 [ ссылка ]
Ответ от Автора
сомневаюсь, у меня комп завис... в базе 10 000 нод, по 200 связей на ноду, это в 5-ом шаге получилось
200*100005 == смерть компа =)
27.08.2005 // 19:59 [ ссылка ]
Антон Скоробогатов
Вот ту кратенько про ген. алгоритм и задачу коммивояжера [ ссылка ]
Правда, многие математики считают ГА фикцией и профанацией.
28.08.2005 // 12:35 [ ссылка ]
Ответ от Автора
задача коммивояжера считается нерешаемой, за решение предлагаю много денег ;)
28.08.2005 // 14:47 [ ссылка ]
Антон Скоробогатов
А тут даже есть реализация на Java [ ссылка ]
28.08.2005 // 12:38 [ ссылка ]