Поиск кратчайшего расстояния на графе дорог. Протестируйте

[Voltron]

А Voltron говорит, нужно перебирать все дороги, тогда будет честное соревнование по скорости с модулем RoadGraph.

Вот не надо только передергивать.
То, что говорилось относилось к одному частному случаю. А именно к вашему сравнению вашей программы, работающей только с автодорогами, и RoadGraph, который вы гоняли на всех дорогах.

Постороитель маршрута не обязан различать типы дорог. Может, но необязан. И если нужно построить маршрут по каким-то одним дорогам ­— быстрее и проще всего, отфильтровать нужные типы уже с ними работать.

[Pifagoroff]

А именно к вашему сравнению вашей программы, работающей только с автодорогами, и RoadGraph, который вы гоняли на всех дорогах.

Такое сравнение корректно, и вот почему. Я скачиваю слой дорог из интернета (из проекта Gis-Lab), загружаю своей программой в базу. Потом ставлю в программе на карте две точки, нажимаю на кнопочку, получаю через 15 секунд маршрут. Настоящий маршрут заметьте, по которому можно ехать. Сравниваем с RoadGraph. Скачиваю c Gis-Lab карту и проект для qgis. Загружаю в qgis, ставлю на карте две точки и через полчаса … получаю… но понятно, что получаю… Короче, не поймёт меня пользователь, ой не поймёт, если я ему предложу в RoadGraph маршруты строить… Хотя и не обязан построитель маршрутов различать типы дорог, вовсе и не обязан. Про свой навигатор Вы вряд ли так думаете…

[Voltron]

Такое сравнение корректно, и вот почему. Я скачиваю слой дорог из интернета (из проекта Gis-Lab), загружаю своей программой в базу. Потом ставлю в программе на карте две точки, нажимаю на кнопочку, получаю через 15 секунд маршрут.

Опять передергиваете. Цитата с вашего сайта

Первое, что нужно сделать – это загрузить слой дорог в базу. При этом будем загружать только полилинии имеющие следующие значения атрибута HIGHWAY:
Очень короткие дороги во дворах
service
Короткие дороги
Tertiary
tertiary_link
residential
unclassified
Протяжённые дороги
secondary
Магистрали, трассы, проспекты, шоссе
motorway
primary
trunk
Развязки
trunk_link
secondary_link
motorway_link
primary_link
Этим мы ограничиваем построение маршрута только по автомобильным дорогам.

Для RoadGraph фильтрация не выполнялась. Вы все еще утверждаете, что сравнение корректно? Извините, в таком случае продолжать разговор не вижу смысла.

[stopa85]

Возможно, я делаю, что-то не так. Загружаю проект для Москвы в qgis, полученный вот отсюда: http://gis-lab.info/projects/osm_shp/region . Пытаюсь построить с помощью модуля маршрут. У меня получился маршрут через Битцевский парк, по велодорожкам.

Загружаю в qgis, ставлю на карте две точки и через полчаса … получаю… но понятно, что получаю…

Во-первых, 99.99999% времени плагин тратит на то что бы из сырых данных сделать граф пригодный для анализа. Расчет кратчайшего маршрута я даже в прогресс-бар не добавлял. Он мгновенен, по сравнению с "из сырых данных..." . Всякого рода навигаторы в своих картах уже имеют эту выжимку, т.е. хранят два набора данных: один для отображения, другой для поиска пути. PgRouting тоже работает с "выжимкой". RoadGraph не работает (пока!) с выжимкой по политическим соображениям.
К этому недостатку можно еще добавить то, что Road Graph требует значительные объемы ОЗУ (особенно в QGIS 1.7, в 1.8 уже полегче будет). Я стараюсь балансировать на гране простоты реализации/возможностей плагина.

Во-вторых, плагин не производит фильтрацию дорог по их типу. Более того, многие "дороги" даже не отображаются на экране (по крайней мере в Тюменской области). Если Вам не нужны велодорожки - удалите их. Средства для этого в QGis'е есть.

В-третьих и самых главных.
Я вижу будущее моего плагина как универсального средства для анализа сети. Да, сейчас он выглядит как приблуда для прокладки маршрута, но в апстриме доступна питон-библиотека с базовыми возможностями, а в моих экспериментальных сборках плагин умеет искать кратчайший путь на растре: смотреть тут. (Сегодня пробовал на растре 1700х3500px. Отрабатывает секунд за 30)
Закончу с растрами, займусь классическими алгоритмами: задача коммивояжера, минимальное дерево Штайнера/Остовное дерево, анализ близости/доступности... но это все для людей, которые понимают с чем имеют дело и зачем оно вообще нужно. Для тех, кому "поставил две точки и вперед" есть Navintel по доступным ценам. Ей, народ, поддержите меня!

[ericsson]

Да уж поддержал, куда уж еще См. тезисы на прошлой странице.

[stopa85]

Видимо, маршрут по дорожкам наиболее короткий . Если не ошибаюсь, используется алгоритм Дейкстры.

Да, алгоритм Дейкстры. Все, что классифицирует типы дорог - тоже Дейкстры, только отношение сравнения другое.

Pifagoroff писал(а):А не знаете, сколько по времени должен работать модуль, если проект сохранить в базе PostGIS?

К сожалению, тестирования на разных источниках данных не проводил, хотя это интересная тема.

Столько же если не больше.

Да уж поддержал, куда уж еще См. тезисы на прошлой странице.

ericsson, я ждал от тебя что-то вроде "В баню эти навигаторы с их "через 50 метров поворот налево"!!! Давай, stopa85, сделай нам полноценный network-analysis в QGis!!!"

[Voltron]

Ей, народ, поддержите меня!

Куда донейты слать-то? Доку по обвязке я пилю потихоньку.

Давай, stopa85, сделай нам полноценный network-analysis в QGis!!!"

Как говорится, special for you #4312

[bim2010]

stopa85 абсолютно прав!
У меня алгоритм Дейкстры на готовом графе работает менее 1 секунды.
На матрице 1000x1000 узлов выполняется за 0,28 секунды. Пробовал и на больших массивах < 1 сек. Основное время тратится на загрузку из базы в массив.
И еще, практически всегда можно выделить из общего графа дорог ту часть, которая необходима для анализа и работы алгоритма Дейкстры, т.е. нет необходимости анализировать весь граф. С помощью индексирования избавляюсь в анализе от “неинформационных” узлов, т.е. например полилиния может содержать 50 узлов, а достаточно двух.
Pifagoroff разве можно при текущем состоянии информации в OSM (сырые данные) в принципе построить правильный транспортный граф?Я, например, внутри одного населенного пункта вижу несколько других(на самом деле это должны быть улицы). Посмотрите на Ваш район, где Вы живете и хорошо знаете дорожную обстановку. Для тестов, курсовой, дипломный …подойдет, не более.
stopa85 ждем продолжения Вашей замечательной работы. Полностью поддерживаю.
Просто есть такой способ освоения материала - провокация.
Хорошо было бы пообсуждать алгоритмы, которые Вы планируете реализовывать.

[SS_Rebelious]

Было бы неплохо добавить опцию, которая позволяла бы учитывать ещё одно или несколько полей для совместного анализа, то ечть чтобы можно было считать кратчайший путь с дополнительными условиями, например, кратчайший и самый безопасный путь.

Такой функционал востребован в работах по экологической безопасности. Я читал одну интересную канадскую работу, посвящённую транспортировке опасных грузов. Там припрокладке маршрута учитывалось не только расстояние между точками, но и плотность населения и вероятность ДТП. Причём плотность населения, если не ошибаюсь, была в виде растра.

В идеале, хотелось бы, чтобы плагин расчитывал самый быстрый/которкий маршрут с учётом нескольких дополнительных параметров, и даже с учётом значений из растровой подложки.

[bim2010]

Что бы еще можно было добавить в плагине? Например, поиск кратчайшего маршрута для сети городского транспорта. Как добраться из одной точки города в другую с минимальным количеством пересадок и за кратчайшее время / кр.путь.

[Александр Мурый]

Во-первых: в баню эти навигаторы с их "через 50 метров поворот налево"!!! Давай, stopa85, сделай нам полноценный network-analysis в QGIS!!

Во-вторых: поигрался с кратчайшим маршрутом в GRASS по дорогам Москвы.
Машина: Lenovo Ideapad V560 (Core i3, 2.53GHz, память 3Gb)
ОС: Ubuntu 10.04.03 LTS
GRASS 6.4.2svn49260.

Координаты начальных/конечных точек маршрутов А-А' и Б-Б' --- на картинке, дороги отфильтрованы как упоминалось выше в теме (только автомобильные), почищена топология, всего 144624 линий.
Время построения засекалось с помощью утилиты time.

Маршрут А-А':

Код: Выделить всё

time echo "1 37.134567 56.029486 37.945861 55.794829" | v.net.path in=moscow_roads_clean_filter out=moscow_roads_clean_filter_path1 --o

real   0m6.404s
user   0m6.048s
sys    0m0.340s

Маршрут Б-Б':

Код: Выделить всё

time echo "2 37.561133 55.471948 37.470181 56.024938" | v.net.path in=moscow_roads_clean_filter out=moscow_roads_clean_filter_path2 --o

real    0m6.410s
user    0m6.048s    
sys     0m0.332s

network_Moscow_path_1_2.png (639.14 КБ) 15111 просмотров

Не сочтите за оффтоп, просто для сравнения ПО

[Pifagoroff]

На матрице 1000x1000 узлов выполняется за 0,28 секунды.

Я счастлив! Только где-это вы видели матрицы 1000x1000? Можт 10 000 х 10 000 больше похоже на правду? или даже 100 000?

[Pifagoroff]

Во-первых: в баню эти навигаторы с их "через 50 метров поворот налево"!!! Давай, stopa85, сделай нам полноценный network-analysis в QGIS!!

Во-вторых: поигрался с кратчайшим маршрутом в GRASS по дорогам Москвы.
Машина: Lenovo Ideapad V560 (Core i3, 2.53GHz, память 3Gb)
ОС: Ubuntu 10.04.03 LTS
GRASS 6.4.2svn49260.

Координаты начальных/конечных точек маршрутов А-А' и Б-Б' --- на картинке, дороги отфильтрованы как упоминалось выше в теме (только автомобильные), почищена топология, всего 144624 линий.
Время построения засекалось с помощью утилиты time.

Маршрут А-А':

Код: Выделить всё

time echo "1 37.134567 56.029486 37.945861 55.794829" | v.net.path in=moscow_roads_clean_filter out=moscow_roads_clean_filter_path1 --o

real   0m6.404s
user   0m6.048s
sys    0m0.340s

Маршрут Б-Б':

Код: Выделить всё

time echo "2 37.561133 55.471948 37.470181 56.024938" | v.net.path in=moscow_roads_clean_filter out=moscow_roads_clean_filter_path2 --o

real    0m6.410s
user    0m6.048s    
sys     0m0.332s

network_Moscow_path_1_2.png

Не сочтите за оффтоп, просто для сравнения ПО

Вот это уже кое-что... И не так уж плохо для моей программки! Ей Богу не плохо!

[Александр Мурый]

Вот это уже кое-что... И не так уж плохо для моей программки! Ей Богу не плохо!

Прекрасно, надеюсь, вы уже подали заявку на премию Тьюринга?
И да, кстати, вы не хотите выпустить вашу программу под открытой лицензией?

[bim2010]

Я счастлив! Только где-это вы видели матрицы 1000x1000? Можт 10 000 х 10 000 больше похоже на правду? или даже 100 000?

На самом деле тестировал на трехмерной матрице 1000*1000*1000
На алгоритме Дейкстры транспортная задача не заканчивается.
Для организации, имеющей в справочнике потенциальных клиентов около 3000 организаций, необходимо было в течение 1 дня осуществить доставку менее 1000 клиентам.
stopa85 уже Вам писал, что реальный транспортный граф и набор данных для отображения это две больших разницы.
Так и сам транспортный граф по одним и тем же объектам не один.
В одном случае г. Москва = 1 узел
Во втором случае г. Москва = 64 узлов = зоны (кол-во зон определялось эмпирически)
В третьем случае г. Москва = кол-во перекрестков + кол-во точек доставки
И т.д. …
Переход с одного уровня на другой делаю с помощью индексов (хотя можно было и в отдельном слое).Поставив произвольно точки А и Б на карте через сколько узлов у Вас проходит маршрут?
Если у Вас их 1000 и более Вы неправильно строите транспортный граф, или скажем не оптимально.

Другой пример: осмеры нарисовали памятники Курган Бессмертия и самолет в виде полигонов, каждый из которых состоит из более 50 точек. А я считаю эти POI как два точечных объекта.