Устройство поиска экстремального пути в графе Советский патент 1987 года по МПК G06F15/173 

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

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

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

Устройство содержит матричную модель 1 графа, образованную наддиаго- нальной и поддиагональной матрицами моделей дуг, каждый узел матричной . модели 1 содержит регистры 2 и блок 3 элементов И, группу элементов ИЛИ генератор 5 импульсов, элемент И 6, регистр 7 сдвига, элемент ИЛИ iB,элемент НЕ 9, группу блоков 10 элементо ИЛИ, две группы элементов И-НЕ 11 и 12, две группы блоков 13 и 14 элементов И, группу сумматоров 15, блок 16 определения максимального кода, блок 17 формирователей пути, группу блоков 18 элементов И-НЕ, группу блоков 19 элементов И, группу регистров 20, вход 21 пуска устройства.

Блок 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),

10

15

20

где /м- 1,,..,4. К 1,..., 4 - номера вершин графа, (/И, к)-е (А1+к) элементы матрицы - веса соответствующих дуг графа (если какая-либо из дуг графа отсутствует, то на соответствующее ей место записывается .код . нуля).

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

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

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

(2.2)станет равным (d+a), а элемент

(2.3)матрицы (3) станет равным единице. После просмотра четвертого столбца получим суммы-в + а, d+S+a, пусть б + сч-)( , тогда четвертый элемент матрицы (2.2) будет равен (ь+а), а элемент (2.4) матрицы (3) станет равным единице.

Третий этап заключается в просмотре сформированной матрицы (3). Пра30

35

40

45

50

55

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

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

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

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

IQ 15 20 25 зо

35

0

5

0

5

Устройство начинает работу после подачи единичного сигнала на вход 21 устройства. Этим сигналом открывается элемент И 6, и импульсы генератора 5 начинают поступать в цепи сдвига регистра 7. По первому импульсу с генератора 5 единица, записанная в нулевом (младшем) разряде регистра 7, переписывается в первый разряд. С выхода первого разряда регистра 7 / единичный сигнал поступает на первьй вход первого элемента ИЛИ 4, с выхода которого единичный сигнал поступает на пе-рвые входы блоков 3 элементов и блоков 18 и через элемент ИЛИ 8 - на управляющие входы блоков 19 элементов И. Блок 18 элементов И-НЕ открывается и на первый регистр 20 осуществляется прием обратного кода максимального числа с выхода блока 16. Код числа с выхода регистра 20 к (k 1,...,и- 1) через соответствующий элемент И 19k поступает на входы элементов И-НЕ 12ки блок 13к элементов И. Если данный код не равен обратному коду нуля, то на выходе элемента И-НЕ 12 k формируется единич- . . ный сигнал, которым открывается блок элементов И, в противном случае он будет закрыт. Кроме того, коды весов дуг графа, записанные на регистры 2л1, , через открытые блоки Зл(,-((м 1,..., н- 1) элементов и через соответствующие блоки 10k элементов ИЛИ поступают на элементы И-НЕ 11ч и И 14k . Если код веса, поступивший с выхода регистра 2k, отличается от обратного кода нуля, то единичным сигналом с выхода элемента И-НЕ 11k открывается блок 13к элементов И и код числа с выхода регистра 20 поступает на второй вход сумматора 15k.

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

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

б На И-м таге второго этапа прощие его позиционный номер блока 17,

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

Второй этап начинается с приходом М-го импульса от генератора 5. По 15 Рого установлен в единичное состоя- этому сигналу (как и на первом этапе) ние, с выхода элемента И 34 через производится опрос первого столбца элемент ИЛИ 29к и элемент И 28 к еди- модели 1, суммирование значащих ко- ничный сигнал поступает на элемент доз весов дуг и соответствующих кодов 26k задержки и вход шифратора экстремальных путей, хранящихся на 20 25 преобразует позицион- регистрах 20. В блоке 16 выбирается минимальная из полученных сумм, код числа этой суммы записывается в соответствующий регистр 20. Кроме того.

изводится определение номеров вершин, через которые проходят экстремальный путь. Единичный сигнал с выхода регистра 7 поступает на вход элемент НЕ 9, после чего закрывается элемент И 6. Кроме того, единичный сигнал по входу 41 поступает на входы

ментов И и 34 33 формирователя 31 1, X . После того, как найден формирователь 31 к , X , триггер 35 котоный код номера строки в двоичный код, который записывается в первый регистр блока 22. Элемент 26k задержки задерживает распространение едиуправляющий сигнал поступает на пер- 25 ничного сигнала на время срабатывавый вход 39 блока 17, а на один из входов 40, определяющий позиционный номер максимального кода, подается единичный сигнал. По этим сигналам

устанавливается в единичное состоя- зо выхода которого нулевой сигнал зание триггер 35 одного из формирователей 31. По очередным тактовым импульсам работа блока 16 осуществляется аналогичным образом.

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

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

35

40

45

50

крывает элемент И 28 к. с выхода элемента ИЛИ 25 единичный сигнал поступает через элемент 23 задержки в цепи сдвига всех регистров блока 22, освобождая первый регистр блока 22 для приема очередного номера вершины. Кроме того, сигнал с выхода элемента 26 задержки поступает через элемент ИЛИ 36k на опрос к-го столбца матрицы 30. Блок 17 функционирует аналогично до тех пор, пока не будет найден блок 31 1к. При этом на первый регистр блока 22 записывается единица ( номер начальной вершины). Для определения минимального пути в графе .веса дуг заносятся на регистры матрицы 1 в обратном коде, а для определения максимального пути - в прямом коде. Во втором случае, так же как и в первом, при отсутствии пути из k-й вершины графа в м-ю на КМ -и регистр мЪдели 1 заносится обратный код нуля.

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

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

б На И-м таге второго этапа проэлементов И 38 и через открытый эле- мент И 38 дг - на первые входы эле-

изводится определение номеров вершин, через которые проходят экстремальный путь. Единичный сигнал с выхода регистра 7 поступает на вход элемент НЕ 9, после чего закрывается элемент И 6. Кроме того, единичный сигнал по входу 41 поступает на входы

элементов И 38 и через открытый эле- мент И 38 дг - на первые входы эле-

Рого установлен в единичное состоя- ние, с выхода элемента И 34 через элемент ИЛИ 29к и элемент И 28 к еди ничный сигнал поступает на элемент 26k задержки и вход шифратора 25 преобразует позицион

ментов И и 34 33 формирователя 31 1, X . После того, как найден формирователь 31 к , X , триггер 35 котоРого установлен в единичное состоя- ние, с выхода элемента И 34 через элемент ИЛИ 29к и элемент И 28 к еди- ничный сигнал поступает на элемент 26k задержки и вход шифратора 25 преобразует позицион-

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

выхода которого нулевой сигнал за

крывает элемент И 28 к. с выхода элемента ИЛИ 25 единичный сигнал поступает через элемент 23 задержки в цепи сдвига всех регистров блока 22, освобождая первый регистр блока 22 для приема очередного номера вершины. Кроме того, сигнал с выхода элемента 26 задержки поступает через элемент ИЛИ 36k на опрос к-го столбца матрицы 30. Блок 17 функционирует аналогично до тех пор, пока не будет найден блок 31 1к. При этом на первый регистр блока 22 записывается единица ( номер начальной вершины). Для определения минимального пути в графе .веса дуг заносятся на регистры матрицы 1 в обратном коде, а для определения максимального пути - в прямом коде. Во втором случае, так же как и в первом, при отсутствии пути из k-й вершины графа в м-ю на КМ -и регистр мЪдели 1 заносится обратный код нуля.

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

Таким образом, на регистр 20к записан вес экстремального пути из первой вершины графа в U-ю, а на регистрах блока 22 записаны номера вершин.

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

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

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

элементов И того же узла наддиагональ-2о рому входу К-го элемента ИЛИ и к

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

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

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

5

К-МУ информационному входу первой группы блока формирователей пути (2Н-1)-и разряд информационного выхода регистра сдвига подключен к так- 5 товом входу блока формирователей пути и к входу элемента НЕ, выход которого подключен к третьему входу элемента И, выход блока элементов И К-го узла М-й строки поддиагональной матрицы моделей ребер подключен к (Н-.м+к)-му входу (М+ 1)-го блока элементов ИЛИ группы, выход Т-го блока элементов ИЛИ (т 2,.,.,Н) подключен к входу (т-1)-го элемента И-НЕ первой группы и к первому входу (т-1)-го блока элементов И второй группы, выход которого подключен к входу первого слагаемого (т-1)-го сумматора, вьрсод К-го элемента И-НЕ первой группы подключен к первому входу k-го блока элементов И третьей группы, выход которого подключен к входу второго слагаемого К-го сумматора, выход элемента ИЛИ подключен к второму входу К-го блока элементов И первой группы, выход которого подключен к второму входу F -го блока элементов И третьей группы и к входу К-го элемента И-НЕ второй группы, выход которого подключен к второму входу К-го блока элементов И второй группы, К-и информационный выход блока определе- . ния максимального кода подключен к К -му информационному входу второй группы блока формирователей пути.

0

5

0

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

39п

.f

fff

П(р6ыи зтоп

(П

(2.)

13

Редактор М.Дылын

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

Заказ 4438/53 Тираж 672Подписное

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

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

фиг.д

тт

Првеметр mptfmtto cmuifutj

Лроснотр

vfrnt moM

emoafftfo

{г.2

(3.3}

r-.«)

фиг. ii

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