Диссертация (792664), страница 10
Текст из файла (страница 10)
В качестве новой текущей вершины рассматривается текущая желтая вершина,в качестве запомненной вершины – текущая серая. Блок разбит на две части сцелью обозначения дальнейшего пути выполнения действий в процессе возвратаиз рекурсивно вызванных процедур (переход от блока 14).В блоке 10 – завершается цикл по желтым вершинам, соседним с текущейсерой.В блоке 11 –раскрашивается серая вершина графа в черный цвет.В блоке 12 – завершается цикл по всем серым вершинам графа.В блоке 13 – происходит восстановление после возврата из рекурсивныхпроцедур после достижения граничного условия построения пути.Блоком 14 – отмечено завершение алгоритма.3.4.5Сравнение результатов уплотнения графа и построения дереваПараметрыисходныхиуплотненныхграфов,атакжесоответствующих разным типам станций, приведена в Таблице 3.2.деревьев,84Таблица 3.2 – Параметры исходных и уплотненных графов, а также деревьев,соответствующих разным типам станцийТипыстанцийИсходный графМощность Мощностьмножества множестваребер Eвершин V2 стрелки3 стрелки4 стрелки6 стрелок11121214Мощностьмножестваребер«уплотненного»графа1213121435525082ДеревоМощностьмножестваребердерева1211141134935953Мощностьмножествастоковдерева2836042012600Исходные графы являются разреженными.
Для всех четырех типов станций|| гораздо меньше ||2 , где || – множество ребер графа, а || – множество еговершин. В связи с этим при разработке программного и информационногообеспечения автоматизированной системы «АРМ Графиста–2.0» в качествеспособа описания исходных графов выбраны списки смежных вершин –последовательности исходящих ребер для каждой вершины [142]. Такой способописания более компактный в случае разреженных графов, чем использованиематрицы смежности, и удобен для реализации функций визуализации графов.Мощностьмножествавершин«уплотненного»графасовпадаетсмощностью множества вершин исходного графа.
Мощность множества ребер«уплотненного» графа превышает мощность множества ребер исходного графа в3-5 раз.Мощность множества вершин дерева превышает мощность множества егоребер на единицу. Каждая третья или четвертая вершина является стоком дерева.Количествостоковравноколичествувозможныхпоследовательностейзаполнения или освобождения указателей ночной расстановки составов.Мощность множества вершин дерева растёт с увеличением количествастрелочных переводов на станции. Мощность множества вершин дерева растёт сувеличением количества стрелочных переводов на станции и может превышатьколичество вершин исходного графа в 1000 раз. При переходе от двух стрелочных85переводов к трем или четырем мощности множеств, описывающих деревья,увеличиваются на порядок, а при переходе к шести стрелочным переводам – ещев 30 раз.
Длина всех возможных путей от истока к стоку в построенных деревьяходна и та же, она меньше мощности множества вершин исходного графа наединицу.Таким образом, результаты, приведенные в Таблице 3.2, иллюстрируютпреимущество использования алгоритма уплотнения графа с последующимразворачиванием «уплотненного» графа в дерево по сравнению с прямымпостроением дерева.В составе программного обеспечения системы «АРМ Графиста–2.0».автором реализованы: функции ввода информации об указателях ночной расстановки составов; функциивводаинформацииоразмещенииуказателейночнойрасстановки составов на путях линии; разработанные автором и входящие в состав процесса формированияинформации о последовательности заполнения и освобождения указателейночной расстановки составов алгоритмы, схемы которых представлены наРисунках 3.5, 3.8 и 3.10.Результаты работы алгоритмов, представленные на Рисунках 3.4, 3.7, 3.9 и3.11 получены в ходе работы системы «АРМ Графиста–2.0».
Для визуализациирезультатов на Рисунках 3.7, 3.9 и 3.11 использован пакет утилит поавтоматической визуализации графов Graphviz [144].3.4.6 Использование матрицы смежности графа для уплотнения графаИнформация, представленная в форме графов, может быть представлена вформе таблиц [145]. В ходе диссертационного исследования разработан алгоритм,позволяющий преобразовать матрицу смежностей графа, полученного после86удалениявершин,соответствующихстрелочнымпереводам,вматрицусмежностей «уплотненного» графа [146] [145].
На Рисунке 3.13 представленсоответствующий алгоритм.Блоком 1 – отмечено начало алгоритма.В блоке 2 – выбирается строка матрицы, которая соответствует истокуграфа (т.е. столбец с тем же номером не содержит ни одной единицы).В блоке 3 – формируется множества номеров непройденных строк матрицы.В блоке 4 – проверяется условие наличия хотя бы одной единицы в строке.В случае, если в строке существует только одна единица, происходит переход кблоку 5, в ином случае – переход к блоку 7.В блоке 5 – удаляется из множества номеров непройденных строк номератекущей строки.В блоке 6 – выбирается переход к строке, номер которой равен номерустолбца, содержащему единицу в текущей строке.В блоке 7 – составляется множество номеров столбцов, содержащихединицы в текущей строке.В блоке 8 – составляется множество всех возможных размещений по 2элемента этого множества [147].В блоке 9 – Записывается единица в ячейки, положение которыхопределяется полученными наборами индексов.
Единица записывается в ячейку сзаданными индексами, если единица может быть записана и в ячейку споменянными местами индексами. Т.е. если исходно ячейка с индексами i, jсодержала единицу, а ячейка с индексами j, i ее не содержала, то мы содержимоеэтой ячейки и не изменяем.В блоках 10 – 12 организован цикл по строкам, номера которых равныномерам столбцов, содержащих единицы в текущей строке.В блоке 11 – происходит переход к следующему шагу (блок 1) ипродолжается просмотр строк.В блоке 12 – завершается цикл по строкам, номера которых равны номерамстолбцов, содержащих единицы в текущей строке.871.Начало процедуры «Просмотр строк»2.Выбор строки матрицы, котораясоответствует истоку графа3.Формирование множества номеровнепройденных строк4.5.НетВ строке только одна единица ?ДаУдаление из множества номеровнепройденных строк номера текущейстроки6.Переход к строке, номер которой равенномеру столбца, содержащему единицув текущей строке7.Cоставление множества номеровстолбцов, содержащих единицы8.Составление всех возможныхразмещений по 2 элемента этогомножества9.Запись единиц в ячейки, положениекоторых определяется полученныминаборами индексов10.Цикл по всем строкам, номера которыхравны номерам столбцов, содержащихединицы в текущей строкеРекурсивный вызов длястроки, являющейсяпараметром цикла)11.Просмотр строк12.Цикл по всем строкам, номера которыхравны номерам столбцов, содержащихединицы в текущей строке13.14.Множество номеровнепройденных строк пустоеНетДаКонец процедуры «Просмотр строк»Рисунок 3.13 – Алгоритм преобразования матрицы смежностей графа88В блоке 13 – проверяется условие того, что множество номеровнепройденных строк пустое.
В случае, если оно пустое, происходит переход кблоку 14, в ином случае – переход к блоку 4.Блоком 14 – отмечено завершение алгоритма.На Рисунках 3.14 и 3.15 представлены исходные данные и результатыпостроения «уплотненного» графа для одного из типов станций, существующихна Московском метрополитене. Исходный граф, полученный после удаления изграфа вершин, соответствующих стрелочным переводам, является подграфомуплотненного.
Ребра, добавленные в граф в ходе перехода от исходного графа куплотненному, выделены пунктиром.N6N7N8Станция AN5N4N3N2N1Рисунок 3.14 – Схема организации ночной расстановки составов на станцииРисунок 3.15 – «Уплотненный» граф последовательностей заполнения илиосвобождения указателей ночной расстановки составов89В таблицах 3.3 и 3.4 представлены исходная и результирующая матрицысмежности, соответствующие графам, представленным на Рисунках 3.14 и 3.15(«уплотненный»граф)длядвухстрелочнойстанции,существующихнаМосковском метрополитене. Информация на Рисунках 3.11, 3.15 и в Таблице 3.3подтверждаютсовпадениерезультатов,полученныхприматричномиграфическом представлении информации.Таблица 3.3 – Матрица смежностей графа, полученного после удаления вершин,соответствующих стрелочным переводам0000000010000000010000000010000000010000001000000000010000000010Таблица 3.4 – Матрица смежностей «уплотненного» графа000000001000000001000000001001110001011100111000000111000001101090Основные выводы и результаты по главе1.
Разработаны алгоритмы, выполняемые в ходе процесса формированияинформации о последовательности заполнения и освобождения указателейночной расстановки составов.2. Реализован алгоритм восстановления дерева из «уплотненного» графа,который позволяет получить тот же набор последовательностей заполнения илиосвобождения указателей ночной расстановки составов.3. Реализована возможность использования двух форм (матричной играфической)представленияинформацииографовыхобъектахдляавтоматизации построения ПГД и ГО. Показано совпадение полученныхрезультатов.4. Выполнена автоматизация процесса формирования информации опоследовательности заполнения и освобождения указателей ночной расстановки врамках системы «АРМ Графиста–2.0.».5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
