| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Теория графов и поиск оптимального пути |
| Автор: over 21.4.2009, 18:13 |
| Написан векторный редактор дорожного графа (т.е. есть возможность рисовать дорожные сети), а также задавать правила дорожного движения: односторонние дороги и запреты поворотов. Основная суть проблемы состоит в поиске оптимального пути на дорожном графе, с учетом вышеописанных правил. Для поиска кратчайшего пути пользуюсь библиотекой AGraph (метод Диекстра), но, к сожалению, в библиотеке нет возможности учитывать такие вещи как односторонняя дорога и запреты поворотов. После долгих мучений удалось обработать односторонние дороги. С запретами поворотов никак не получается справится. Вполне возможно, что выбранный за основу алгоритм (Диекстра) вообще нельзя заточить под выполнение поставленых задач. Возможно кто нибудь сталкивался с похожей проблемой, или может помочь с выбором алгоритма, в конце концов работают как то навигационные системы (Навител и пр.) |
| Автор: TrЭin3e 21.4.2009, 20:03 |
| Вы имеете в виду "запреты поворота" в том смысле, что нельзя, дойдя до вершины А по ребру АБ, пойти сразу в вершину Б? А как вообще вы поставили ограничения на односторонние дороги? ведь это по сути одно и тоже, только это ребро считается односторонним в определенный момент времени(когда по нему осуществляется проход), если я ничего не путаю |
| Автор: yeputons 21.4.2009, 21:25 | ||||
| я думаю, что под "запретами поворотов" подразумевается то, что, например, прийдя в вершину Б из вершины А идти сразу в вершину В. А если прийдем из вершины Г, то идти в В можно. моё предложение таково: разбейте каждую вершину на k вершин, где k - кол-во исходящих из неё дорог. Т.о. каждую новую вершину можно обозначить парой (i, j), где i - номер старой вершины (номер перекрестка), а j - номер дороги в этом перекрестке. Новые ребра генерим так: для каждого ребра из A в B, где A и B - старые вершины делаем новые рёбра из всех вершин (A, *) во все вершины (B, *). Как запрещать после этого поворот тоже понятно: если нам с дороги i вершины a нельзя поворачивать на дорогу j, то удаляем ребро (a, i)->(g[a][i], *), где g[a][i] - вершина, на которую ведет дорога i из вершины a. "односторонность" дорог реализуется очень просто: 1)в матрице смежности/списке ребер/списке соседей оставляете то и только то направление, в котором можно ехать. 2)везде в программе заменяете проверки вида:
на
p.s.Алгоритм называется алгоритмом Дейкстры (Dijkstra) |
| Автор: over 22.4.2009, 09:21 |
| Спасибо за советы, но разбивать вершины и пр. не хочется (я обдумывал эту возможность), в идеали хочется выдумать/найти алгоритм (не полный перебор) который отработает на текущем графе. Пример графа в прикрепленном файле. (красные стрелки это запреты поворотов, линия со стрелками - односторонняя дорога) |
| Автор: Earnest 22.4.2009, 09:43 |
| Можно и не разбивать вершины, а просто при "нехорошем" повороте так увеличивать вес пути, чтобы он зашкалил. Дийкстра будет работать, если нет ребер с отрицательными весами (т.е. каждое новое ребро в пути только увеличивает вес). И у тебя именно такой случай. Так что весь вопрос в правильной реализации весовой функции или функции релаксации. Не знаю что такое AGraph, но с помощью BGL (boost) можно было бы сделать, там гибкости достаточно. Одностороннее движение - это вообще элементарно - граф должен быть направленным; ребра по которым можно ехать в обе стороны просто удваиваются. |
| Автор: AVA12 22.4.2009, 12:14 | ||
Не годится. Если "нехороший" вес слишком велик, то после нескольких "нехороших" поворотов счетчик может переполниться, и запрещенный маршрут окажется вдруг "наилучшим". Если "нехороший" вес слишком мал, то на очень хитрозакрученном графе запрещенный маршрут может оказаться дешевле разрешенного. Если же легального пути вообще нет, то алгоритм вернет запрещенный путь. Плюс при поиске маршрута может потребоваться зайти на одну и ту же вершину несколько раз (например, чтобы повернуть на Х-образном перекрестке налево), на что алгоритм Дейкстры неспособен. А вот идея с разбиением вершин - то, что надо. |
| Автор: over 22.4.2009, 12:25 |
| С разбиением будет куча геммороя, осбенно на сложных перекрестках. Алгоритм я уже придумал, работать будет дольше чем дейкстра, но правильно и с учетом всех нужных правил. Как реализую - отпишусь получилось ли. |
| Автор: yeputons 22.4.2009, 19:28 |
| идея с "зашкаливанием" тоже хороша. давайте попробуем её доработать: 1)вспоминаем, где вообще будет это "зашкаливание" стоять в алгоритме Дейкстры. Правильно - в процедуре релаксации по всем ребрам, исходящим из вершины. 2)так давайте запоминать для каждой вершины, откуда в неё был самый короткий путь. и передавать эту "предыдущую" вершинку в процедуру релаксации 3)а процедура релаксации будет проверять "запретность" поворота при релаксации очередного ребра и не делать её, если нельзя. Говоря проще: вместо записывания весом перехода очень большого числа, просто не будем этот переход делать. |
| Автор: Earnest 22.4.2009, 19:42 | ||
Кто заставляет оставаться в рамках простой арифметики? Я имела ввиду после неправильного поворота установить вес пути равным какому-то спецциальному значению. В терминах объектов, а не просто чисел. Можно реализовать так, что это спец. значение при любых сравнениях буть бОльшим; если вес уже равен этому значению, то к нему уже ничего не прибавляется; при возврате пути с таким весом ясно, что пути нет. |
| Автор: yeputons 23.4.2009, 16:17 |
| Такое значение есть ((1 << 31) - 1). |
| Автор: over 23.4.2009, 17:42 |
| Все что связано с немного модифицированной дейкстрой не прокатит (можете поверить). С ней только на первый взгляд кажется все просто но после копания глубже ничего путного не получается, перебрали кучу всяких способов и методов, и всегда где нибудб выдается не корректный результат. Задачу получилось решить сильно модифицированным полным перебором. Теперь осталось последнее, и пожалуй самое сложное, в плане реализации - добавить возможность разворачиваться в разрешенных местах. |
| Автор: yeputons 23.4.2009, 19:32 |
| over Чисто из спортивного интереса попробую и напишу. Жди код.  ) |
| Автор: maxdiver 23.4.2009, 23:40 |
| Запрет поворота - когда, приходя в вершину по какому-то ребру, выходить должны тоже по строго определённому? И что тогда за модифицированная Дейкстра? Имхо такая "модификация" невозможна в принципе - ведь состоянием теперь уже будет не только вершина, в которой мы стоим, но и ребро, по которому мы пришли. |
| Автор: Sefko 24.4.2009, 10:43 | ||
А что есть вершина или ребро графа? Ведь это просто некая абстракция, которой как-то соответствует какая-то реальность. Никакой алгоритм ничего не знает об этом соответсвии, знать не может и не должен. Разработчик волен иметь в виду любое соответствие. Если он придумал как-то неправильно (например, противоречиво), то это проблема не алгоритма, а разработчика. Это его - разработчика - проблема, так придумать соответствие, чтобы в абстракции были отражены существенные для работы алгоритма детали реальности. Мне кажется, что вся проблема выросла из того, что установленно "естественное" соответствие: вершина графа <==> перекресток. Представляется разумным для данной конкретной задачи мыслить вершину графа именно как некий прямолинейный участок пути, внутри которого невозможны никакие повороты/развороты. Тогда ребра графа будут соответсвовать разрешенным изменениям направления движения. При таком подходе, в частности, можно задавать разный вес правому и левому повороту, прохождению перекрестка по главной и второстепенной дорогам, etc.. Если на участке между двумя перекрестками развороты невозможны, то вершиной графа можно считать одну сторону движения. Очень удобно: участкам с односторним движениям будет соответсвовать только одна вершина. Если развороты возможны, то одной стороне движения соответствует две вершины. И т.д., и т.п. Надеюсь - идея понятна. |
| Автор: maxdiver 24.4.2009, 10:52 |
| Не, для начала, я не понял точной формулировки задачи. Если на некоторых перекрёстках вообще нельзя поворачивать - тогда это эквивалентно тому, что этого перекрёстка просто нет? Удалим эту вершину, а вместо этого просто пообъединяем рёбра, соответствующие "одной дороге без поворотов". Потому что какой смысл в вершине - месте пересечения нескольких дорог, если мы фактически запрещаем переходить в этом месте с одной дороги на другую. На оставшемся графе уже будет обычная задача для Дейкстры... |
| Автор: over 24.4.2009, 12:11 |
| Задачу решал исходя из того, что бы не менять и не подстраивать существующий граф под алгоритм, поэтому разбиение, удаление и т.п. делать не хотелось. Тем не менее задачу уже решил. Большинство предложенных вами алгоритмов я пробовал и ранее, и ни один из них не смог корректно справится со всеми тестами на сильно извращенном графе. В любом случае с удовольствием гляну на чужую реализацию (вполне возможно я реализовал ее не оптимально). P.S. Если перед кем нибудь стала похожая задача, пишите в icq (494107927), помогу с алгоритмом. |
| Автор: yeputons 24.4.2009, 18:02 | ||
имеется ввиду, что на каком-то перекрестке нельзя поворачивать, например, направо с одной и только одной дороги. см. пост выше:
|
| Автор: over 25.4.2009, 09:18 |
| yeputons, все именно так |
