Comments 11
Дорожные сети вроде как не просто «графы с особыми свойствами», а «планарные графы» (т.е. графы, которые можно изобразить на плоскости без самопересечения ребер). Известный класс графов, исследованию которых посвящено много публикаций и времени. И алгоритмов, которые используют ограничения, накладываемые планарностью графов достаточно много.
Примеры хорошие, немного смущает «плавание» в терминологии. Отдельное спасибо за ссылку с файлами реально существующих дорожных сетей.
Если кому интересно — подборка алгоритмов для планарных графов
Примеры хорошие, немного смущает «плавание» в терминологии. Отдельное спасибо за ссылку с файлами реально существующих дорожных сетей.
Если кому интересно — подборка алгоритмов для планарных графов
Да, дорожные графы планарные, некоторые почти планарные, но это свойство тут не используется. В том смысле, что приведенные алгоритмы не требуют от графов планарности. В частности, алгоритм поиска радиуса так же хорошо отрабатывает на полном графе (полная матрица МКР соответствует полному графу), который для такого количества вершин не может быть планарным.
А вы не рассматривали алгоритмы с многоуровневыми вспомогательными графами на подобие МКР? Если вам это любопытно, могу найти ссылки на статьи и, возможно, слайды (на английском, правда). Интересная деталь, которая мне вспоминается про эту область (я по работе с ней дела не имею, ознакомился поверхностно на досуге) — определённое свойство «фрактальности» графа дорожной сети там определяется формально, и для типичных графов континентального масштаба оно действительно выполняется (в одной из статей есть даже рассуждения на тему, что так получается из-за исторически инкрементального развития сети дорог). Оно, правда, не выполняется, например, на регулярных сетках типа расчерченного строго перпендикулярными улицами района города.
Практический аспект — континентальные дорожные сети очень велики и алгоритмы линейной сложности по размеру графа не удовлетворяют практическим требованиям, нужны алгоритмы суб-линейные по сложности (которые как раз существуют для пред-обработанных графов с пред-вычисленной дополнительной информацией, аналогичной многоуровневым МКР). О, кстати, бегло пробежавшись по ссылкам, увидел знакомую фамилию по последней ссылке — Голдберг, я был как раз на его презентации однажды (на которой он излагал теорию и практику этого подхода).
Практический аспект — континентальные дорожные сети очень велики и алгоритмы линейной сложности по размеру графа не удовлетворяют практическим требованиям, нужны алгоритмы суб-линейные по сложности (которые как раз существуют для пред-обработанных графов с пред-вычисленной дополнительной информацией, аналогичной многоуровневым МКР). О, кстати, бегло пробежавшись по ссылкам, увидел знакомую фамилию по последней ссылке — Голдберг, я был как раз на его презентации однажды (на которой он излагал теорию и практику этого подхода).
Многоуровневый подход требуется, например, когда МКР для всего графа не помещается в памяти (или в достаточно быстрой памяти). Тут есть разные подходы, но это — несколько другая задача.
В данном случае предполагается, что МКР хранится в памяти целиком, значит размер графа ограничен. Для этого в статьях из исходных графов-примеров приходилось вырезать «куски» определенного размера (без всяких хитростей, просто по смежным узлам).
Действительно, дорожные сети бывают и «фрактальные», и нет (мы больше сталкиваемся с последними), но фрактальность, как и планарность, не обязательные условия для алгоритмов.
Вообще, соответствие графа дорожной сети — условие достаточное для эффективной работы алгоритмов, но не необходимое. Алгоритмы могут успешно работать и на тех сетях, которые физически невозможны. Например, можно взять несколько дорожных сетей и «сшить» их ребрами, но не «с краев», а случайно (в небольшом числе мест, чтобы не нарушить разреженности). Получится не планарная, «многослойная», физически невозможная дорожная сеть, но алгоритмы на ней будут так же эффективны.
В данном случае предполагается, что МКР хранится в памяти целиком, значит размер графа ограничен. Для этого в статьях из исходных графов-примеров приходилось вырезать «куски» определенного размера (без всяких хитростей, просто по смежным узлам).
Действительно, дорожные сети бывают и «фрактальные», и нет (мы больше сталкиваемся с последними), но фрактальность, как и планарность, не обязательные условия для алгоритмов.
Вообще, соответствие графа дорожной сети — условие достаточное для эффективной работы алгоритмов, но не необходимое. Алгоритмы могут успешно работать и на тех сетях, которые физически невозможны. Например, можно взять несколько дорожных сетей и «сшить» их ребрами, но не «с краев», а случайно (в небольшом числе мест, чтобы не нарушить разреженности). Получится не планарная, «многослойная», физически невозможная дорожная сеть, но алгоритмы на ней будут так же эффективны.
Да, согласен, задача несколько другая, но смежная — я всё-таки подумываю о пересказе того, что просматривал на досуге; темы переплетаются (и, как показывает беглый поиск, здесь на Хабре заинтересовавшие меня вопросы пока не обсуждались). Один из интересных пунктов — формальное определение оного свойства «фрактальности», при соблюдении которого для большой карты увеличение размера памяти для хранения МКР-информации всей карты — фиксированный множитель. Не буду вдаваться в детали, потому что могу легко что-нибудь напутать из памяти — надо сесть, вдумчиво пересмотреть статьи / презентации. Если таки-доведу идею написать запись по теме до успешного воплощения, помещу здесь ссылку.
Что касается поиска поиска МКР, алгоритм легко уничтожает вершины в графе К5, так же легко в графе К3,3, если там добавлено пара ребер, которые не переводят этот граф в планарный.
Терминологию использовал «попроще», чтобы было понятнее. В статьях она правильная.
Терминологию использовал «попроще», чтобы было понятнее. В статьях она правильная.
Для универсального и правильного моделирования вершинами графов являются не только населенные пункты, но и каждая развилка, а ребрам графа соответствуют сегменты дорог без внутренних развилок. В противном случае вы не сможете описать ситуацию, когда на трассе, соединяющей города А и B есть развилка, от которой отходит дорога в деревню C. Чтобы это описать на языке графов, нужно ввести вершины графа A, B, C, так же добавить вершину D, соответствующую развилке, и будет у графа 3 ребра: AD, BD и CD.
Кстати, считать граф неориентированным — большой риск, т.к. одно и то же шоссе может иметь в разные стороны разную пропускную способность, особенно во время ремонтных работ (которые могут длиться месяцами), специфических погодных условий, заторов, вызванных календарными событиями или социальными факторами и т.д.
UPD: дополнительную «ориентированность» ребрам графа может придавать рельеф, из-за которого поездка по одному и тому же участку шоссе в разных направлениях требует разного времени и разных затрат горючего.
Кстати, считать граф неориентированным — большой риск, т.к. одно и то же шоссе может иметь в разные стороны разную пропускную способность, особенно во время ремонтных работ (которые могут длиться месяцами), специфических погодных условий, заторов, вызванных календарными событиями или социальными факторами и т.д.
UPD: дополнительную «ориентированность» ребрам графа может придавать рельеф, из-за которого поездка по одному и тому же участку шоссе в разных направлениях требует разного времени и разных затрат горючего.
То, что перекрестки входят в вершины графа, упоминается несколько раз, начиная с в первого абзаца.
Что значит «большой риск»? Риск совершить ошибку? Иногда он не такой «большой», по сравнению с риском вообще не решить задачу.
Что значит «большой риск»? Риск совершить ошибку? Иногда он не такой «большой», по сравнению с риском вообще не решить задачу.
Лично мне не хватило визуализации сказанного
Sign up to leave a comment.
Графы дорожных сетей и алгоритмы работы с ними