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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #11  
Старый 30.04.2010, 19:10
гость

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

Сообщение от artem_k Посмотреть сообщение
Все ответы на текущий момент свелись к "отказаться от всех хитростей и тупо пересчитывать каждый раз"
я предложил тебе написать на C++ бэк-энд, который постоянно будет держать граф в памяти и по сети отвечать на запросы о кратчайших путях в нем. За счет того что данные уже есть в памяти, их не надо каждый раз грузить черти откуда, и они постоянно "подогреты" в кеше, а расходы на поиск пути практически линейные по размеру данных, ты получишь нехилое ускорение. Но это неасимптотическая оптимизация алгоритма.

А так, алгоритмически, да. Без "пересчитывания каждый раз" пожалуй не обойтись. A* должен помочь сильно сократить объем пересчитывания по сравнению с Дейкстрой.
  #12  
Старый 01.05.2010, 20:10
Новичок

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

Храни ответы только на самые популярные запросы. остальное пересчитуй.
  #13  
Старый 10.05.2010, 13:39
Новичок

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

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


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск мостов в графе 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