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

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

Иллюстрации

Показать все

Реферат

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU„„1265790 A 1 (5D 4 G 06 F 15/20

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ (21) 3669493/24-24 (22) 30.11.83 (46) 23.10.86. Бюл. 9 39 (71) Ленинградский институт авиационного приборостроения (72) М. Б. Игнатьев, В. И. Петров. и В. Е. Сорокин (53) 681.333(088.8) (56) Авторское свидетельство СССР

М 525954, кл. 0 06 F 15/20, 1974.

Авторское свидетельство СССР

У 851411, кл. G 06 F 15/20, 1979. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

КРАТЧАЙШЕГО ПУТИ НА ДВУМЕРНОМ РЕШЕТЧАТОМ ГРАФЕ (57) Изобретение относится к вычислительной технике, а именно к электронным моделирующим устройствам для определения кратчайшего пути на планарном графе, и может быть использовано, в частности, при расчете транспортной сети. Цель изобретения — сокращение аппаратных затрат за счет представления топологии графа в блоке памяти в виде матрицы связи. Для достижения этой цели устройство дополнительно содержит счетчик, схемы сравнения на равенство, схемы сравнения на больше — меньше, элементы И, мультиплексор, распределитель, мультиплексоры перестановки координат, вычитатель, сумматор и элемент ИЛИ, что позволяет представить исходный граф в блоке памяти в виде матрицы связи вместо матрицы смежности и тем самым значительно уменьшить .объем требуемой памяти. Предлагаемое устройство может быть использовано при, расчете транспортной сети. 5 ил.

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

65/90 2

1 12

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

Цель изобретения — сокращение аппаратных затрат за счет представле-, ния топологии графа в блоке памяти в виде матрицы связи.

На фиг. 1 изображена структурная схема устройства для определения кратчайшего пути на двумерном решетчатом графе; на фиг. 2 — пример выполнения одного разряда мультиплексора перестановки координат; на фиг. 3-5 соответственно пример транспортной сети промьппленных транспортных роботов; граф, являющийся моделью этой транспортной сети; преобразованный граф.

Устройство для определения кратчайшего пути на двумерном решетчатом графе (фиг. 1) содержит генератор 1 импульсов, первый — четвертый регистры 2-5 соответственно, первый— пятый счетчики 6-10 соответственно, первый и второй регистры ll и 12 промежуточных результатов соответственно, блок 13 памяти, сумматор 14, триггер 15, первую — пятую схемы 1620 сравнения на равенство соответственно,.первую и вторую схемы 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 и вторым входом

55 второго элемента 2-2И-ИЛИ 35. Выход элемента НЕ 33 подключен к третьим входам первого и второго элементов

2-2И-ИЛИ 34 и 35.

Графовые модели используются очень широко, в том числе в качестве моделей транспортных сетей. Плоские транспортные сети, а также пространственные сети, графы которых не содержат полного пятивершинного и полного двудольного шестивершинного подграфов, могут быть представлены в виде планарного графа. Следовательно, широкий класс транспортных сетей может иметь своей моделью планарный граф. Планарный граф можно преобразовать в подграф двумерного решетчатого графа, вершинами которого являются упорядоченнь|е пары чисел (i, j), где i=1 m,)=1,п, называемые координатами вершин. Для этого вводятся фиктивные вершины при последовательном разбиении ребер и при уменьшении степеней вершин. В первом случае вес одного из образованных ребер равен весу разбиваемого ребра, а вес остальных образованных ребер равен О.

Во втором случае одна вершина представляется несколькими вершинами таким образом, что сумма их степеней без учета ребер, инцидентных только им и имеющих веса О, равна степени представляемой вершины. Информация о полученном таким образом графе предварительно записывается в блоке памяти в виде матрицы связи С, каждая строка которой содержит три элеменТа j С g(и С y - номера Вершин инци дентных.к-му ребру, С вес < --ro ребра. Если в графе N вершин, N — число фиктивных вершин, X — - коэффициент средней степени вершин графа, то для представления графа матрицей смежности А и матрицей связи С потребуются соответственно объемы памяти N и Мр

NA =N (1), (2), N N (3)

Н 3 х(Н+М )

В конечном двумерном решетчатом

N 11 графе х(4 и - -» — — -. Таким обра1 1с 6(N+N ) зом, в тех случаях, когда число фик1 тивных вершин по отношению к числу вершин невелико, а число последних достаточно велико, объем памяти, требуемый Для представления графа матри1265790 цей связи, значительно меньше объема памяти, требуемой для представления графа матрицей смежности. Поскольку основной объем аппаратных затрат приходится на блок памяти для представления топологии графа, то замена представления графа матрицей связи вместо матрицы смежности позволит значительно сократить объем оборудования устройства поиска кратчайшего fO пути на графе.

На предлагаемом устройстве последовательно генерируются пути, у которых монотонно изменяется хотя бы одна координата. Пути представляются в одной из двух форм:

1) (О,, )-(1, q )-(1, 1 )-...—

-(1, j )-(2, J )-...-(2, j )-...—

2) (i;, o)-(i;,1)-(, 1)-".— 20

-(i,, 1)-(i,, 2)-...-(i >, 2)-...—

-(i„";, п-1)-(i„, n), где r и P — число ребер в пути, инциндентные вершины которых имеют координаты =9 и 1=з соответственно 2S

41

Ч

Для путей, записанных в первой форме, монотонно изменяется координата, второй — 1.

Каждый путь однозначно определяется множеством координат:

) (.,,,,, ° .i .,, ij1 ) : : ".<- -3.

При. выполнении полного перебора в

35 этих множествах координат Анерируются все пути. При этом определяющими путь вершинами являются:

1) (О, q ), (1, q ), (1, g" ), (m+1, ); (4 ° 2)) ")(i ) )(i ", ri)) (1„„, n+1

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

Веса всех существующих путей сравниваются и путь с минимальным весом 55 ,является кратчайшим.

Перед началом работы во второй регистр 3 заносятся две кочечные вершины, между которыми ищется кратчайший путь, а в блоке 13 памяти зано-и сится матрица связи преобразованного графа. Сначала записываются ребра, у вершин которых одинаковое значение i а значение j возрастает, затем аналогично для следующих значений i, После этого подобным образом записываются ребра, у вершин которых одинаковое значение

После запуска генератора 1 импуль сов .с его выхода импульсы поступают на вход первого счетчика 6, с первого (параллельного) выхода которого код адреса поступает на первый (адресный вход блока 13 памяти, после полного просмотра которого со второго) последовательного (выхода первого счетчика 6 подается импульс, увеличивающий на I содержимое второго счетчика 7, в котором содержится код первой координаты вершин, и сдвигающий содержимое первого ре .истра 2 .

Разрядность первого счетчика 6 равна разрядности кода адреса блока 13 памяти, а сдвиг содержимого первого ре. гистра 2 осуществляется каждый раз на число разрядов, отводимых под хранение кода одной координаты. Для этого первый регистр 2.может быть организован из параллельно включенных регистров, число которых равно числу разрядов. С второго (последовательного) выхода второго счетчика

7 после полного пересчета подается импульс, сбрасывающий триггер 1$ и увеличивающий на 1 содержимое пятого счетчика 10 все разряды которого, кроме двух старших, при этом записываются в первый регистр 2. Эти разряды содержат множество кодов вторых координат, однозначно определяющих путь. Следующий за ними разряд с третьего выхода пятого счетчика 10 подается на управляющие входы первого и второго мультиплексоров 24 и 25 перестановки координат, на информационные входы которых подаются соответственно содержимое второго регистра 3 и блока 13 памяти для установления соответствия между первой и второй координатами i u j-в зависимости от формы представления пути.

Старший разряд пятого счетчика 10, служит для отключения генератора и останова устройства после генерации всех путей. В первом регистре 2 хранятся коды вторых координат, а с первого (параллельного) выхода

1265790 второго счетчика 7 снимается код первой координаты. С выхода второго мультиплексора 25 перестановки координат снимаются коды координат вершин ребер, которые хранятся в блоке !3 памяти. С выхода первого мультиплексора 25 перестановки координат в соответствующем виде коды координат конечных вершин поступают íà !б вход третьей схемы 18 сравнения на равенство, на другие входы которой поступают код координаты с выхода мультиплексора 27 и код второй координаты. При совпадении сгенерированной вершины с любой из конечных вершин на выходе этой схемы появляется единичный сигнал, который поступает на второй вход триггера 15. На входы первой схемы 16 сравнения на равенст- 2б во поступают: коды координат вершин ребер, первой и второй координат и уменьшенной на 1 первой координаты в сумматоре 18 уменьшения на 1, на входы которого подаются код первой 25 координаты и код 1. В этой схеме происходит обнаружение ребер вида (9-1 д ) †(Я i ) и (1 " 3-1)-(i,, s).

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

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

В этой схеме производится обнаружение ребер вида (1,,1 )-(с, J ) и (1, з)Сигнал с выхода этой схемы поступает на второй (счетный) вход шестого счетчика 23 и второй вход элемента KIH 30. Когда триггер 15 взведен и на выходе первой или второй схем

16 и !7 сравнения на равенство появляется единичный сигнал, с выхода второго элемента И 32 лоступает сигнал на входы записи первого и второго регистров 11 и 12 промежуточного результата, в первый из которых, построенный как стековый регистр, последовательно записываются коды

1 вершин ребер из блока 13 памяти, а во второй записывается значение из сумматора 14, на второй вход которого поступает значение веса ребра из блока 13 памяти, а на первый — предыдущее значение, содержащееся во втором регистре 12 промежуточного результата, которое поступает также на второй вход (данных) четвертого регистра 5 и второй вход первой схе- ,мы 21 сравнения на больше — меньше, на первый вход которой поступает содержимое четвертого регистра,5 ° Выход первого регистра 11 промежуточного результата соединен с вторым входом (данных) третьего регистра 4. На второй вход пятой схемы 20 сравне- ния на равенство поступает содержимое шестого счетчика 23. При совпадении значений на входах схемы 20 сравнения на равенство подается сигнал на первый вход (обнуления) шестого счетчика 23 и на второй (счетный) вход четвертого счетчика 9. Со1265790 держимое третьего и четвертого счетчиков 8 и 9 поступает соответственно на второй и третий входы четвертой схемы 19 сравнения на равенство, на первый вход которого поступает код 5 первой координаты, а с выхода которой единичный сигнал поступает на первый вход первого элемента И 31, на второй вход которого поступает сигнал с выхода первой схемы 21 срав- 10 нения на больше — меньше, а на третий вход — сигнал.п с первого (инверсного) выхода триггера 15. Таким образом, когда рассмотрение пути закончено, т.е. триггер 15 сброшен, 15 его вес меньше веса пути с минимальным весом из рассмотренных ранее, т.е. на выходе первой схемы 21 сравнения на больше — меньше — единичный сигнал, и все ребра пути существуют, т.е. содержимые третьего и четвертого счетчиков 8 и 9 равны коду первой координаты, с выхода первого элемента И 31 подается сигнал на первые входы (записи) третьего и четвертого регистров м и 5, в первый из которых записываются коды вершин, образующих данный путь, а во второй — вес этого пути. После генерации всех путей .в этих регистрах хранятся соответственно коды вершин, образующих кратчайший путь и его вес.

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

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

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

ИЛИ,. выход которого подключен к вто- рому входу второго элемента И, вы- 10 ход которого соединен с вторым входом первого и первым входом второго регистров промежуточного результата, выход второго регистра промежуточного результата подключен к вторым вхо- 5 дам первой схемы сравнения на больше - меньше и четвертого регистра и к первому входу первого сумматора, выход которого соединен с вторым входом второго регистра промежуточного результата, второй вход первого сумматора соединен с выходами блока памяти, выход первого регистра промежуточного результата подключен к второму входу третьего регистра, первый выход пятого счетчика соединен с первым входом первого регистра, выход которого подключен к второму входу третьей схемы сравнения на равенство, первому входу распре- 30 делителя.и входу второй схемы срав790 10 нения на больше — меньше, выход которой соединен с вторым входом распределителя, первый выход которого подключен к первому входу пятой схемы сравнения на равенство, выход которой соединен со счетными входами четвертого и шестого счетчиков, выход шестого счетчика соединен с вторым входом пятой схемы сравнения на равенство, третьим входом второй схемы сравнения на равенство и входом второго сумматора, выход которого подключен к четвертому входу второй схемы сравнения на равенство, выход которой соединен с вторым входом элемента ИЛИи упI равляющим входом шестого счетчика, вход начальной установки которого подключен к второму выходу распределителя, выход вычитателя соединен с четвертым входом первой схемы сравнения на равенство, управляющим входом четвертого счетчика и управляющим входом мультиплексора, выход которого подключен к третьему входу .третьей схемы сравнения на равенство, а выходы третьего и четвертого регистров являются выходами устройства для фиксации кодов вершин кратчайшего пути.! 265790

О 1 2 3 9 5 б 7 8 У 10

О

Составитель С, Назаров

Редактор А. Ворович Техред И.Ходанич Корректор М. Максимишинец

Заказ 5666/47 Тираж 671 Подписное

ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4