Устройство для определения кратчайшего пути на двумерном решетчатом графе Советский патент 1986 года по МПК G06F15/173 

to

о ел

со 1 Изобретение относится к вычислительной технике, а именно, к электронным моделирующим устройствам для определения кратчайшего пути на двумерном решетчатом графе, и может быть использовано, в частности, при расчете транспортной сети. Цель изобретения - сокращение аппаратнб1х затрат за счет представлег кия топологии графа в блоке памяти в виде матрицы связи. . На фиг. 1 изображена структурная схема устройства для определения кратчайшего пути на двумерном решетчатом графе; на фиг. 2 - пример выполнения одного разряда мультиплексора перестановки координат; на фиг. 3-5 соответственно пример транс портной сети промышленных транспортных роботов; граф, являющийся моделью этой транспортной сети; преобразованный граф. Устройство для определения кратчайшего пути на двумерном решетчатом графе (фиг. 1) содержит генератор 1 импульсов, первый - четвертый регистры 2-5 соответственно, первый пятый счетчики 6-10 соответственно, первый и второй регистры 11 и 12 про межуточных результатов соответственно, блок 13 памяти, сумматор 14, триггер 15, первую - пятую схемы 1620 сравнения на равенство соответственно,, первую и вторую схемы 21 к 22 сравнения на больше-меньше соответственно, шестой счетчик 23, первый и второй мультиплексоры 24 и 25 перестановки координат, распределитель 26, мультиплексор 27, вычитатель 28, сумматор 29 и элемент ИЛИ 30, первый и второй элемент И 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 и вторым входом 90 . 2 второго элемента 2-2И-ИЛИ 35. Выход элемента НЕ 33 подключен к третьим входам первого и второго элементов 2-2И-Ш1И 34 и 35. Графовые модели используются очень широко, в том числе в качестве моделей транспортных сетей. Плоские транспортные сети, а также пространственные сети, графы которых не содержат полного пятивершинного и полного двудольного щестивершинного подграфов , могут быть представлены в виде планарного графа. Следоват.ельно, широкий класс транспортных сетей может иметь своей моделью пленарный граф. Планарный граф можно преобразовать в подграф двумерного решетчатого графа, вершинами которого являются упорядоченные пары чисел (i, j), где ,m, j l ,n, называемые координатами вершин. Для этого вводятся фиктивные вершины при последовательном разбиении ребер и при уменьшении степеней вершин. В первом случае вес одного из образованных ребер равен весу разбиваемого ребра, а вес остальных образованных ребер, равен 0. Во втором случае одна вершина представляется несколькими вершинами таким образом, что сумма их степеней без учета ребер, инцидентных только им и имекяцих веса О, равна степени представляемой вершины. Информация о полученном таким образом графе пред- варительно записывается в блоке памяти в виде матрицы связи С, каждая строка которой содержит три элемента ;С, - номера вершин, инцидентных, к -му ребру, вес к-го ребра. Если в графе N вершин, N - число фиктивных вершин, к - кoэdЙlициeнт средней степени вершин графа, то для . представления графа матрицей смежности А и матрицей связи С потребуются соответственно объемы памяти N. и ,а ОА L ,(1), ) .(2), №. . ij 3 йТй+йТ в конечном двумерном решетчатом графе и | . Таким образом, в тех случаях, когда число фик- тивных вершин по отношению к числу вершин невелико, а число последних достаточно велико, объем памяти, треуемый Для представления графа матрицей связи, значительно меньше объем памяти, требуемой для представления графа матрицей смежности. Поскольку основной объем аппаратных затрат приходится, на блок памяти для представления топологии графа, то замен представления графа матрицей связи вместо матрицы смежности позволит значительно сократить объем оборудо вания устройства поиска кратчайшего пути на графе. На предлагаемом устройстве после довательно генерируются пути, у которых монотонно изменяется хотя бы одна координата. Пути представляютс в одной из двух форм: О (о, j:)-(i, j;)-(i, j;)-...-d, f )-(2, j;)-...-(2, j/O-...-(m-i;ji-;)-(m, jM; 2) (i:;o)-(i;,(i , 1)-...-(, l)-(i.:, 2)-...-{A , 2)-...-(Cr,- , n-D-d:, n), где Га и Pj - число ребер в пути, лнциндентные вершины которых имеют координаты и соответственно -jPj о . ч.-йО . t -t + l,. .t ч, - ч Для путей, записанных в первой форме, монотонно изменяется координата i, второй - J.. Каждый путь однозначно определя ется множеством координат: 1 N г 40 JO О о 1° 1/ iJo J, J.v.j 2) i«, i°, i°,...i., , i;}. При. выполнении полного перебора в этих множествах координат Лнериру ются все пути. При этом определяющ ми путь вершинами являются: 1) (О, Г), (, Г), (1, j ), .- . 1 7 Vf .2, j;),.. (m ,-rJ, (m, л О Л/ . . / - I-.. т (m+1. j, ); 2Г 1„, 0), (i;, ,), (i-;. , ,), (i;, 2),...,(i:, n)(i: , n), (C, n+1). Путь начинает рассматриваться, как только одна из двух его конечны вершин совпадает с определяющей пут вершиной, и кончает рассматриваться когда другая из двух его конечных вершин также совпадает с определяющей путь вершиной. Если все ребра между этими вершинами существуют, т существует на графе и данный путь. Веса всех существуннцих путей сравни ваются и путь с минимальным весом является кратчайшим. Перед началом работы во второй регистр 3 заносятся две конечные ве шины, между которыми ищется кратчайший путь, а в блоке 13 памяти зано-и сится матрица связи преобразованного графа. Сначала записываются ребра, у вершин которых одинаковое значение 1, а значение j возрастает, затем аналогично для следующих значений i. После этого подобным образом записываются ребра, у вершин которых одинаковое значение j. После запуска генератора 1 импуль сов -с его выхода импульсы поступают на вход первого счетчика 6, с первого (параллельного) выхода которого код адреса поступает на первый (адресный вход блока 13 памяти, после полного просмотра которого со второго) последовательного (выхода первого счетчика 6 подается импульс, увеличивающий на 1 содержимое второго счетчика 7, в котором содержится код первой координаты вершин, и сдвигающий содержимое первого ре:истра 2 ; Разрядность первого счетчика 6 равна разрядности кода адреса блока 13 памяти, а сдвиг содержимого первого регистра 2 осуществляется каждый раз на число разрядов, отводимых-под хранение кода одной координаты. Для этого первый регистр 2.может быть организован из параллельно включенных регистров, число которых равно числу разрядов. С второго (последовательного) вьгхода второго счетчика 7 после полного пересчета подается импульс, сбрасывающий триггер 15 и увеличивающий на . 1 содержимое пятого счетчика 10, все разряды которого, кроме двух старших, при этом записываются в первый регистр 2, Эти разряды содержат множество кодов вторых координат, однозначно определяющих путь. Следукнций за ними разряд с третьего выхода пятого счетчика 10 подается на управляющие входы первого и второго мультиплексоров 24 и 25 перестановки координат, на информационные входа которых подаются соответственно содержимое второго регистра 3 и блока 13 памяти для установления соответствия между первой и второй координатами i и j в зависимости от формы представления пути. Старший разряд пятого счетчика 10, служит для отключения генератора и останова устройства после генерации всех путей. В первом регистре 2 хранятся коды вторых координат, а с первого (параллельного) выхода

второго счетчика 7 снимается код первой координаты. С выхода второго мультиплексора 25 перестановки координат снимаются коды координат вершин ребер, которые хранятся в блоке 13 памяти. С выхода первого мультиплексора 25 перестановки координат в соответствующем виде коды координат конечных вершин поступают на вход третьей схемы 18 сравнения на равенство, на другие входы которой поступают код координаты с выхода мультиплексора 27 и код второй координаты. При совпадении сгенерированной вершинь: с любой из конечных вершин на выходе этой схемы появляется единичный сигнал, который поступает на второй вход триггера 15. На входы первой схемы 16 сравнения на равенство поступают: коды координат вершин ребер, первой и второй координат и уменьшенной на 1 первой координаты в сумматоре 18 уменьшения на 1, на входы которого подаются код первой координаты и код 1. В этой схеме происходит обнаружение ребер вида (q-1, /- )-(q, j;) и ( , s-D-d;, s).

При обнаружении одной из конечных вершин и ребра, инцидентного ему, первый раз для данного пути триггер 15 взводится, второй раз сбрасывается. При взведении триггера 15 происходит начальная установка третьего счетчика 8 в значение кода первой координаты и четвертого счетчика 9 в значение уменьшенного на 1 кода первой координаты. На первый и третий (информационные) входы мультиплексора 27 поступают соответственно коды первой координаты и первой координаты, уменьшенной на 1, а на второй (управляющий) вход поступает сигнал с второго (прямого) выхода триггера 15 таким образом, что при взведенном триггере с выхода мультиплексора снимается код первой координаты, уменьшенной на 1, а при невзведенном - код первой координаты. Коды двух крайних координат с выхода первого регистра 2 поступают на первый (информационный) вход распределителя 26 и вход второй схемы 22 сравнения на больше - меньше, на выходе которой единичный сигнал появляется только в том случае, если код первой из поступающих на вход координат меньше кода второй, С

выхода этой схемы сигнал подается на второй (управляющий) вход распределителя 26, который устроен аналогично мультиплексорам перестановки координат таким образом, что код большей координаты поступает на первый вход пятой схемы 20 сравнения на равенство, а меньшая - на третий вход (начальной установки) шестого счетчика 23, выход которого вместе с увеличенным на 1 своим значением в сумматоре 29 увеличения на 1, на входы которого поступают коды выхода шестого счетчика 23 и код +1, а также коды первой координаты и координаты вершин ребер, поступает на входы второй схемы 17 сравнения на равенство. В этой схеме производится обнаружение ребер вида

(а, jM-(i, j/ ) и (i, s)-fi ч - J-s , s;.

Сигнал с выхода этой схемы .поступает на второй (счетный) вход шестого счетчика 23 и второй вход элемента ИЛИ 30. Когда триггер 15 взведен и на выходе первой или второй схем 16 и 17 сравнения на равенство появляется единичный сигнал, с выхода второго элемента И 32 поступает сигнал на входы записи первого и второго регистров 11 и 12 промежуточного результата, в первый из которых, построенный как стековый регистр, последовательно записываются коды вершин ребер из блока 13 памяти, а во второй записьшается значение из сумматора 14, на второй вход которого поступает значение веса ребрй из блока 13 памяти, а на первый - предыдущее значение, содержащееся во втором регистре 12 промежуточного результата, которое поступает также на второй вход (данных) четвертого регистра 5 и второй вход первой схе,мы 21 сравнения на больше - меньше, на первый вход которой поступает содержимое четвертого регистра-,5. Выход первого регистра П промежуточного результата соединен с вторым входом (данных) третьего регистра 4. На второй вход пятой схемы 20 сравнения на равенство поступает содержимое шестого счетчика 23. При совпадении значений на входах схемы 20 сравнения на равенство подается сигнал на первый вход (обнуления) шестого счетчика 23 и на второй (счетный) вход четвертого счетчика 9. Со7

держимое третьего и четвертого счетчиков 8 и 9 поступает соответственно на второй и третий входы четвертой схемы 19 сравнения на равенство, на первый вход которого поступает код первой координаты, а с выхода которой единичный сигнал поступает на первый вход первого элемента И 31, на второй вход которого поступает сигнал с выхода первой схемы 21 срав нения на больше - меньше, а на третий вход - сигняп с первого (инверсного) выхода триггера 15. Таким образом, когда рассмотрение пути закончено, т.е. триггер 15 сброшен, его вес меньше веса пути с минимальным весом из рассмотренных ранее, т.е. на выходе первой скемы 21 сравнения на больше - меньше - единичный сигнал, и все ребра пути существуют, т.е. содержимые третьего и четвертого счетчиков 8 и 9 равны коду первой координаты, с выхода перового элемента И 31 подается сигнал на первые входы (записи) третьего и четвертого регистров 4 и 5, в первый из которых записываются коды вершин, образующих данный путь, а во второй - вес этого пути. После генерации всех путей в этих регистрах хранятся соответственно коды вершин, образующих кратчайший путь и его вес.

Фо-рмула изобретения

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

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

третью, четвертую и пятую схемы сравнения на равенство, две схемы сравнения на больше - меньше, два элемента И, мультиплексор, распределиfo тель, два мультиплексора перестановки координат, вычитатель, второй сумматор и элемент ИЛИ, выходы второго счетчика подключены к входам вычитателя, первым информационным входам

J5 мультиплексора, первым входам второй и четвертой схем сравнения на равенство и входам третьего счетчика, выход которого соединен с вторым входом четвертой схемы сравнения на ра20 венство, выход которой подключен к первому входу первого элемента И, выход которого подключен с первым входам третьего и четвертого регистров, выход четвертого регистра сое-

25 динен с первым входом первой схемы сравнения на больше - меньше, выход которой подключен к второму входу первого элемента И, третий вход которого соединен с нулевым выходом

, триггераj единичный выход которого .

подключен к первому входу второго элемента И входам начальной установки третьего и четвертого счетчиков и управляющему входу мультиплексора, выход четвертого счетника сое динен с третьим входом четвертой схемы сравнения на равенство, второй выход второго счетчика подключен к входу пятого счетчика и нулевому входу триггера, счетный вход которого соединен с выходом третьей схемы сравнения на равенство, первый вход которой соединен с выходом первого мультиплексора перестановки координат, информационный вход которого

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

55 второго мультиплексора перестановки координат соединен с выходом блока

памяти, информационные входы которого являются входами устройства для задания топологии графа, выход второго мультиплексора перестановки ко ординат соединен с третьим входом первой и вторым входом второй схем сравнения на равенство, выход перво схемы сравнения на равенство соединен с управляющим входом третьего счетчика и первым входом элемента ИЛИ,выход которого подключен к вто рому входу второго элемента И, выход которого соединен с вторым входом первого и первь1М входом второго регистров промежуточного результата выход второго регистра промежуточно го результата подключен к вторым вх дам первой схемы сравнения на больше - меньше и четвертого регистра и к первому входу первого сумматора, выход которого соединен с вторым входом второго регистра промежуточного результата, второй вход первог сумматора соединен с выходами блока памяти, выход первого регистра промежуточного результата подключен к второму входу третьего регистра, первый выход пятого счетчика соединен с первым входом первого регистра, выход которого подключен к второму входу третьей схемы сравнения на равенство, первому входу распределителя, и входу второй схемы сравнения на больше - меньше, выход которой соединен с вторым входом распределителя, первый выход которого подключен к первому входу пятой схемы сравнения на равенство, выход которой соединен со счетными входами четвертого и шестого счетчиков, выход шестого счетчика соединен с вторым входом пятой схемы сравнения на равенство, третьим входом второй схемы сравнения на равенство и входом второго сумматора, выход которого подключен к четвертому входу второй схемы сравнения на равенство, выход которой соединен с вторым входом элемента KJIH-1i управляюш;им входом шестого счетчика, вход начальной установки которого подключен к второму выходу распределителя, выход вычитателя соединен с четвертым входом первой схемы сравнения на равенство, управляющим входом четвертого счетчика и управляющим входом мультиплексора, выход которого подключен к третьему входу третьей схемы сравнения на равенство, а выходы третьего и четвертого регистров являются выходами устройства для фиксации кодов вершин кратчайшего пути.

h-П-D

D

7 -ПDОD

/

-О-

N

Изобретение относится к вычислительной технике, а именно к электронным моделирукнцим устройствам для определения кратчайшего пути на планарном графе, и может быть использовано, в частности, при расчете транспортной сети. Цель изобретения - сокращение аппаратных затрат за счет представления топологии графа в блоке памяти в виде матриць связи. Для достижения этой цели устройство дополнительно содержит счетчик, схемы сравнения на равенство, схемы сравнения на больше - меньше, элементы И, мультиплексор, распределитель, мультиплексоры перестановки, координат, вычитатель, сумматор и элемент ИЛИ, что позволяет представить исходный граф в блоке памяти в виде Матрицы с S связи вместо матрицы смежности и тем (Л самым значительно уменьшить.объем требуемой памяти. Предлагаемое устройство может быть использовано при расчете транспортной сети. 5 ил.

Фиг.З

Фиг.if