"Умные" алгоритмы маршрутизации

Nicolai · 2010-03-17T09:45:07.000Z

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

Ezhick · 2010-03-17T09:46:16.000Z

Есть ПокетГИС, который использует статистику о пробках при построении маршрута. Но информация об алгоритмах закрыта. Кое-что можно почерпнуть на офсайте, но очень немного.

Nicolai · 2010-03-17T11:42:33.000Z

Ну я узнать ноу-хау и не рассчитываю. Меня интересуют общие подходы и модели. А работающие приложения - больше в плане функционала.

Vovanium · 2010-03-17T12:52:32.000Z

Несколько неспецифично, но можно посмотреть в сторону нейронных сетей. Скажем, к примеру каждому ребру графа прилагается перцептрон, который получает на входы информацию вроде дня недели, времени, (пред/пост)праздничности и выдаёт вес ребра (или, скорее его «привлекательность», величину, обратную весу), а обучается на основе статистики несоответствий проложенного и выбранного маршрута.

dimuzz · 2010-03-18T05:53:43.000Z

Вот подход с БД скоростей на ребрах графа, правда, без подробностей: http://www.tomtom.com/whytomtom/subject.php?subject=12