ТРАНСПОРТ в России
Список темНовая темаПоискПравилаВойти Темы: <<>>
Страницы: <<1 2 Все
Страница: 2 из 2
Re: Раскраска схемы линий :)
karelalex  07.05.2012 15:29

Для проверки наличия маршурта можно использовать вот такой примитивный (в общем-то) алгоритм. Вычислительная сложность его не больше, чем у простой сортировки.
1) Строим матрицу связывания.
2) Берём массив, соответствующий узлам, в котором помечаем элемент связанным с конечной точкой, начальной точкой или не определенным.
3) Одной и той же функцией идём с разных концов. Соответственно помечаем связанные узлы. А также вновь добавленные точки кладём в стек или очередь, чтобы потом с них продолжать поиск. Как только с одной из сторон мы встречаем точку, связанную с другим узлом, говорим "Да маршрут существует".
4) Если же очередь (стек) кончается с обеих сторон, говорим, что "Маршрута нет".
Всё на уровне школьных знаний.

Re: Раскраска схемы линий :)
Toman  07.05.2012 18:52

Цитата (karelalex)
3) Одной и той же функцией идём с разных концов. Соответственно помечаем связанные узлы. А также вновь добавленные точки кладём в стек или очередь, чтобы потом с них продолжать поиск. Как только с одной из сторон мы встречаем точку, связанную с другим узлом, говорим "Да маршрут существует".
4) Если же очередь (стек) кончается с обеих сторон, говорим, что "Маршрута нет".

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

Re: Раскраска схемы линий :)
karelalex  09.05.2012 01:55

Что-то я долго думал, хотя есть абсолютно очевидный алгоритм, который сможет дать точные данные по каждой линии:
1) Мысленно вычёркиваем линию из схемы
2) Ищем альтернативный маршрут между узлами вычеркнутой линии
2а) Если найден, то вычёркиваем его целиком, счётчик найденных маршрутов увеличиваем на один.
2б) Повторяем пункт 2а сколько нужно раз.
3) Как только маршрут оказывается не найден, присваиваем цвет исходной линии. Красный, если счётчик ноль, жёлтый - 1, зелёный - 2, синий - 3 и более.

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

Re: Раскраска схемы линий :)
Toman  09.05.2012 23:42

Цитата (karelalex)
2) Ищем альтернативный маршрут между узлами вычеркнутой линии
2а) Если найден, то вычёркиваем его целиком, счётчик найденных маршрутов увеличиваем на один.

Собственно, именно это же я и предложил в предыдущем посте. Но, видимо, всё не так просто, и рановато говорить, что это решение.

Цитата

Правда, в случае синей линии возможна ситуация, когда маршрут будет построен так, что она будет по ошибке принята за жёлтую, но это маловероятно.
А как это? Найденный "кратчайший" маршрут проходит так, что перерезает все остальные возможные маршруты (при том, что на их месте можно было бы проложить несколько полностью независимых)? "Маловероятно" в данном случае не годится, увы - это детерминированный дискретный алгоритм, в нём либо ошибка исключена (а это надо доказывать), либо сам алгоритм надо считать ошибочным. Я даже не могу сказать, что ситуация маловероятна - в развитой сети она как раз очень вероятна, и нетрудно специально сконструировать такую сеть, где ошибка такого рода будет происходить. И не только между синей и жёлтой, а на любом уровне в сторону понижения (не ниже жёлтого, конечно: если уж маршрут есть, он будет найден). А именно: рисуем первый обход исследуемой линии - тот, который станет кратчайшим и потому первым найденным и перекрытым. Потом рисуем два частичных обхода этой линии, с некоторым перекрытием в середине (по типу как ж.д. разъезд полупродольного типа), но оба насколько-то удлиняющих путь в том смысле, который используется алгоритмом - хоть по числу узлов, хоть в километрах, хоть ещё как (хотя достаточно и того, чтобы они были равны по длине, т.к. в этом случае выбор "главного" маршрута произойдёт по каким-то случайным и не имеющим отношения к делу факторам, и с большой вероятностью попадёт так, как нам надо для получения ошибки). Кусок схемы такого вида настолько тривиально выглядит, что игнорировать такое нельзя даже под предлогом маловероятности.

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

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

...Но всё это опять основано на предположениях, в которых я совершенно не уверен, по крайней мере, пока...

Re: Раскраска схемы линий :)
karelalex  10.05.2012 01:53

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

Вот в таком графе, если мы рассматриваем синюю линию, то несложно заметить, что разрыв её и розовых линий приведут к разрыву всего графа, однако кратчайший маршрут по графу в обход синей линии (голубые и розовые линии) проходит как раз через них. Для удобства я пометил "расстояния" до рассматриваемых узловых точек, от различных узлов графа. Т.о. хотя бы теоретически, но для синих линий возможно занижение их статуса до жёлтых при использовании ранее мною предложенного метода.
Цитата
И не только между синей и жёлтой, а на любом уровне в сторону понижения (не ниже жёлтого, конечно: если уж маршрут есть, он будет найден).
Про жёлтую я высказался ранее, а вот теперь я покажу, что для зелёной в любом случае такой ситуации не возникнет. Рассмотрим зелёную линию, а также любые 2 линии, который собственно и делают эту линию зелёной. Тогда граф можно изобразить вот в таком виде:

Большие области - это две половинки графа, связи в внутри которых нас не интересуют, главное, что эти половинки внутри себя полностью связаны, а между ними есть только 3 связи (зелёная и серые линии).
Будем доказывать утверждение от противного: пусть кратчайший маршрут в обход зелёный ветки проходит по обеим серым веткам. Без ограничения общности можно считать, что начальная точка находится в голубой половине, а конечная в оранжевой, тогда маршрут либо уходит в оранжевую область по одной из веток, затем возвращается по ней в эту же область и снова выходит из неё по другой, либо сначала выходит по одной, возвращается по другой и снова выходит по первой. В обоих случаях маршрут проходит дважды через одни граничные узлы первой серой линии, а следовательно никак не может быть кратчайшим. ЧТД.
В общем мне пока очевидно только то, что предложенный мной алгоритм с некой долей вероятности может ошибаться при определении статуса синей линии.

Re: Раскраска схемы линий :)
Toman  10.05.2012 05:59

Цитата (karelalex)
Большие области - это две половинки графа, связи в внутри которых нас не интересуют, главное, что эти половинки внутри себя полностью связаны, а между ними есть только 3 связи (зелёная и серые линии).

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

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

Вот непонятно, зачем ему так проходить, когда вполне достаточно мирно пройти по одной, после чего уже в оранжевой области "подрезать" второй?

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

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

Цитата
В обоих случаях маршрут проходит дважды через одни граничные узлы первой серой линии, а следовательно никак не может быть кратчайшим. ЧТД.
Нет, это не ЧТД. Просто в примере с синей линией можно было провести линию раздела между "голубой" и "оранжевой" областями так, что кратчайший маршрут запоганил все три независимых маршрута именно на этой линии раздела. Конечно, для того, чтобы один маршрут мог запоганить все независимые маршруты именно на одном и том же "узком месте", и при этом быть несамоповторяющимся, этих независимых маршрутов должно быть нечётное число. Но такое строгое оформление не обязательно - на самом деле, когда я писал предыдущий пост, я не имел в виду в первую очередь именно такой проход "зигзагом", с обязательным реверсом на одном из независимых маршрутов. Узких мест может быть несколько последовательно, с одной или несколькими перемычками между независимыми маршрутами. Достаточно кратчайшему маршруту даже без всякого реверса, в "правильном направлении", перебрать все независимые маршруты, чтобы заткнуть их все (а обход по перемычкам тоже станет невозможен, т.к. они тоже заткнуты, да и к узлам подход может быть разный). При этом на любом узком сечении, где две части сети соединяет ровно определяющее число линий, кратчайший маршрут честно использует только одну из них (или, в общем случае, удовлетворяет условию выше: в "правильном" направлении проходит на на один раз больше, чем в неправильном, итого использует нечётное количество ниток).

Вот фактически простейший вариант схемы-ловушки с зелёной линией:

Тонкие линии показывают возможные узкие места, по которым можно поделить сеть на две части ("голубая" и "оранжевая"), видно, что в любом из них кратчайший маршрут проходит, как и положено, только по одной нитке. Что, однако, не мешает ему уже к другому узкому месту перепрыгнуть на другую нитку, закрыв и её саму, и перемычку. После закрытия только розовых линий, даже обеих одновременно (если не трогать узлы при этом) альтернативный маршрут бы остался (через перемычку в противоположном направлении) - но при закрытии всего кратчайшего маршрута (как это предполагалось делать в обсуждаемом сейчас алгоритме) оставшиеся чёрные звенья уже не смыкаются. В результате ошибочно принимаем зелёную линию за жёлтую. Причём, как видно, схема настолько скромненькая и нехитрая (4 тройных узла, 4, допустим, конечных или узла-подсоединения тупиковых линий или какой-нибудь обходной петли, которая тут ничего не поменяет, 10 неразветвлённых участков линий, да и геометрия не какая-то особо вывернутая), что встречаться такой фрагмент в реальности может ну очень часто и непринуждённо, так что даже о малой вероятности/частоте таких ошибок я бы говорить не стал.

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

Re: Раскраска схемы линий :)
karelalex  10.05.2012 13:35

Нехорошо получилось, значит в общем случае метод последовательного вычёркивания маршрутов целиком не работает. Тогда вспомним, что мы имеем. В принципе мы можем легко определять красные, жёлтые линии, а также статус "более чем жёлтая". Впрочем, как уже выше было замечено, такое определение не требует даже собственно построения маршрута, достаточно проверки его существования. И ещё: метод затирания маршрута только в использованном направлении в случае синей линии тоже даст неправильный результат, т.к. средняя линия первыми двумя маршрутами будет использована в оба направления.
Таким образом видимо нужно делать того, чего не хотелось бы: искать все возможные маршруты и выделять из них максимум не имеющих общих участков. Что пока не очевидно как. Хотя есть ещё один способ методом тупого перебора:
1) разрываем интересующую нас линию, затем разрываем 2 другие: проверяем связанность.
2) Повторяем до тех пора, пока не обнаружим разрыв или не кончатся отрезки сети
3) Делаем выводы из результатов второго пункта.

Страницы: <<1 2 Все
Страница: 2 из 2
Список темНовая темаПоискПравилаВойти Темы: <<>>


©  "ТРАНСПОРТ В РОССИИ", 2003-.
©  Дизайн - интернет-ателье "Рузайн" (Rusign), 2003.
Rambler's Top100
AT.

[ Generated in 0.004 seconds ]