ТРАНСПОРТ в России
Список темНовая темаПоискПравилаВойти Темы: <<>>
Страницы:  1 2Все>>
Страница: 1 из 2
Раскраска схемы линий :)
Toman  07.04.2011 10:00

Вот взял я и попробовал раскрасить схему трамвайных линий Москвы:


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

Re: Раскраска схемы линий :)
karelalex  07.04.2011 21:21

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

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

Цитата (karelalex)
Непонятно только с голубой линией. А так: жёлтые линии имеют возможность альтернативного проезда только с одной стороны, зелёные с двух (справа и слева), а красные - безальтернативны.

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

Т.е. похоже, да, эта закономерность по наличию обходов справа и слева - действительно случайное совпадение.

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

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

Т.е. грубо говоря, вводится некий целочисленный параметр. Минимальное количество единичных разрывов линий, в сочетании (но только в сочетании, а не сами по себе) с разрывом данной линии вызывающих разрыв всей сети в целом.
0 - красный, 1 - жёлтый, 2 - зелёный, и >2 - синий. Но вот в правильности окраски синего кусочка в московской схеме я не уверен, т.к. проверять вручную как-то трудновато, по крайней мере, пока процесс подсчёта этого параметра не алгоритмизирован каким-то удобным способом.

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

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

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

Re: Раскраска схемы линий :)
karelalex  08.04.2011 00:33

Теорема: Аффтар ошибся: синяя линия на самом деле зелёная.

Доказательство: разорвем сеть по следующим точкам: МЭИ, Преображенское кладбище, Москва товарная курская.
Проверяем условия: сеть разорвана - да, рассматриваемый кусок в разрыве участвует - да, удаление разрыва на рассматриваемом участке восстановит сеть в единую - да, число прочих разрывов соответствует критерию синий линии - нет, зелёной - да.

Ура, товарищи, синих линий в Москве нет.



Редактировано 1 раз(а). Последний раз 08.04.11 00:52 пользователем karelalex.

Re: Раскраска схемы линий :)
Toman  08.04.2011 04:01

Цитата (karelalex)
Теорема: Аффтар ошибся: синяя линия на самом деле зелёная.

Ура, товарищи, синих линий в Москве нет.

Большое спасибо! Я так и думал, что в таком в общем-то небогатом "огрызке" как Москва не получится четверного дублирования, впрочем, на момент рисования правила и не были сформулированы, рисовалось всё немножко по другому принципу, а конкретно осмысленные правила появились только вот в момент написания предыдущего поста. Да, значит, теперь, по правилам, будет зелёной.

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

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

Re: Раскраска схемы линий :)
Geoalex  08.04.2011 08:54

Цитата (Toman)
Но было бы интересно получить формальное описание

Формально красные линии принято называть дендритами, жёлтые - границой остова, зелёные - границами циклов.

Re: Раскраска схемы линий :)
Yaroslav  08.04.2011 12:50

Цитата (Geoalex)
Формально красные линии принято называть дендритами, жёлтые - границой остова, зелёные - границами циклов.
Автор терминологии - основоположник эволюционной морфологии транспортных сетей С.А. Тархов.

Re: Раскраска схемы линий :)
Toman  08.04.2011 13:47

Цитата (Geoalex)
Цитата (Toman)
Но было бы интересно получить формальное описание

Формально красные линии принято называть дендритами, жёлтые - границой остова, зелёные - границами циклов.

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

И, наоборот, некоторые из жёлтых линий по внешнему контуру могли бы стать зелёными, если бы к ним не были подсоединены тупиковые ветки. Они от этого перестали бы считаться границей остова, и стали "границами циклов"? Всё-таки, мне кажется, это немножко другого плана терминология.

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

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

Так и надо рисовать депо и линию по Стромынке жёлтым! Ведь с точки зрения декларированной задачи показа надёжности - как раз таки Стромынка должна быть жёлтой, т.к. двумя разрывами (с разных сторон от выезда с Матросской Тишины) от сети отсекается целое депо.

Re: Раскраска схемы линий :)
karelalex  08.04.2011 23:49

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

Re: Раскраска схемы линий :)
Toman  09.04.2011 13:43

Цитата (Алексей Черников)
Так и надо рисовать депо и линию по Стромынке жёлтым! Ведь с точки зрения декларированной задачи показа надёжности - как раз таки Стромынка должна быть жёлтой, т.к. двумя разрывами (с разных сторон от выезда с Матросской Тишины) от сети отсекается целое депо.

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

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

Re: Раскраска схемы линий :)
Toman  03.05.2012 17:54

Цитата (karelalex)
Касательно алгоритма начало его мне представляется таким:
1) Находим узлы и линии.

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

Цитата
2) Находим красные линии, ибо они очевидны.

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

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

В принципе, можно (и даже нужно, пожалуй) сформулировать в виде единственного цикла:
найти линию, у которой хотя бы в одном из концов(узлов) число других линий с ненулевым рейтингом (неопределённый считается также ненулевым!) равно нулю, присвоить ей рейтинг=0, повторять до тех пор, пока такие линии не перестанут находиться.

После выполнения этой стадии можно считать, что все линии, которые пока помечены "неопределённым" рейтингом, имеют рейтинг>0.
Цитата
3) Мысленно стираем красные линии, ну и заодно узлы, к которым подходят только красные линии.
4) Смотрим, что осталось. Если из какого-то узла выходит только 2 линии, смело присваиваем желтый цвет. Это легко доказать, ибо разрыв обеих линий приведет к отрыву узла от остальной сети, а разрыв любой из линий не приведет к этому, иначе одни были бы красными.
Более коротко и близко к уже программной реализации формулируем то же самое так: находим линии, у которых хотя бы в одном конце число других линий с ненулевым рейтингом равно 1, и присваиваем этим линиям рейтинг=1 ("жёлтые"). Это то же самое, просто в другой формулировке. То, что этим линиям надо присвоить рейтинг=1, понятно. Но есть проблема, что таким образом мы не исчерпаем все "жёлтые" линии, т.е. в общем случае останутся ещё, как мне кажется. И с этим надо что-то делать, если мы хотим продолжать работать путём последовательного исчерпывания линий с рейтингом=1, потом 2, 3 и т.д.

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

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

Цитата (Toman)
После выполнения этой стадии можно считать, что все линии, которые пока помечены "неопределённым" рейтингом, имеют рейтинг>0.
И в этот момент совершаем историческую ошибку. Главный недостаток предложенного алгоритма заключается в том, что он работает от тупиков, однако красные линии могут находится и между узлами, к которым никакие тупиковые ветки и не подходят.
Посмотрим на карту Москвы, линию от площади Борьбы до Красносельской указанный алгоритм красной не посчитает. (Т.к. для присваивания красноты требуется, чтобы один из концов линии был тупиком или становился таким после мысленного стирания всех красных линий, с указанной линией это, очевидно, не произойдет).
Так что похоже, что рассматривая только локальные свойства линий, что Вы делаете в своих рассуждениях здесь и далее, рейтинг линии можно оценить только сверху т.е. если наш алгоритм показал, что линия жёлтая, то она никак не может быть зелёной.
Цитата (Toman)
Но есть проблема, что таким образом мы не исчерпаем все "жёлтые" линии, т.е. в общем случае останутся ещё, как мне кажется.
Разумеется. Однако в Москве, похоже, таких случаев нету. Но его не сложно представить: уберём мысленно линию на 16-парковую от Семёновской. От этого линия Семёновская - Преображенская площадь не станет зелёной, однако указанному критерию удовлетворять перестанет.
Цитата (Toman)
...Ещё один факт, который как-то выпал из виду, когда доказывалось отсутствие "синих" линий в Москве, но теперь представляется очевидным: линия просто никак не может иметь рейтинг>2 (условие для "синей" линии), если оба её конца не являются узлами четверными или имеющими большее число сходящихся линий.
Ну да, это же очевидно: если к узлу примыкает эн линий, то, чтобы оторвать узел от сети, достаточно не более эн разрывов. Следовательно примыкающие к узлу линии не могут иметь рейтинг больший, чем тот, что соответствует эн разрывам.
Пока больше ничего не придумывается.



Редактировано 3 раз(а). Последний раз 06.05.12 13:56 пользователем karelalex.

Re: Раскраска схемы линий :)
Toman  06.05.2012 21:50

Цитата (karelalex)
И в этот момент совершаем историческую ошибку. Главный недостаток предложенного алгоритма заключается в том, что он работает от тупиков, однако красные линии могут находится и между узлами, к которым никакие тупиковые ветки и не подходят.

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

Цитата
Так что похоже, что рассматривая только локальные свойства линий, что Вы делаете в своих рассуждениях здесь и далее, рейтинг линии можно оценить только сверху т.е. если наш алгоритм показал, что линия жёлтая, то она никак не может быть зелёной.
Значит, придётся использовать те же самые уже найденные неповторяющиеся (сами поверх себя, т.е. не закольцованные) маршруты. В простейшем (но вычислительно тяжёлом) случае можно искать все такие маршруты. Далее ищем наиболее популярную линию (или несколько таковых, при равной популярности), и смотрим, входит ли она во все маршруты без исключения. Если да - то линия жёлтая. Если нет - пробуем все попарные сочетания линий, чтобы вырубить все обходы, далее тройные и т.д.

Но если сеть большая, то все маршруты заранее проложить и потом анализировать физически невозможно. Отчасти тут пригодится то самое локальное верхнее ограничение: как только оно достигнуто, дальше прибавлять маршруты уже нет смысла. Но вот что делать с теми случаями, когда оно не будет достигнуто никогда? Значит, надо делать ограничение не только строго локальное по концам самой линии, но и по каким-то более далёким "границам", скорее всего, целенаправленно выбранным.

Re: Раскраска схемы линий :)
karelalex  06.05.2012 23:22

Цитата (Toman)
Для проверки остальных линий можно попробовать метод поиска неповторяющихся маршрутов, соединяющих концы линии, кроме собственно самой этой линии. Если такой маршрут не находится, линия красная и исключается.
Вот ещё мысли:
Пусть мы умеем строить маршруты от точки к точке или находить, что такого маршрута нет, как, это можно обсудить потом.
Строго я сейчас этого доказать не могу, но на интуитивном уровне мне кажется, что стирание любой красной линии не влияет на цвет остальных, если мы не трогаем узлы (за исключение узлов, к которым подходят только красные линии, их можно тоже смело удалять).
Алгоритм строим так:
1) Присваиваем красный цвет всем тупиковым линиям
2) Удаляем их
3) Повторяем до тех пор, пока они не перестанут находится.
4) Проводим проверку на красноту всех линий, методом построения альтернативного маршрута. Если он есть, помечаем линию как некрасную, чтобы потом не рассматривать. При нахождении стираем линию и возвращаемся к первому пункту. (Это для экономии вычислительного ресурса).
5) То, что осталось считаем как минимум жёлтым.
6) Линии, выходящие из двойных узлов считаем жёлтыми сразу.
7) Проверку на желтизну остальных линий делаем следующим образом: мысленно удаляем проверяемую линию и на оставшейся сети ищем красные линии. Если они появились, значит проверяемая линия жёлтая, и те самые теперь уже красные тоже жёлтые.
8) Остальные линии, очевидно, оказываются как минимум зелёными.
Как отличать зелёную от синей только методом проверки существования маршрута - пока не очень понятно.



Редактировано 1 раз(а). Последний раз 06.05.12 23:25 пользователем karelalex.

Re: Раскраска схемы линий :)
ailcat  07.05.2012 01:00

Обычная "теория графов" вам в помощь.

Только рассматривать надо не тупики, а все возможные варианты проезда "от узла до узла".
Ну а метод рейтингования - получается простым: он равен числу альтернативных маршрутов (т.е. красный - это 1, желтый - 2 и т.п.).
Кстати, в сети есть не только голубые, но и белые участки (в схеме есть кусочек с числом альтернативных маршрутов = 5, хотя, конечно, объезд маршрутом на порядок длиннее основного - это из области фантастики. Но возможность-то есть!)

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

Цитата (ailcat)
Обычная "теория графов" вам в помощь.
Это понятно, но для конкретной задачи вся теория явно не нужна, в главное: у нас её преподавали почему-то только параллельной группе.
Цитата
Только рассматривать надо не тупики, а все возможные варианты проезда "от узла до узла".
А Вам не кажется, что это метод потребует заметно больше вычислительных ресурсов?
Цитата
Ну а метод рейтингования - получается простым: он равен числу альтернативных маршрутов (т.е. красный - это 1, желтый - 2 и т.п.).
Тут есть один момент: число маршрутов в объезд напрямую не связано с предложенным тов. Томаном рейтингом. Так, например, от Семёновской до Преображенской площади можно доехать (кроме прямого) ещё минимум 4-мя способами, однако прямая линия между ними желтая.
Цитата
Кстати, в сети есть не только голубые, но и белые участки (в схеме есть кусочек с числом альтернативных маршрутов = 5, хотя, конечно, объезд маршрутом на порядок длиннее основного - это из области фантастики. Но возможность-то есть!)
Вы заменили исходное условие задачи, да в вашей задаче цветов сильно больше, но они отвечают совсем другому критерию. И это даже понятно почему: критерий тов. Томана отвечает не общему количеству альтернативных маршрутов, а количеству альтернативных маршрутов, не имеющих общих участков.

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

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

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

Re: Раскраска схемы линий :)
karelalex  07.05.2012 02:09

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

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

Цитата (karelalex)
А теперь уберём линию на Краснобогатырской, ни одна не поменяет цвет. Вот поэтому у меня и случился затык в придумывании дальнейшего алгоритма.
Если сравнивать с состоянием, когда убраны не только красные линии, но и узлы, где они присоединяются, всё бы поменяло как надо. Теоретически, можно и так считать - вначале убрать красные вместе с узлами, посчитать только для замкнутых остовов сети, а потом вернуть красные вместе с узлами, и перекрасить что положено в жёлтый. Но, пожалуй, это всё - слишком сильное усложнение. В т.ч. по выч. ресурсам - поскольку схема сети по ходу дела меняется, и кэшировать маршруты между разными этапами уже не получится.
Тем более, что на практике же алгоритм поиска маршрута не ищет только один маршрут, он всё равно так или иначе найдёт несколько маршрутов (возможно, даже все), т.е. уже будет сделана бОльшая работа, чем бинарная информация о существовании или несуществовании маршрута, т.е. мы уже сразу имеем какую-то кучку маршрутов, и можем сразу найти среди них не имеющие общих участков, если таковые есть.

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

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

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


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

[ Generated in 0.007 seconds ]