.question | Shortest Path Problem

Пытаюсь наверстать все лекции по «конкретной математике», что когда-то сознательно были прогуляны на первом курсе в универе, а потому интересуют популярные решения одной, довольно банальной проблемы, завязанной вокруг теории графов.

Предположим, что есть у меня таблица с нодами, что-то из серии CREATE TABLE nodes(id INT4, name VARCHAR(255)), далее есть вторая таблица, в которой сохранены все «отношения» между любой пары нод, например: CREATE TABLE paths(parent INT4, child INT4).

[image]

Задача такова – найти самый короткий путь между любыми двумя нодами (например, между нодами 1 и 3 на рисунке). Какие есть алгоритмы, кроме тех, что описаны в википедии? Да и вообще, есть ли они?

Top

Слова: coding, internet, databases

Комментарии Отключены

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 [ ссылка ]