Диссертация (792664), страница 8
Текст из файла (страница 8)
На схемах представлен наиболее полный набор указателей. Прирасположении нескольких указателей на одном и том же главном илистанционном пути последовательность их заполнения строго определенавозможностью достижения их составом, а при освобождении учитываетсявозможностьпродолжениябеспрепятственногодвижениявзаданномнаправлении. Последовательность заполнения и освобождения указателей,находящихся на разных станционных путях может варьироваться.Стрелками обозначено правильное направление движения поездов поглавнымпутям–пошерстное[141].Требуетсвоегорешениязадачаавтоматического определения последовательности заполнения и освобожденияуказателей ночной расстановки составов54На Рисунке 3.3 представлены фрагменты ПГД, построенных для линийМосковскогометрополитена,иллюстрирующиепоследовательностьосвобождения указателей ночной расстановки для станций, соответствующихсхемам на Рисунке 3.2.a)N6N5N4N3N2N11 ст.
п.ук. 11 ст. п.ук. 2I гл. ст.п. ук. 3I гл. п.ук. 4I гл. п.ук. 5I гл. п.ук. 6Станция A2 ст. п.ук. 12 ст. п.ук. 2II гл. ст.п. ук. 3II гл. п.ук. 4II гл. п.ук. 5II гл. п.ук. 6N7N8N9N10N11N12N61 ст. п.ук. 1N51 ст. п.ук. 2N4I гл. ст.п. ук. 3N3I гл. п.ук. 4N2I гл. п.ук. 5N1I гл. п.ук. 6II гл. п.ук. 4N10II гл. п.ук. 5N11II гл. п.ук. 6N12б)3 ст. п.Станция AN132 ст.
п.ук. 1N72 ст. п.ук. 2N8II гл. ст.п. ук. 3N955в)N61 ст. п.ук. 1N51 ст. п.ук. 2N4I гл. ст.п. ук. 3N3I гл. п.ук. 4N2I гл. п.ук. 5N1I гл. п.ук. 6Станция A2 ст. п.ук. 1N72 ст. п.ук. 2N8II гл. ст.п. ук. 3N9II гл. п.ук. 4N10II гл. п.ук. 5N11II гл. п.ук. 6N12N51 ст. п.ук. 2N4I гл. ст.п. ук. 3N3I гл. п.ук. 4N2I гл. п.ук. 5N1I гл.
п.ук. 6II гл. п.ук. 4N10II гл. п.ук. 5N11II гл. п.ук. 6N12г)N61 ст. п.ук. 13 ст. п.N13Станция A4 ст. п. N142 ст. п.ук. 1N72 ст. п.ук. 2N8II гл. ст.п. ук. 3N9Рисунок 3.2 – Схемы расположения указателей ночной расстановки для основныхтипов станций, существующих на Московском метрополитене: а) –на конечнойдвухстрелочной станции; б) –на конечной трехстрелочной станции; в) –наконечной четырехстрелочной станции; г) –на конечной шестистрелочной станции56a)б)в)г)Рисунок 3.3 – Последовательности освобождения и заполнения указателей ночнойрасстановки в рамках ПГД для различных типов станций, существующих наМосковском метрополитене: а) –на промежуточной двухстрелочной станции(станция Баррикадная Таганско-Краснопресненской линии); б) –напромежуточной трехстрелочной станции (станция Третьяковская Калининскойлинии); в) –на конечной четырехстрелочной станции (станция Юго-ЗападнаяСокольнической линии); г) –на конечной шестистрелочной станции (станцияРечной вокзал Замоскворецкой линии)57После выполнения функций ввода информации об указателях ночнойрасстановки составов и размещении указателей ночной расстановки составов напутях линии (Рисунок 2.1) в распоряжении владельцев функций (инженерграфистСлужбыдвиженияисотрудникСлужбыпообслуживаниюинфраструктуры) таблица указателей ночной расстановки составов и граф,отражающий информацию о взаимном расположении указателей ночнойрасстановки составов и стрелочных переводов на путях каждой станции (базаданных размещения указателей ночной расстановки составов на путях линии).Исходной информацией для решения поставленной задачи построения ГОявляется схема организации ночной расстановки составов на станции, по которойстроится граф, отражающий информацию о взаимном расположении указателейночной расстановки составов и стрелочных переводов на путях станции.
НаРисунке 3.4 представлены такие графы, полученные на основе информации,визуализированной на Рисунке 3.2. Представленные на Рисунке 3.4 графыраскрашены в три цвета: желтый цвет используется для раскрашивания вершин, соответствующихуказателям; белый цвет используется для раскрашивания вершины, соответствующейточке начала освобождения указателей или завершения заполнения указателей.Первыми освобождаются или последними заполняются указатели, которымсоответствуют вершины, смежные с белой, т.е. соединенные с ней ребром. Взависимости от того, какое действие выполняется (освобождение или заполнениеуказателей и в каком направлении) меняется местоположение белой вершины награфе. Вершине белого цвета в построенном дереве будет соответствовать исток; зеленый цвет используется для раскрашивания вершин, соответствующихстрелочным переводам [139].Рассматриваемыйграфявляетсясмешанным,содержащимкакориентированные, так и неориентированные ребра в зависимости от ихположения относительно зеленых вершин:58 ребро направленное и его концом является зеленая вершина, если оноподходит к зеленой вершине в пошерстном направлении (движение пострелочному переводу в направлении от крестовины к его острякам); ребро ненаправленное во всех остальных случаях.а)N6N5N4N3N2N11 ст.
п.ук. 11 ст. п.ук. 2I гл. ст.п. ук. 3I гл. п.ук. 4I гл. п.ук. 5I гл. п.ук. 62 ст. п.ук. 12 ст. п.ук. 2II гл. ст.п. ук. 3II гл. п.ук. 4II гл. п.ук. 5II гл. п.ук. 6N7N8N9N10N12N13Для заполненияДля освобожденияб)N6N5N4N3N2N11 ст. п.ук. 11 ст. п.ук. 2I гл. ст.п. ук. 3I гл. п.ук. 4I гл. п.ук. 5I гл. п.ук. 6Для заполнения2 ст. п.ук.
12 ст. п.ук. 2II гл. ст.п. ук. 3II гл. п.ук. 4II гл. п.ук. 5II гл. п.ук. 6Для освобожденияN7N8N10N11N12N133 ст. п.N959в)N6N5N4N3N2N11 ст. п.ук. 11 ст. п.ук. 2I гл. ст.п. ук. 3I гл. п.ук. 4I гл. п.ук. 5I гл. п.ук. 62 ст. п.ук. 12 ст. п.ук. 2II гл. ст.п. ук. 3II гл. п.ук.
4II гл. п.ук. 5II гл. п.ук. 6N7N8N9N10N11N12Для заполненияДля освобожденияг)N6N5N4N3N2N11 ст. п.ук. 11 ст. п.ук. 2I гл. ст.п. ук. 3I гл. п.ук. 4I гл. п.ук. 5I гл. п.ук. 6Для заполнения2 ст. п.ук. 12 ст. п.ук. 2II гл. ст.п. ук. 3II гл. п.ук. 4II гл. п.ук. 5II гл. п.ук.
6Для освобожденияN7N8N9N10N11N12N133 ст. п.4 ст. п.N14Рисунок 3.4 – Графы, полученные по схеме расположения указателей ночнойрасстановки для основных типов станций, существующих на Московскомметрополитене: а) –на конечной двухстрелочной станции; б) –на конечнойтрехстрелочной станции; в) –на конечной четырехстрелочной станции; г) –наконечной шестистрелочной станции60В исходном графе каждому стрелочному переводу соответствует своязеленая вершина, которой инцидентны как минимум три ребра: однонеориентированное или ориентированное, началом которого является эта зеленаявершина, и два ориентированных, концом которых является эта зеленая вершина.Количество ребер, инцидентных зеленой вершине, т.е.
соединяющих её с другимивершинами, может превышать три, если ей смежны другие зеленые вершины.Двум зеленым вершинам инциденты два кратных, т.е. инцидентных одной и тойже паре вершин, ребра, направленные в противоположных направлениях.3.3 Удаление из графа вершин, соответствующих стрелочным переводамПервой исполняемой функцией в рамках процесса формирования порядказаполнения указателей ночной расстановки составов на линии (Рисунок 3.1)является удаление из графа вершин, соответствующих стрелочным переводам.Соответствующий алгоритм представлен на Рисунке 3.5.Блоком 1 – отмечено начало алгоритма.В блоке 2 – проверяется условие наличия в графе зеленые вершины.
Вслучае, если они существуют, происходит переход к блоку 9, в ином случае –переход к блоку 4.В блоках 3 – 8 организован цикл по ребрам, инцидентным желтой и зеленойвершинам одновременно, неориентированным или ориентированным, длякоторых зеленая вершина является началом.В блоке 3 – начинается указанный цикл.В блоке 4 – проверяется условие наличия рёбер, кратных выбранному. Вслучае, если они не существуют, происходит переход к блоку 5, в ином случае –переход к блоку 8.В блоке 5 – из графа удаляется выбранное ребро, инцидентное желтой изеленой вершинам одновременно.611.Начало2.Есть зеленые вершины?3.ДаЦикл по ребрам, инцидентнымжелтой и зеленой вершинамодновременно, неориентированным илиориентированным, для которых зеленаявершина является началом4.У выбранного ребра естькратные ребра ?Нет5.Из графа удаляется выбранное ребро,инцидентноежелтой и зеленой вершинамодновременноДаНет6.Рёбра, инцидентные зеленойвершине, инцидентной удаленномуребру, становятся инцидентныжелтой вершине, инцидентнойудаленному ребру7.Из графа удаляется зеленая вершина,инцидентная удаленному ребру8.Цикл по ребрам, инцидентнымжелтой и зеленой вершинамодновременно, неориентированным илиориентированным, для которых зеленаявершина является началом9.Все кратные ориентированные ребразаменяются единственныминеориентированными10.КонецРисунок 3.5 – Схема алгоритма удаления из графа вершин, соответствующихстрелочным переводам62В блоке 6 – рёбра, инцидентные зеленой вершине, инцидентной удаленномуребру, становятся инцидентны желтой вершине, инцидентной удаленному ребру.В блоке 7 – из графа удаляется зеленая вершина, инцидентная удаленномуребру.В блоке 8 – завершается указанный цикл.Вблоке9–всекратныеориентированныеребразаменяютсяединственными неориентированными.Блоком 10 – отмечено завершение алгоритма.На рисунке 3.7 представлены графы, полученные на основе информации,визуализированной на Рисунке 3.4 в результате исполнения разработанногоалгоритма.3.4 Уплотнение графа и построение дерева3.4.1Общие положенияПосле удаления из графа вершин, соответствующих стрелочным переводам,возможен выбор одной из следующих функций [89]: построение дерева; уплотнение графа с последующим разворачиванием «уплотненного»графа в дерево.Урезультатовисполнениякаждогоиз этихдействийестьпреимущества и недостатки, представленные в Таблице 3.1 и на Рисунке 3.6.свои63Таблица 3.1 – Преимущества и недостатки результатов преобразования графоврасположения указателей ночной расстановки составов после удаления вершин,соответствующих стрелочным переводамСпособПреимуществапреобразованияУплотнение СжатоеграфапредставлениеинформацииПостроениедереваНедостаткиНеобходимостьдополнительнойобработкиинформацииприееиспользовании всценарияхпостроения ПГДИнформация не Объемноетребуетпредставлениедополнительнойинформацииобработки при ееиспользовании всценарияхпостроения ПГДВсе вершины дерева,соответствующиеодной вершинеисходного графа,редуцируют в однувершину уплотненногографаВершиныИсходный графОтличительныечерты множествавершинВсе вершиныдерева,соответствующиеодной вершинеисходного графа,заменяютсяодной вершинойуплотненногографаКаждой вершинеуплотненногографа, имеющейразные пути,приведшие к нейот истока,соответствуетотдельнаявершина дереваДеревоВсе кратные одинаковонаправленные ребрадерева заменяютсяодним ребромуплотненного графа стем же направлениемУ каждой вершиныдереваесть только одновходящее ребро,соответствующееединственномувозможному пути отистока к вершине, имножествоисходящих ребер,соответствующихвсем ветвлениямпутиКаждой вершинеуплотненного графа,имеющей разные пути,приведшие к ней отистока, соответствуетотдельная вершинадереваУплотненный графРебраОтличительныечерты множествареберВсе кратныеодинаковонаправленные ребрадерева заменяютсяодним ребромуплотненного графас тем женаправлениемДеревоУ каждой вершиныдерева есть только одно входящееребро, соответствующееединственному возможному путиот истока к вершине, и множествоисходящих ребер,соответствующих всемветвлениям путиизоморфныеРисунок 3.6 – Возможность получения из уплотненного графа дерева,содержащего все возможные последовательности заполнения или освобожденияуказателей ночной расстановки на станции64Разработанные автором алгоритмы уплотнения графов и построениядеревьев являются комбинацией следующих алгоритмов [142] [143]: поиска в ширину (сначала посещаются вершины, которые расположеныближе к исходной вершине, а потом более дальние вершины); поиска в глубину (сначала выбирается вершина, смежная с текущей; есливсе смежные вершины уже посещены или у вершины нет смежных вершин,алгоритм возвращается на последнюю вершину, у которой есть непосещенныесмежные вершины); топологической сортировке вершин графа с учетом всех возможныхперестановок вершин и ряда ограничений, связанных с цветом вершин (это такоеупорядочение его вершин, при котором если в графе присутствует ребро,начинающееся в вершине и заканчивающееся в вершине , то вершина появляется до вершины в упорядочении; это упорядочивание вершин графавдоль вертикальной линии, при котором все рёбра направлены сверху вниз).При реализации функций уплотнения графа и построения дерева множествоцветов, используемых для раскрашивания вершин графа расширяется: серыйцветиспользуетсядляраскрашиваниявершин,которымсоответствует вершина в «уплотненном» графе или построенном дереве; черный цвет используется для раскрашивания вершин, обладающихследующим свойством: самой вершине и всем смежным ей вершинамсоответствуют вершины в «уплотненном» графе или построенном дереве.65Рисунок 3.7.а – Результат преобразования схем организации ночной расстановкисоставов для двухстрелочной станцииРисунок 3.7.б – Результат преобразования схем организации ночной расстановкисоставов для трехстрелочной станции66Рисунок 3.7.в – Результат преобразования схем организации ночной расстановкисоставов для четырехстрелочной станцииРисунок 3.7.г – Результат преобразования схем организации ночной расстановкисоставов для шестистрелочной станции673.4.2Построение дереваНа Рисунке 3.8 представлен алгоритм построения дерева.Припервомвызовеалгоритмавкачестветекущейвершинырассматривается белая вершина графа, а запомненной вершины не существует.Блоком 1 – отмечено начало алгоритма.В блоке 2 – проверяется условие работы с текущей вершиной белого цвета.В случае, если текущая вершина белая, происходит переход к блоку 3, в иномслучае – переход к блоку 4.В блоке 3 – создается исток дерева.В блоке 4 – добавляется в дерево вершина, соответствующая текущейвершине графа, как смежной к вершине, соответствующей запомненной вершинеграфа.В блоке 5 – фиксируются параметры текущей итерации процесса с цельюкорректного их восстановления после возврата из рекурсивных процедур последостижения граничного условия построения дерева: сохранение информации отекущей серой вершине и текущей раскраске вершин.В блоке 6 – раскрашивается текущая вершина в серый цвет.В блоках 7 – 13 организован цикл по всем серым вершинам графа.В блоке 7 – начинается цикл по всем серым вершинам графа.В блоке 8 – проверяется условие наличия пары вершин, одна из которыхжелтая, а другая – текущая серая, инцидентных единственному ребру, при этомэто ребро неориентированное или выходит из текущей вершины.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
