Устройство поиска экстремального пути в графе

 

Изобретение относится к вычислительной технике и может быть использовано для определения экстремальных путей в циклических графах. Для этого исследуемый граф представляют в виде матрицы, значение (К,м)-гр элемента которой (k 2; ...,Н,М 1,...,Н-1, , Н- количество вершин в графе) равно весу дуги соединяющей k-ю и М-ю вершины графа. Используя сложный алгоритм определяют экстремальный путь в графе , при этом, если вес дуги представлен в прямом коде, определяется максимальный , а если в обратном - минимальный путь в графе. Результаты поиска записываются в те ячейки матрицы смежности, которые соответствуют экстремальному пути. Далее, используя шифратор и блок регистров сдвига, записывают номера вершин кратчайшего пути на регистры сдвига блока. 4 ил. i СП со 4;i 05 4

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

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

РЕСПУБЛИН (51)4 G 06 F 15/20

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

К А BTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4035424/24-24 (22) 27.01.86 (46) 30.09.87. Бюл. № 36 (72) С.М.Баженов, С.И.Одинцов и В.А.Титов (53) 681.333(088.8) (56) Авторское свидетельство СССР № 842842, кл. G 06 G 7/122, 1980.

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

¹ 1151979, кл. G 06 F 15/20, 1983. (54) УСТРОЙСТВО ПОИСКА ЭКСТРЕМАЛЬНО-

ГО ПУТИ В ГРАФЕ (57) Изобретение относится к вычислительной технике и может быть использовано для определения экстремальных путей в циклических графах.

Для этого исследуемый граф представ„„SU,14147 А1 ляют в виде матрицы, значение (V,М)-го элемента, которой (K = 2; ,Н, М= 1,...,Н-1, К= М, Н вЂ” количество вершин в графе) равно весу дуги соединяющей K --ю и М-ю вершины графа. Используя сложный алгоритм определяют экстремальный путь в графе, при этом, если вес дуги представлен в прямом коде, определяется максимальный, а если в обратном " минимальный путь в графе. Результаты поиска записываются в те ячейки матрицы смежности, которые соответствуют экстремальному пути. Далее, используя шифратор и блок регистров сдвига, записывают номера вершин кратчайшего пути на регистры сдвига блока. 4 ил.

1 134

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

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

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

Устройство содержит матричную модель 1 графа, образованную наддиагональной и поддиагональной матрицами моделей дуг, каждый узел матричной модели 1 содержит регистры 2 и блок

3 элементов И, группу элементов ИЛИ 4 генератор 5 импульсов, элемент И 6, регистр 7 сдвига, элемент ИЛИ 8,элемент НЕ 9, группу блоков 10 элементов

ИЛИ, две группы элементов И-НЕ 11 и

12, две группы блоков 13 и 14 элементов И, группу сумматоров 15, блок

16 определения максимального кода, блок 17 формирователей пути, группу блоков 18 элементов И-НЕ, группу блоков 19 элементов И, группу регистров

20, вход 2 1 пуска устройства.

Блок 17 формирователей пути содержит блок 22 регистров сдвига, элемент 23 задержки, элемент ИЛИ 24, шифратор 25, группу элементов 26 задержки, группу триггеров 27, группу элементов И 28, группу блоков 29 элементов ИЛИ, матрицу 30 формирователей 31 пути, каждый из которых содержит элементы И 32, 33 и 34 и триггер 35, группу элементов ИЛИ 36, группу триггеров 37, группу элементов

И 38, информационные входы 39 и 40 блока 17 формирователей пути, тактовый вход 41 блока 17 формирователей пути.

Устройство работает следующим образом.

Пусть требуется определить максимальный путь в графе, представленном на фиг. 3. Указанный граф можно задать матрицей смежности (фиг. 3), 1647 2 где м =. 1,...,4. К = 1,..., 4 — номера вершин графа, (м, K)-е (@+K) элементы матрицы — веса соответствующих дуг графа (если какая-либо из дуг с> графа отсутствует, то на соответствующее ей место записывается код нуля) .

Алгоритм поиска можно разделить на три этапа.

Первый этап заключается в просмотре первой строки матрицы 1 с целью обнаружения в ней значащих кодов (см. фиг. 4). Эти коды записываются в матрицу — столбец 2 по следующему правилу: если в (1.К) ячейке матрицы

1 есть значащий код (не равный нулю), то он переписывается в ячейку матрицы столбца 2.1. В результате выполнения первого этапа получим матрицу (2.1) .

-На втором этапе происходит исправление матрицы (2.1) и формирование матрицы путей (3). Корректировка мат25 рицы (2.1) произвоцится следующим образом. Производится поочередный просмотр столбцов, начиная с второго столбца матрицы (1). Все значащие коды, обнаруженные во втором столбдд це матрицы 1 складываются с соответствующими им значащими кодами матрицы (2.1) (исключение составляет лишь первая строка матрицы (1), ее значащие коды суммируются с нулем), из полученных сумм выбирается максималь35 ная и записывается в качестве второго элемента матрицы (2.2). Пусть в нашем примере о+ 0>A+a, тогда вторым элементом матрицы (2.2) станет сумма +О, при этом в матрице путей (3) элемент (1.2) станет равным единице (так как максимальный элемент найдет в первой строке при просмотре второго столбца матрицы (1). Это говорит дб о том, что максимальный путь из первой вершины во вторую равен а . Следующим просматривается третий столбец матрицы (1). Для данного столбца + 0 (б+ а . Третий элемент матрицы (2.2) станет равным (б +с ), а элемент

50 (2. 3) матрицы (3) станет равным единице. После просмотра четвертого столбца получим суммы в+и, 3 + 6 +a пусть ь+а д+ +а, тогда четвертый элемент матрицы (2.2) будет равен

55 (ь+а), а элемент (2.4) матрицы (3) станет равным единице.

Третий этап заключается в просмотре сформированной матрицы (3). Пра1341647 вило, которого необходимо придерживаться при определении вершин, через которые проходит максимальный путь, следующее — просмотр начинается с

5 последнего столбца, т.е. с четвертого столбца матрицы, при обнаружении в нем единицы осуществляется переход на просмотр столбца с номером, равным номеру строки, в которой была обнаружена единица. Просмотр столбцов производится до тех пор, пока не будет обнаружена единица в первой строке матрицы. Причем номера строк, в которых обнаружены единицы, запоминаются, так как они определяют вершины графа, через которые проходит максимальный путь. Таким образом, зафиксировав четвертую вершину (в нее определяют максимальный путь), начнем просмотр матрицы (3). Элемент (2.4) этой матрицы равен единице: зафиксировав число 2, нечнем просмотр второго столбца, в нем элемент (1.2) равен единице. Таким образом, 25 искомый путь проходит через вершины графа 1.2.4 и равен в + а . Однако следует иметь ввиду, что при описании алгоритма мы пользовались допущениями. Исходя из этого необходимо отметить, что максимальный путь может быть выбран из следующей совокупности путей в зависимости от весов дуг графа: 1.2.3.4 1.3.2.4. 1.2.4. 1.3.4.

Рассмотрим работу устройства при35 менительно к поиску минимального пути в графе. В исходном состоянии на регистры 2 модели 1 заносятся обратные коды весов соответствующих дуг графа, в младшем разряде регистра

7 записана единица, триггеры регистров 20 находятся в единичном состоянии, на втором регистре сдвига блока 22 записано число н — количество вершин графа триггеры 27 установлеЭ

45 ны в единичное состояние, а триггеры 35 формирователей 31 матрицы 30 в нулевое состояние, триггер 37 х— в единичное состояние, где х — номер вершины, в которую необходимо опре50 делить экстремальный путь из первой вершины. Цепи установки и занесения кодов весов дуг графа не показаны.

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

Устройство начинает работу после подачи единичного сигнала на вход 21 устройства. Этим сигналом открывается элемент И 6, и импульсы генератора 5 начинают поступать в цепи сдвига регистра 7. По первому импульсу с генератора 5 единица, записанная в нулевом (младшем) разряде регистра

7, переписывается в первый разряд. С

I выхода первого разряда регистра 7 единичный сигнал поступает на первый вход первого элемента ИЛИ 4, с выхода которого единичный сигнал поступает на первые входы блоков 3 элементов и блоков 18 и через элемент ИЛИ 8 на управляющие входы блоков 19 элементов И. Блок 18 элементов И-НЕ открывается и на первыи регистр 20 осуществляется прием обратного кода максимального числа с выхода блока 16.

Код числа с выхода регистра 20 к (к = 1,..., n — 1) через соответствующий элемент И 19 к поступает на входы элементов И-НЕ 12ки блок 13к элементов И. Если данный код не равен обратному коду нуля, то на выходе элемента И-НЕ 12 к формируется единич- . ный сигнал, которым открывается блок 14к элементов И, в противном случае он будет закрыт. Кроме того, коды весов дуг графа, записанные на регистры 2м,4, через открытые блоки

Зм, < (м = 1,..., и — 1) элементов и через соответствующие блоки 10 к элементов ИЛИ поступают на элементы

И-HE 11к и И 14к . Если код веса, поступивший с выхода регистра 2к, отличается от обратного кода нуля, то единичным сигналом с выхода элемента И-HE 11 открывается блок 13к элементов И и код числа с выхода регистра 20 поступает на второй вход сумматора 15 к.

Таким образом, на входы сумматора

15 могут поступить коды весов дуг графа (с регистра 2 k) и код числа (с регистра 20 к) только в том случае, если они оба отличны от обратного кода нуля.

С выхода сумматора 15 полученная сумма поступает на -й вход блока 16.

Блок 16 производит поиск максимального кода и вырабатывает единичный сигнал на выходе, соответствующем номеру входа с максимальным кодом. Максимальный код поступает на блоки 18 элементов И-НЕ, а выходы, указываю134164 щне его позиционный номер — на вход блока 17.

Устройство работает аналогично

4 до поступления (и-1)-ro импульса с

15 выхода генератора 5. По этому сигналу опрошен (H 1) столбец модели 1, произведено суммирование значащих кодов, блоком 16 выбрана максимальная из полученных сумм и код этого числа записан на соответствующий регистр

20 ° На этом первый этап определения минимального пути заканчивается.

Второй этап начинается с приходом

М-ro импульса от генератора 5. По этому сигналу (как и на первом этапе) производится опрос первого столбца модели 1, суммирование значащих кодов весов дуг и соответствующих кодов экстремальных путей, хранящихся на регистрах 20. В блоке 16 выбирается минимальная из полученных сумм, код числа этой суммы записывается в соответствующий регистр 20. Кроме того, управляющий сигнал поступает на пер- 25 вый вход 39 блока 17, а на один из входов 40, определяющий позиционный номер максимального кода, подается единичный сигнал. По этим сигналам устанавливается в единичное состоя- зп ние триг.гер 35 одного из формирователей 31. По очередным тактовым импульсам работа блока 16 осуществляется аналогичным образом.

На к -м шаге работы нторого этапа

35 опрашивается k -й столбец модели 1, производится сложение кодов с выхода регистров 2м, к с соответствующими кодами чисел с регистров 20м, из полученных кодов сумм н блоке 16 выбирается максимальная сумма (пусть она подается на первый вход блока 16), Этот код записывается на регистр 20ККроме того, устанавливается в единичное состояние триггер 35 формиро45 вателя 31м,к сигналами, поступающими по входам 39 к и 40м. Далее устройство функционирует аналогично.

После (Н-1)-ro шага второго этапа

50 устройство находится в следующем состоянии. На регистре 20к записывается код числа, определяющего экстремальный путь из первой вершины н К-ю, В матрице 30 размещается матрица смежности графа, причем в единичное состояние установлены триггеры 35 только тех дуг графа, через которые проходит экстремальный путь.

На Н -м шаге второго этапа производится определение номеров вершин, через которые проходят экстремальный путь. Единичный сигнал с выхода регистра 7 поступает на вход элемент НЕ 9, после чего закрывается элемент И 6. Кроме того, единичный сигнал по входу- 4 1 поступает на входы элементов И 38 и через открытый элемент И 38 х — на первые входы элементов И и 34 33 формирователя 31

1, х . После того, как найден формирователь 31 к, х, триггер 35 которого установлен и единичное состояние, с выхода элемента И 34 через элемент ИЛИ 29к и элемент И 28 к единичный сигнал поступает на элемент

26к задержки и k -й вход шифратора

25. Шифратор 25 преобразует позиционный код номера строки в двоичный код, который записывается в первый регистр блока 22. Элемент 26к задержки задерживает распространение единичного сигнала на время срабатывания шифратора. С выхода элемента 26к задержки единичный сигнал поступает на вход элемента ИЛИ 24 и устанавливает в нулевое состояние триггер 27к с выхода которого нулевой сигнал закрывает элемент И 28 к. С выхода элемента ИЛИ 25 единичный сигнал поступает через элемент 23 задержки в цепи сдвига всех регистров блока 22, освобождая первый регистр блока 22 для приема очередного номера вершины.

Кроме того, сигнал с выхода элемента

26 задержки поступает через элемент

ИЛИ Збк на опрос s -го столбца матрицы 30. Блок 17 функционирует аналогично до тех пор, пока не будет найден блок 31 1к. При этом на первый регистр блока 22 записывается единица (номер начальной вершины).

Для определения минимального пути в графе веса дуг заносятся на регистры матрицы 1 в обратном коде, а для определения максимального пути — н прямом коде. Во втором случае, так же как и в первом, при отсутствии пути из k-й вершины графа в м-ю íà kM -й регистр модели 1 заносится обратный код нуля.

На этом процесс поиска экстремального пути в графе заканчивавается.

Таким образом, на регистр 20к записан вес экстремального пути из первой вершины графа в к-ю, а на регис "".рах блока 22 записаны номера вершин, 7 134 ч< рез которые проходит экстремальный путь, причем экстремальных путей для графа может быть несколько. 647 8 входу блока элементов И того жс узла поддиагональной матрицы моделей дуг, причем выход элемента И подключен к

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

Устройство поиска экстремального пути в графе, содержащее генератор импульсов, регистр сдвига, (й-1) блоков элементов ИЛИ, где Н вЂ” количество вершин в графе, (Н-1) регистров, (II — 1) блоков элементов И-НЕ, группу блоков элементов И, (Н-1) сумматоров, элемент И, блок определения максимального кода и наддиагональную матрицу моделей дуг, каждый узел которой содержит блок элементов И и регистр, информационный выход которого подключен к первому входу блока элементов И того же узла наддиагональ.>О ной матрицы модулей дуг, причем вход пуска устройства подключен к первому входу элемента И, второй вход которого подключен к выходу генератора импульсов, выход блока элемен- 25 тов И К-го узла М-й строки наддиагональной матрицы модулей дуг (К вЂ” 1, ..., Н -1, М = 1,..., Н вЂ” 1) подключен к k -му входу M -ro блока элементов

ИЛИ, выход первого блока элементов ЗО

ИЛИ подключен к первому информационному входу блока определения максимального кода, выход Н-го сумматора подключен к (К + 1)-му информационному входу блока определения максимального кода, К-й выход признака

35 максимального кода которого подключен к первому входу К -го блока элементов И-НЕ, выход. которого подключен к информационному входу К -ro регистра, выход которого подключен к первому входу k-го блока элементов

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

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

ИЛИ, элемент НЕ, блок формирователей пути и поддиагональная матрица моделей дуг, каждый узел которой содержит блок элементов И и регистр, выход которого подключен к первому входу признака сдвига регистра сдвига, k-é разряд информационного выхода которого подключен к первому входу

k -го элемента ИЛИ группы, выход которого подключен к K -му входу элемента ИЛИ, к вторым входам блоков элемен. тов И всех узлов к -го столбца поддиа,гональной матрицы моделей дуг, к вторым входам блоков элементов И всех узлов k -ro столбца наддиагональной матрицы моделей дуг, к второму входу

9-го блока элементов И-НЕ и к входу признака записи k -ro регистра, (Н-1+V) é разряд информационного выхода регистра сдвига подключен к второму входу K --го элемента ИЛИ и к

К-му информационному входу первой группы блока формирователей пути (2Н-1)-й разряд информационного выхода регистра сдвига подключен к так— товому входу блока формирователей пути и к входу элемента НЕ, выход которого подключен к третьему входу элемента И, выход блока элементов И К -ro узла М-й строки поддиагональной матрицы моделей ребер подключен к (Н-М+к) — му входу (М+ 1)-го блока элементов ИЛИ группы, выход Т -го блока элементов ИЛИ (Т = 2,...,Н) подключен к входу (Т-1)-го элемента И-НЕ первой группы и к первому входу (Т-I)-го блока элементов И второй группы, выход которого подключен к входу первого слагаемого (Т-1)-ro сумматора, выход К-го элемента И-НЕ первой группы подключен к первому входу К -го блока элементов И третьей группы, выход которого подключен к входу второго слагаемого V го сумматора, выход элемента ИЛИ подключен к второму входу К -го блока элементов И первой группы, выход которого подключен к второму входу E -го блока элементов И третьей группы и к входу К -го элемента И-HE второй группы, выход которого подключен к второму входу h --го блока элементов И второй группы, K-й информационный выход блока определения максимального кода подключен к

К -му информационному входу второй группы блока формирователей пути.

1341647

1341647 сне 3

Пгрбмй эяал

Z а (7) Фиг. Ф

Корректор 11.Пожо

Подписное

4/5

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

Составитель А.Иишин редактор М.Дылын Техред,дидык

Заказ 4438/53 Тираж 672

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

113035, Москва, Ж-35, Раушская наб., д. г п

Паюгаюр мрже аа сагарйга

3 б а а о а вк фасжщо 7 g ч. лА мгага ondyа а

Ю бга