Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 30.04.2010, 13:28
Новичок

Отправить личное сообщение для artem_k Посмотреть профиль Найти все сообщения от artem_k
 
Регистрация: 30.04.2010
Сообщений: 6

Многократный поиск кратчайшего пути в графе.
Помогите пожалуйста решить задачку (или подскажите, по какому запросу гуглить).
Дано: есть карта, хранимая в виде графа в SQL-таблицах. Вершины - регионы, ребра - дороги, соединяющие регионы (с указанием длины - веса).
Необходимо: найти кратчайший путь из точки А в точку Б.
Важное дополнение: задача поиска пути вызывается крайне часто (вплоть до нескольких раз в секунду в моменты пиковой нагрузки).
Важное дополнение №2: карта большая. Кол-во регионов - до нескольких тысяч (в перспективе до десятков тысяч).
Понятно, что тупо каждый раз вычислять кратчайший путь - безумное расточительство.
Идея №1 - заранее просчитать кратчайшие маршруты и хранить их в отдельной таблице. В принципе вполне нормальный вариант, но есть одно но: таблица получается очень большой - от нескольких миллионов до десятков миллионов записей и поиск в ней перестает быть тривиальной задачей, временем выполнения которой можно пренебречь.

Хотелось бы услышать другие идеи. Более чем уверен, что подобная задача уже была решена ранее.
  #2  
Старый 30.04.2010, 14:15
гость

 
Сообщений: n/a

Выкинуть SQL, использовать A*
  #3  
Старый 30.04.2010, 14:36
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>до десятков миллионов записей и поиск в ней перестает быть тривиальной задачей

Это почему?
  #4  
Старый 30.04.2010, 16:02
Новичок

Отправить личное сообщение для artem_k Посмотреть профиль Найти все сообщения от artem_k
 
Регистрация: 30.04.2010
Сообщений: 6

>Выкинуть SQL, использовать A*
Боюсь тут мы несколько ограничены в выборе средств. Да и в любом случае простой заменой метода хранения данных мы проблему не решим.

>>до десятков миллионов записей и поиск в ней перестает быть тривиальной задачей
>Это почему?
Даже при использовании индексов время выполнения банального SELECT недостаточно мало. Напоминаю, при пиковых нагрузках придется считать три-четыре раз в секунду, а поиск кратчайшего пути - только часть алгоритма.
  #5  
Старый 30.04.2010, 16:15
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Насколько насыщенный граф?
т.е. сколько ориентировочно ребер? (для планарного графа-сети дорог обычно V~E)

Последний раз редактировалось MBo, 30.04.2010 в 16:17.
  #6  
Старый 30.04.2010, 16:53
гость

 
Сообщений: n/a

Сообщение от artem_k Посмотреть сообщение
>Выкинуть SQL, использовать A*
Боюсь тут мы несколько ограничены в выборе средств.
Хотите чтобы было быстро - придется извернуться.

К черту SQL и базы данных. Берём старый добрый C++, загоняем весь граф в память и пишем A* или Дейкстру на этом графе. Для 10000 вершин, 30000 ребер (примерно предел для планарных графов, как заметил MBo), все это будет просто летать. Гарантирую QPS в несколько сотен, если даже не тысяч.

Если надо интегрировать C++ с вужул васиком, коболом, адын эс и прочей дрянью -- пожалуйста, делайте из C++ программы сетевой сервис, общайтесь с ним по RPC, сокетам, пайпам и т.п.
  #7  
Старый 30.04.2010, 17:40
Новичок

Отправить личное сообщение для artem_k Посмотреть профиль Найти все сообщения от artem_k
 
Регистрация: 30.04.2010
Сообщений: 6

Сообщение от MBo Посмотреть сообщение
Насколько насыщенный граф?
т.е. сколько ориентировочно ребер? (для планарного графа-сети дорог обычно V~E)
Из каждого региона выходит в среднем 3 - 4 дороги. Не менее 1 и не более 8. Забегая вперед уточню: между двумя любыми точками гарантированно существует маршрут.
  #8  
Старый 30.04.2010, 17:47
Новичок

Отправить личное сообщение для artem_k Посмотреть профиль Найти все сообщения от artem_k
 
Регистрация: 30.04.2010
Сообщений: 6

Сообщение от гость Посмотреть сообщение
Хотите чтобы было быстро - придется извернуться.
К черту SQL и базы данных. Берём старый добрый C++, загоняем весь граф в память и пишем A* или Дейкстру на этом графе. Для 10000 вершин, 30000 ребер (примерно предел для планарных графов, как заметил MBo), все это будет просто летать. Гарантирую QPS в несколько сотен, если даже не тысяч.
Почему в рунете принято вместо ответа на четко поставленный вопрос предлагать изменить условия задачи? Поиск кратчайшего пути - только малая часть всей задачи. В худшем случае мы можем просто отказаться от поиска точно минимального маршрута и обойтись "достаточно приемлимым маршрутом", который по длинне будет отличаться от оптимального на 15 - 20%. Если же придется отказаться от SQL то объем работ возрастет на порядок.
  #9  
Старый 30.04.2010, 18:00
гость

 
Сообщений: n/a

Сообщение от artem_k Посмотреть сообщение
Почему в рунете принято вместо ответа на четко поставленный вопрос предлагать изменить условия задачи?
А почему вы не рассказаеты нам всем о "большой картине"? Какое условие такие и ответы.

Цитата:
Если же придется отказаться от SQL то объем работ возрастет на порядок.
а с каких это пор на sql вообще можно было что-то серьезное нормально писать? Надо use the rights tools for the job. SQL для формулировки запросов в базам данных, ну простых триггеров максимум, компилируемые языки для time-critical участков кода.
  #10  
Старый 30.04.2010, 18:50
Новичок

Отправить личное сообщение для artem_k Посмотреть профиль Найти все сообщения от artem_k
 
Регистрация: 30.04.2010
Сообщений: 6

Сообщение от гость Посмотреть сообщение
А почему вы не рассказаеты нам всем о "большой картине"? Какое условие такие и ответы.
А что еще надо рассказать? Знаки зодиака всех участников проекта? Или т.з. изложенное на ~50 листах А4?
Сообщение от гость Посмотреть сообщение
а с каких это пор на sql вообще можно было что-то серьезное нормально писать? Надо use the rights tools for the job. SQL для формулировки запросов в базам данных, ну простых триггеров максимум, компилируемые языки для time-critical участков кода.
На SQL пишут обычно запросы для получения данных из СУБД коей на данный момент является Postgres. Все остальное - С++. Плюс PHP+HTML для вебморды контроля. Но речь ведь не об этом.
Изначальный вопрос звучал так: как сократить издержки при многократном поиске кратчайшего пути при том, что сам граф ни разу не меняется в процессе работы (точнее, он меняется, но настолько редко, что этим можно пренебречь).
Все ответы на текущий момент свелись к "отказаться от всех хитростей и тупо пересчитывать каждый раз". Ответ из разряда "1000 советов Капитана Очевидности" и, возможно, он нас устроит, а возможно - нет. Меня интересуют альтернативные варианты.

Последний раз редактировалось artem_k, 30.04.2010 в 18:57.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск мостов в графе Masha Реализация, исходники, языки 1 24.12.2009 20:34
Поиск самого длинного пути в ориентированном графе terlan Графы 11 26.11.2009 01:27
Поиск кратчайшего пути во взвешенном графе с заданным количеством вершин или ребер Mitrich Графы 9 24.07.2009 18:21
Поиск кратчайшего пути в бесконтурном графе гость Реализация, исходники, языки 1 06.06.2009 10:27
Поиск путей в графе MrFandorin Графы 5 24.04.2008 01:25