Устройство для определения кратчайшего пути на двумерном решетчатом графе

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 5040 06 Р 15/ тв ЕТЕНИЯ т,т 39 виаци нстит В. И. Петров. етельство СС Р 15/20, 197 ельство СССР Р 15/20, 197 ислитГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ ОПИСАНИЕ ИЗОБ Н АВТОРСКОМУ СВИДЕТЕЛЬСТ(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯКРАТЧАЙШЕГО ПУТИ НА ДВУМЕРНОМ РЕШЕТЧАТОМ ГРАФЕ(57) Изобретение относится к вычтельной технике, а именно к элекронным моделирующим устройствам дляопределения кратчайшего пути на пла,ЯО 12657 нарном графе, и может быть использовано, в частности, при расчете транспортной сети. Цель изобретения - сокращение аппаратных затрат за счетпредставления топологии графа в блоке памяти в виде матрицы связи. Длядостижения этой цели устройство дополнительно содержит счетчик, схемысравнения на равенство, схемы сравнения на больше - меньше, элементы И,мультиплексор, распределитель, мультиплексорыперестановки координат,вычитатель, сумматор и элемент ИЛИ,что позволяет представить исходныйграф в блоке памяти в виде матрицысвязи вместо матрицы смежности и темсамым значительно уменьшить .объемтребуемой памяти. Предлагаемое устройство моиет быть исиоиьвоваио ири,расчете транспортной сети. 5 ил.65/90 Ъ 50 1 12Изобретение относится к вычислительной технике, а именно, к электронным моделирующим устройствам для определения кратчайшего пути на двумерном решетчатом графе, и может быть использовано, в частности, при расчете транспортной сети.Цель изобретения - сокращение аппаратных затрат за счет представле-, ния топологии графа в блоке памяти в виде матрицы связи.На фиг. 1 изображена структурная схема устройства для определения кратчайшего пути на двумерном решетчатом графе; на фиг. 2 - пример выполнения одного разряда мультиплексора перестановки координат; на фиг. 3-5 соответственно пример транс. портной сети промьппленных транспортных роботов; граф, являющийся моделью этой транспортной сети; преобразованный граф.Устройство для определения кратчайшего пути на двумерном решетчатом графе (фиг. 1) содержит генератор 1 импульсов, первый - четвертый регистры 2-5 соответственно, первый - пятый счетчики 6-10 соответственно, первый и второй регистры 11 и 12 промежуточных результатов соответственно, блок 13 памяти, сумматор 14, триггер 15, первую - пятую схемы 16- 20 сравнения на равенство соответственно,.первую и вторую схемы 21 и 22 сравнения на больше-меньше соответственно, шестой счетчик 23, первый и второй мультиплексоры 24 и 25 перестановки координат, распределитель 26, мультиплексор 27, вычитатель 28, сумматор 29 и элемент ИЛИ 38, первый . и второй элемент И 31 и 32.Один разряд мультиплексора 24 (25) перестановки координат(фиг, 2) содержит элемент НЕ 33 и первый и второй элементы 2-2 И-ИЛИ 34 и 35 соответственно, выходы которых являются выходами одного разряда мультиплексора 24(25) перестановки координат. Его входы подключены следующим образом: первый вход соединен с входомэлемента НЕ 33 и первыми входами первого и второго элементов 2 2 И-ИЛИ 34 и 35, и второй вход соединен с вто-рым входом первого элемента 2-2 И-ИЛИ34 и червертым входом второго элемента 2-2 И-ИЛИ 35, третий вход соединен с четвертым входом первого элемента 2-2 И-ИЛИ 34 и вторым входом 0 15 20 25 30 35 40 45 55 второго элемента 2-2 И-ИЛИ 35, Выходэлемента НЕ 33 подключен к третьимвходам первого и второго элементов2-2 И-ИЛИ 34 и 35,Графовые модели используются очень широко, в том числе в качестве моделей транспортных сетей. Плоскиетранспортные сети, а также пространственные сети, графыкоторых не содержат полного пятивершинного и полного двудольного шестивершинного подграфов, могут быть представлены ввиде планарного графа. Следовательно,широкий класс транспортных сетей может иметь своей моделью планарныйграф. Планарный граф можно преобразовать в подграф двумерного решетчатого графа, вершинами которого являются упорядоченнье пары чисел (, 3),где х=1,ш)=1,п, называемые координатами вершин. Для этого вводятсяфиктивные вершины при последовательном разбиении ребер и при уменьшениистепеней вершин. В первом случае весодного из образованных ребер равенвесу разбиваемого ребра, а вес остальных образованных ребер равен О.Во втором случае одна вершина представляется несколькими вершинамитаким образом, что сумма их степенейбез учета ребер, инцидентных толькоим и имеющих веса О, равна степенипредставляемой вершины. Информация ополученном таким образом графе предварительно записывается в блоке памяти в виде матрицы связи С, каждаястрока которой содержит три элемента; С , и С- номера вершин, инцидентных.к-му ребру, С вес К -го ребра. Если в графе Б вершин, Б - числофиктивных вершин, Х - коэ 44 ициентсредней степени вершин графа, то дляпредставления графа матрицей смежности А и матрицей связи С потребуютсясоответственно объемы памяти Б и ББ=Б (1),(3)Б 3 ХБ+Б, )В конечном двумерном решетчатомБ Бграфе хс 4 и - - -- -, Таким обраБ, 6(Б+Б 7зом, в тех случаях, когда число фиктивных вершин по отношению к числувершин невелико, а число последнихдостаточно велико, объем памяти, требуемый для представления графа матрицей связи, значительно меньше объема памяти, требуемой для представления графа матрицей смежности. Поскольку основной объем аппаратных затрат приходится на блок памяти для представления топологии графа, то замена представления графа матрицей связи вместо матрицы смежности позволит значительно сократить объем оборудования устройства поиска кратчайшего 10 пути на графе.На предлагаемом устройстве последовательно генерируются пути, у которых монотонно изменяется хотя бы одна координата. Пути представляются 15 в одной из двух форм:1) (о, .1,)-(1, .1)-(1, .1)- - -(1, )-(2, ) )(2, ))- -2) (3., ) 0)-(х1-(з., 1)-.- 20 -(3. 1) - (1 2) --( 2 2) ( , 1) (о )где г и Р - число ребер в пути, инциндентные вершины которых имеют координаты =9 и 1=з соответственно 251ЧДля путей, записанных в первой форме, монотонно изменяется координата , второй - 3.30Каждый путь однозначно определя-. ется множеством координат:) (33, д д .1 д 11ф"ф-.3 При, выполнении полного перебора в35 этих множествах координат Анерируются все пути. При этом определяющими путь вершинами являются: 40 1) (о, .1, ), (1, .1), (1, 1," ),(Х, 2)(, п 1.", и), (1.и+1Путь начинает рассматриваться, фкак только одна из двух его конечных вершин совпадает с определяющей путьвершиной, и кончает рассматриваться, когда другая из двух его конечных вершин также совпадает с определяю-. щей путь вершиной, Если все ребра между этими вершинами существуют, тосуществует на графе и данный путь. Веса всех существующих путей сравниваются и путь с минимальным весом 55 ,является кратчайшим.Перед началом работы во второйрегистр 3 заносятся две кочечные вершины, между которыми ищется кратчайший путь, а в блоке 13 памяти зано-и сится матрица связи преобразованного графа. Сначала записываются ребра, у вершин которых одинаковое значение х, а значениевозрастает, затем аналогично для следующих значений х. После этого подобным образом записываются ребра, у вершин которых одинаковое значениеПосле запуска генератора 1 импуль. сов с его выхода импульсы поступают на вход первого счетчика 6, с первого (параллельного) выхода которого код адреса поступает на первый (адресный вход блока 13 памяти, после полного просмотра которого со второго) последовательного (выхода первого счетчика 6 подается импульс, увеличивающий на 1 содержимое второго счетчика 7, в котором содержится код первой координаты вершин, и сдвигающий содержимое первого ре;истра 2. Разрядность первого счетчика 6 равна разрядности кода адреса блока 13 памяти, а сдвиг содержимого первого ре гистра 2 осуществляется каждый раз на число разрядов, отводимых под хранение кода одной координаты, Для этого первый регистр 2.может быть организован из параллельно включенных регистров, число которых равно числу разрядов. С второго (последовательного) выхода второго счетчика 7 после полного пересчета подается импульс, сбрасывающий триггер 15 и увеличивающий на 1 содержимое пятого счетчика 1 О, все разряды которого, кроме двух старших, при этом записываются в первый регистр 2. Эти разряды содержат множество кодов вторых координат, однозначно определяющих путь. Следующий за ними разряд с третьего выхода пятого счетчика 1 О подается на управляющие входы первого и второго мультиплексоров 24 и 25 перестановки координат, на информационные входы которых подаются соответственно содержимое второго регистра 3 и блока 13 памяти для уста" новления соответствия между первой и второй координатами х ив зависимости от формы представления пути. Старший разряд пятого счетчика 10, служит для отключения генератора и останова устройства после генерации всех путей. В первом регистре 2 хранятся коды вторых координат, а с первого (параллельного) выходавторого счетчика 7 снимается код первой координаты. С выхода второго мультиплексора 25 перестановки координат снимаются коды координат вершин ребер, которые хранятся в блоке 3 памяти. С выхода первого мультиплексора 25 перестановки координат в соответствующем виде коды координат конечных вершин поступают на О вход третьей схемы 18 сравнения на равенство, на другие входы которой поступают код координаты с выхода мультиплексора 27 и код второй координаты. При совпадении сгенерированной вершины с любой из конечных вершин на выходе этой схемы появляется единичный сигнал, который поступает на второй вход триггера 15. На входы первой схемы 16 сравнения на равенст О во поступают: коды координат вершин ребер, первой и второй координат и уменьшенной на 1 первой координаты в сумматоре 18 уменьшения на 1, на входы которого подаются код первой 25 координаты и код 1. В этой схеме происходит обнаружение ребер вида(С 1.3)-(Ч 1 ) Ы, з- -1)-(о з)При обнаружении одной из конечных вершин и ребра, инцидентного ему, первый раз для данного пути триггер 15 взводится, второй раз сбрасываетсяПри взведении триггера 15 происходит начальная установка третьего счетчика 8 в значение кода первой координаты и четвертого счетчика 9 в значение уменьшенного на 1 кода первой координаты. На первый и третий (информационные) входы мультиплексора 27 поступают соответственно коды первой координаты и , первой координаты, уменьшенной на 1, а на второй (управляющий) вход поступает сигнал с второго (прямого) выхода триггера 15 таким образом, что при взведенном триггере с выхода мультиплексора снимается код первой координаты, уменьшенной на а при невзведенном - код первой ко 50 ординаты. Коды двух крайних координат с выхода первого регистра 2 пос" тупают на первый (информационный)вход распределителя 26 и вход второйсхемы 22 сравнения на больше - мень 55 ше, на выходе которой единичный сигнал появляется только в том случае, если код первой из поступающих на вход координат меньше кода второй. С выхода этой схемы сигнал подается на второй (управляющий) вход распределителя 26, который устроен аналогично мультиплексорам перестановки координат таким образом, что код большей- координаты поступает на первый вход пятой схемы 20 сравнения на равенство, а меньшая - на третий вход (начальной установки) шестого счетчика 23, выход которого вместе с увеличенным на 1 своим значением в сумматоре 29 увеличения на 1, на входы которого поступают коды выхода шестого счетчика 23 и код +1, а также коды первой координаты и координаты вершин ребер, поступает на входы второй схемы 17 сравнения на равенство. В этой схеме производится обнаружение ребер вида(1 1 ) (,1 ) и (1з)- Сигнал с выхода этой схемы поступает на второй (счетный) вход шестого счетчика 23 и второй вход элемента ИЛИ 30. Когда триггер 15 взведен и на выходе первой или второй схем 16 и 17 сравнения на равенство появляется единичный сигнал, с выхода второго элемента И 32 поступает сигнал на входы записи первого и второго регистров 11 и 12 промежуточного результата, в первый из которых, построенный как стековый регистр, последовательно записываются коды 1вершин ребер из блока 13 памяти, а во второй записывается значение из сумматора 14, на второй вход которого поступает значение веса ребра из блока 13 памяти, а на первый - предыдущее значение, содержащееся во втором регистре 12 промежуточного результата, которое поступает также на второй вход (данных) четвертого регистра 5 и второй вход первой схе- ,мы 21 сравнения на больше - меньше, на первый вход которой поступает содержимое четвертого регистра,5Выход первого регистра 11 промежуточного результата соединен с вторым входом (данных) третьего регистра 4. На второй вход пятой схемы 20 сравне-ния на равенство поступает содержимое шестого счетчика 23. При совпадении значений на входах схемы 20 сравнения на равенство подается сигнал на первый вход (обнуления) шестого счетчика 23 и на второй (счетный) вход четвертого счетчика 9. Содержимое третьего и четвертого счетчиков 8 и 9 поступает соответственно на второй и третий входы четвертой схемы 19 сравнения на равенство, на первый вход которого поступает код 5 первой координаты, а с выхода которой единичный сигнал поступает на первый вход первого элемента И 31, на второй вход которого поступает сигнал с выхода первой схемы 21 срав 10 нения на больше - меньше, а на третий вход - сигня.п с первого (инверсного) выхода триггера 15. Таким образом, когда рассмотрение пути закончено, т.е. триггер 15 сброшен,15 его вес меньше веса пути с минимальным весом из рассмотренных ранее, т.е. на выходе первой схемы 21 сравнения на больше - меньше - единичный сигнал, и всефребра пути существуют, т.е, содержимые третьего и четвертого счетчиков 8 и 9 равны коду первой координаты, с выхода первого элемента И 31 подается сигнал на первые входы (записи) третьего и четвертого регистров ц и 5, в первый из которых записываются коды вершин, образующих данный путь, а во второй - вес этого пути. После генерации всех путей .в этих регистрах хранятся соответственно коды вершин, образующих кратчайший путь и его вес.Формула изобретения 35Устройство для определения, кратчайшего пути на двумерном решетчатом графе, содержащее генератор импульсов, выход которого соединен с 40 входом первого счетчика, первый выход которого подключен к адресному входу блока памяти, выход которого соединен с первым входом первого регистра промежуточного результата, 45 второй счетчик, вход которого подключен к второму выходу первогосчетчика, первый выход второго счетчика соединен с первым входом первой схемы сравнения на равенство, вто рой вход которой подключен к выходу первого регистра, третий, четвертый и пятый счетчики, первый выход пятого счетчика соединен с первым входом первого регистра, триггер, первый сумматор, второй регистр промежуточного результата, второй, третий и четвертый регистры, о т л и ч а ю -щ е е с я тем, что, с целью сокращения аппаратных затрат за счетпредставления топологии графа в блоке памяти в виде матрицы связи, оносодержит шестой счетчик, вторую,третью, четвертую и пятую схемы сравнения на равенство, две схемы сравнения на больше - меньше, два элемента И, мультиплексор, распределитель, два мультиплексора перестановки координат, вычитатель, второй сумматор и элемент ИЛИ, выходы второгосчетчика подключены к входам вычитателя, первым информационным входаммультиплексора, первым входам второйи четвертой схем сравнения на равенство и входам третьего счетчика, выход которого соединен с вторым входом четвертой схемы сравнения на равенство, выход которой подключен кпервому входу первого элемента И,выход которого подключен,к первымвходам третьего и четвертого регистров, выход четвертого регистра соединен с первым входом первой схемысравнения на больше - меньше, выходкоторой подключен к второму входупервого элемента И, третий вход которого соединен с нулевым выходомтриггера; единичный выход которогоподключен к первому входу второгоэлемента И, входам начальной установки третьего и четвертого счетчиков и управляющему входу мультиплексора, выход четвертого счетчика соединен с третьим входом четвертойсхемы сравнения на равенство, второйвыход второго счетчика подключен квходу пятого счетчика и нулевомувходу триггера, счетный вход которого соеДинен с выходом третьей схемысравнения на равенство, первый входкоторой соединен с выходом первогомультиплексора перестановки координат, информационный вход которогоподключен к выходу второго регистра,вход которого является входом устройства для задания конечных вершин,между которыми ищется кратчайшийпуть, первый вход генератора импульсов соединен с вторым входом пятогосчетчика, третий выход которого подключен к управляящим входам первогои второго мультиплексоров перестановки координат, информационный входвторого мультиплексора перестановкикоординат соединен с выходом блокапамяти, информационные входы которого являются входами устройства для9 12 б 5 задания топологии графа, выход второго мультиплексора перестановки координат соединен с третьим входом первой и вторым входом второй схем сравнения на равенство, выход первой, схемы сравнения на равенство соединен с управляющим входом третьего счетчика и первым входом элемента ИЛИ,. выход которого подключен к вто-рому входу второго элемента И, вы ход которого соединен с вторым входом первого и первым входом второго регистров промежуточного результата, выход второго регистра промежуточного результата подключен к вторым входам первой схемы сравнения на больше- меньше и четвертого регистра и к первому входу первого сумматора, выход которого соединен с вторым входом второго регистра промежуточ ного результата, второй вход первого сумматора соединен с выходами блокаВ памяти, выход первого регистра промежуточного результата подключен к второму входу третьего регистра, 25 первый выход пятого счетчика соединен с первым входом первого регистра, выход которого подключен к второму входу третьей схемы сравнения на равенство, первому входу распре делителя,и входу второй схемы срав 790 10нения на больше - меньше, выход которой соединен с вторым входом распределителя, первый выход которогоподключен к первому входу пятой схемы сравнения на равенство, выходкоторой соединен со счетными входамичетвертого и шестого счетчиков, выход шестого счетчика соединен с вторым входом пятой схемы сравнения наравенство, третьим входом второй схемы сравнения на равенство ивходом второго сумматора, выходкоторого подключен к четвертомувходу второй схемы сравненияна равенство, выход которой соединенс вторым входом элемента ИЛИ й управляющим входом шестого счетчика,вход начальной установки которогоподключен к второму выходу распределителя, выход вычитателя соединен счетвертым входом первой схемы сравнения на равенство, управляющим входом четвертого счетчика и управляющим входом мультиплексора, выход которого подключен к третьему входу.третьей схемы сравнения на равенство, а выходы третьего и четвертого регистров являются выходами устройства для фиксациикодов вершин кратчайшего пути,26579012657900 1 2 3 9 Р б 7 8 У 10 0Составитель С. НазаровРедактор А, Ворович Техред И.Ходанич Корректор М. Максимишинец Заказ 5666/47 Тираж,671 Подписное ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д. 4/5Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4