Устройство для решения задач на графах

 

Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графах. Целью изобретения является повышение быстродействия устройства при решении задачи определения кратчайшего пути в графе со взвешенными вершинами. Устройство содержит блок 46 задания матрицы смежности, блок 47 определения кратчайшего маршрута, регистр 48, коммутатор 49 смежных вершин, многоканальный накапливающий блок 50 выбора минимальной суммы, входы 51 задания весов вершин устройства, входы 52 задания начальной вершины устройства, выходы 53 признаков принадлежности дуг множеству дуг кратчайшего пути устройства, тактовые входы 54, 55 устройства, коммутатор 56 инцидентных дуг и входы 57 задания конечной вершины графа устройства. Перед началом работы обнуляют регистр 48, в блок 46 заносят информацию о топологии графа, в каналы блока 50 заносят коды весов вершин графа, те же коды подают на входы 51. Один из разрядов регистра 48, соответствующий номеру начальной вершины пути, устанавливают по входу 52 в единичное состояние. На входы 54, 55 подают поочередно тактовые импульсы уровня логической единицы. При этом блок 47 формирует на выходах 53 устройства признаки принадлежности дуг множеству дуг кратчайшего пути. 5 ил.

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

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

РЕСПУБЛИН (19) (И) щ) С 06 F 15/20

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

К А8ТОРСНОМУ СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР. (21) 4425141/24-24 (22) 12.05.88 (46) 30.09.90. Бюл. № 36 (71) Институт проблем моделирования в энергетике АН УССР (72) В.В.Васильев и В.Л.Баранов (53) 681.333(088.8) (56) Авторское свидетельство СССР

¹ 1315993, кл. G 06 F 15/20, 1985..

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

¹ 1246110, кл. G 06 F 15/20, 1984. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

НА ГРАФАХ. (57) Изобретение относится к вычислительной технике и может .быть использовано для исследования путей в графах. Целью изобретения является повышение быстродействия устройства при решении задачи определения крат- чайшего пути в графе со взвешенными вершинами. Устроство содержит блок

46 задания матрицы смежности, блок

47 определения кратчайшего маршрута, регистр 48, коммутатор 49 смежных

2 вершин, многоканальный накаплив ающий блок 50 выбора минимальной суммы, входы 51 задания весов вершин устройства, входы 52 задания начальной вершины устройства, выходы 53 признаков принадлежности дуг множеству дуг кратчайшего пути устройства, тактовые входы 54,55 устройства, коммутатор 56;инцидентных дуг и входы 57 задания конечной вершины графа устройства. Перед началом работы обнуляют регистр 48, в блок 46 заносят информацию о топологии графа, в каналы блока 50 заносят коды весов вершин грайа, те же коды подают на входы 51.

Один из разрядов регистра 48, соответствующий номеру начальной вершинь пути, устанавливают по входу 52 в единичное состояние. На входы 54, 55 подают поочередно тактовые импульсы уровня логической единицы. При этом блок 47 формирует на выходах 53 устройства признаки принадлежности дуг множеству дуг кратчайшего пути.5 ил.

1596344

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

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

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

Устройство,.(фиг. 1) содержит регистр 1 сдвига, реверсивный регистр

2 сдвига, сумматор 3, блок 4 управле- 20 ния, триггер 5, группу триггеров

6(1)-6(В), элементы И 7 и 8, две группы элементов И 9 (1)-9 (В) и 10(1)

10(В), элементы ИЛИ 11-13, элемент .И-ИЛИ 14, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 15, 25 элемент ИЛИ-НЕ 16, группу элементов

ИЛИ-HF. 17(1)-17(В), ключи 18 и 19, информационные входы 20(1)-20(В), информационный выход 21, информационные входы 22(1)-22(В) и индикационные выходы 23(1)-23(В), где  — количество вершин в графе.

Блок 4 управления (фиг.2) содержит генератор 24 импульсов, распреде- литель 25 импульсов, генератор 26 одиночных импульсов, коммутаторы 27—

29, триггеры ЗО-, 33, элемент 34 задержки, элементы И 35-39, элементы

ИЛИ 40-42, элемент ИЛИ-НЕ 43, элементы НЕ 44 и 45.

На фиг.5 обозначены блок 46 задания матрицы смежности, блок 47 определения кратчайшего маршрута, регистр 48, коммутатор 49 смежных вер- 45 шин, многоканальный накапливающий блок 50 выбора минимальной суммы,входы 51 задания весов вершин устройства, входы 52 задания начальной вершины устройства, выходы 53 признаков принадлежности дуг множеству дуг кратчайшего пути устройства, пактовые входы 54 и 55 устройства, коммутатор 56 инцидентных дуг и входы

57 задания конечной вершины графа устройства..

На фиг.4а изображен пример графа со взвешенными вершинами, веса кото-, рых указаны внутри обозначения вершины. Начальная вершина обозначена буквой Н, а конечная — буквой К.

Алгоритм поиска кратчайшего пути, на графе фиг.4 заключается в следующем.

Отмечают все вершины, связанные с начальной вершиной. Метка вершин осуществляется квадратом внутри вершины графа. К весу всех отмеченных вершин 8, 7 и 2 прибавляют вес на чального узла, равный единице. Полученную сумму запоминают в отмеченных вершинах 9, 8 и 3. После этих операций завершают первый шаг вычислений, получают граф, изображенный гйа фиг.4б. Дальнейшие вычисления выполняют от всех ранее меченых вершин. Отмечают все вершины графа,связанные дугами с мечеными вершинами на предыдущем шаге вычислений. На втором шаге вычислений метке подлежит конечная вершина и вершина с весом

4. Выделяют минимальную сумму весов из всех меченых ранее вершин, связанных направленными дугами с отмеченными вершийами К и с весом 4.Вершина с весом 4 связана с мечеными вершинами,в которых после первого шага вычислений сумма весов равна 8 и

3 (фиг.4б). Минимальная сумма из 8 . и 3 равна 3. Эта минимальная сумма 3 суммируется с весом вершины 4 и запоминается в ней в виде нового веса

4 .+ 3 = 7 (фиг.4в). Аналогично для конечной вершины следует выбрать ми1 нимальную сумму из двух меченых вершин 9 и 8 ° Минимальная сумма, равная

8, поступающая из всех меченых на первом шаге вершин, суммируется с нулевым весом, конечной вершины и запоминается в ней 8 + 0 = 8. После второго шага внчислений имеем граф, изображенный на фиг.4в. Дуга, соединяющая конечную вершину с вершиной с весом 4, на втором шаге вычислений не учитывалась, так как вершина с весом 4 до начала второго шага вычислений не была мечена.

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

Итак, на третьем шаге вычислений в конечную вершину поступают суммы весовцз вершин 9, 8 и 7 (фиг.4г). Ми1596344 6 нимальная сумма из 9, 8 и 7 равная р го, например, в виде кнопочного пер

7, суммируется с н левым ве ной ве шины и за у пк весом конеч- ключателя) единичного сигна а пк ве — л с выхо р r и запоминается в конеч- да элемента НЕ 44 на вход запуска ной вершине вместо предыьдущего зна- генератора 26 импульсов, который вычения 8, которое сформировалось на деляет из последовательности импульпредыдущем шаге. На этом выч этом вычисления сов выхода элемента И 35, действуюзаканчиваются, так как состояние всех щих с частотой f/2n, одиночный иммеченых вершин не изменяется. пульс, устанавливающий через коммуТаким образом, вес 7 конечной татор 28 триггер 30 в единичное вершины графа после заве авершения вычис- состояние на время n/Е. лений равен длине кратчайшего пути. Х риггер 31 из последовательности

Конфигурация кратчайшего пути оп еу ре- импульсов п-ro разряда распределитеделяется из графа фиг.4г начиная с р фа, «ачиная с ля 25 импульсов формирует две послеконечного узла в оль у, д ль той дуги,по ко- 15 довательности импульсов °

Эти чередующиеся с частотой f/2ï сов, равная 7. Эта дуга сое иняет ко- .Э

° ду ди яет ко- две последовательности импульсов на нечную вершину с вершиной 7 на фиг.4г. Вершина 7 гой к прямом и инверсном выходах триггера иг. г. Вершина 7 дугой кратчайшего 31 определяют два временных цикла пути соединяется с вершиной 3 кото- 2Р работы устройства. Будем считать,что рая соединена дугой с начальной ве ер- последовательность импульсов на шиной Н. Следовательно к атчайший

/ р тчайшии прямом выходе триггера 31 определяпуть на исходном графе (фиг.4а) про- ет первый цикл, а на инверсном выхоходит через вершины 1, 2, 4, 0 и вы- де — второй. Тогда триггер 30, усделен двойными дугами. 25 тановленный в единичное состояние

Генератор 24 импульсов блока 4 уподиночным импульсом в конце второго равления (фиг.2) вырабатывает после- цикла, будет находиться в единичном довательность тактовых импульсов частоты f из кото ых состоянии в течение первого цикла, в тоты, из которых распределитель 25 конце которого он- устанавливается в импульсов формирует и последователь- 30 нулевое состояние импульсом и-го разностей .импульсов частоты f/n сдви- ряда распредел т ?5

У ряда распределителя .5 импульсов. нутых друг. относительно друга на вре- Единичны" .диничный сигнал прямого выхода мя /, где и — количество разрядов триггера 30, .пос, .поступая на вход регистра I сдвига, обеспечивает . В режиме ввода веда узлов графа в запись, начиная с младшего разряда регистр 1 сдвига ко,утатором 28 35 """

У последовательного двоичного кода ве(выполнен, например, в виде переклю- са са узла rpaAa, поступающего с выхода чателя на два положения) блока 4 уп-. эле ИЛИ 40 б 4 элемента блока 4 управления равления подключают выход генератора на вход ввода данных регистра 1 сдви26 одиночных импульсов к входу уста- га 3

4р га. апись двоичного кода в регистр новки в единицу триггера 30. С помо- 1 сдвига осуществляется под действиимпульсов генератора 2 пример, в виде клавишного переключа- импульсов блока 4 управления, постутеля) блока 4 управления задают дво- . лающих н их на вход синхронизации регистичный код веса узла графа. Коммута- ра 1 П р сдвига. осле записи двоичный тор 27 подключает в единичных разря- код веса узл од веса узла графа хранится динамидах двоичного кода веса узла соответ- че кйм б ческйм способом в регистре 1 сдвига ствующие выходы распределителя 25 им- sa счет его циркуляции с выхода регипульсов к входам элемента ИЛИ 40 на ст а 1

Э стра сдвига на его информационный выходе которого формируется после- вход под действием тактовых импульсов довательный двоичный код веса узла. генерат 24 генератора импульсов блока 4 упНапример, если вес узла равен пяти

101, то выходы первого и третьего, разрядов распределителя 25 импульсов В режиме ввода весов триггеры подключаются коммутатором 27 к входам 6(1)-6(В) находятся в нулевом состоэлемента ИЛИ 40.

1 .янии, в которое их устанавливает по

Ввод последовательного двоичного инверсному нулевому входу одиночн и кода веса у зла в и-разрядный регистр импульс генератора 26 одиночных им1 сдвига осуществляется после подачи пульсов, поступающий через элемент с помощью коммутатора 29 (выполненно- HE 45 блока 4 управления. Триггер 5

1596344 устанавливается в нулевое состояние импульсами, действующими на выходе генератора 26 одиночных импульсов блока 4 управления. Триггер 32 блока

4 управления устанавливается в нулевое состояние импульсами первого разряда распределителя 25 импульсов. (Последовательность импульсов выхода элемента И 35, действующая через эле- 10 мент И 38, открытый инверсным выходом триггера 32, устанавливает триггер 33 в нулевое состояние. После записи в первом цикле двоичного. кода веса узла в регистр 1 сдвига этот код во втором цикле нод действием, тактовых импульсов генератора 24 импульсов блока 4 управления записывается, начиная с младшего разряда, через сумматор 4 в реверсивный регистр

2 сдвига.

В режиме моделирования коммутатором 28 блока 4 управления подключают выход генератора 26 одиночных импульсов к единичному входу триггера 33. 25

Начальный узел грайа задают с помощью ключа 18, подключая выход генератора

26 одиночных импульсов блока 4 управления к входу элемента ИЛИ 11. Конечный узел графа задают ключом 19, ко- 30 торый соединяет инверсный выход триггера 33 блока 4 управления с одним из входов элемента ИЛИ 12.

Пуск устройства осуществляют коммутатором 29 блока 4 управления, с

35 помощью которого на вход запуска генератора 26 одиночных импульсов подают сигнал выхода элемента HE 44.

Выходной импульс генератора 26 одиночных импульсов блока 4 управления . поступает через коммутатор 28 на единичный вход триггера 33, устанавливая его в единичное состояние, и через ° ключ 18 модуля, содержащего начальный узел графа, устанавливает триг- 45 гер 5 этого модуля в единичное состояние. Триггер 5 начального узла графа в единичном состоянии снимает блокировку первой и второй групп входов элемента И-ИЛИ 14 блокируя его

У

50 третью группу входов.

Во время первого цикла работы уст% ройства под действием единичного сигнала прямого выхода триггера 31 и последовательности тактовых импульсов генератора 24 импульсов блока 4 уп55 равления из реверсивного регистра 2 сдвига осуществляется сдвиг двоично-. го кода веса начального узла графа, начиная со старшего разряда. Этот двоичиый код, сдвигаемый из реверсивного регистра 2 сдвига старшими разрядами вперед, вновь записывается в реверсивный регистр 2 сдвига по входу записи при сдвиге влево, а также через элемент И-ИЛИ 14 поступает на информационный выход 21 модуля, содержащего начальный узел графа, и далее согласно топологии графа на ин— формационные входы 20(1)-20(В) других модулей моделирующей структуры.

Будем полагать в дальнейшем, что модули, у которых триггер 5 установлен в единичное состояние, находятся в возбужденном состоянии, а модули, содержащие триггер 5 в нулевом состоянии, находятся в невозбужденном состоянии, В невозбужденном состоянии модули вырабатывают на информационном выходе 21 последовательность двойных импульсов, формируемых на выходе элемента ИЛИ 42 блока 4 управления из последовательностей импульсов, которые вырабатываются на выходах элементов И 35 и 37 блока 4 управления. На выходе элемента И 35 блока 4 управления формируется последовательность импульсов n-ro разряда распределителя 25 импульсов, действующая во время второго цикла работы устройства при единичном сигнале на инверсном выходе триггера 31 блока 4 управления. На выходе элемента И 37 действует последовательность импульсов первого разряда распределителя 25 импульсов во время первого цикла работы устройства при единичном сигнале на прямом выходе триггера 31 блока

4 управления.

Таким образом, на выходе элемента

ИЛИ 42 блока 4 управления формируется последовательность двойных импульсов, . действующих в первом разряде первого цикла и в п-м разряде второго цикла работы устройства. Последовательность импульсов выхода элемента ИЛИ 42 блока 4 управления поступает через элементы И-ИЛИ 14 на информационные выходы 21 всех невозбужденных модулей модулирующей структуры, у которых триггер 5 находится в нулевом состоянии.

После установки в единичное состояние триггера 33 блока 4 управления через элемент И 39 начинает поступать последовательность импульсов n-ro раз9

1596344

35 ряда второго цикла, задержанная элементом 34 задержки на длительность тактового импульса генератора 24 импульсов блока 4 управления. Первый .импульс последовательности выхода эле5 мента И 39 блока 4 управления устанавливает триггеры 6(1)-6(В) во всех модулях моделирующей структуры в единичные состояния, при которых снимается блокировка элементов ИЛИ-НЕ

17(1)-17(В), так как на инверсных выходах триггеров 6(1)-6(В) устанавливаются нулевые сигналы. Кроме того, в режиме моделирования, когда триггер 33 блока 4 управления устанавливается в единичное состояние, снимается блокировка элемента ИЛИ-НЕ

43 блока 4 управления со стороны инверсного выхода триггера 33. Управляющая последовательность второго цикла с инверсного выхода триггера 31 блока

4 управления инвертируется элементом ИЛИ-. НЕ 43 блока 4 управления и в виде управляющей последовательности 25 первого цикла поступает на вход элементов И 7 всех модулей моделирующей структуры.

В первом цикле работы устройства в модулях моделирующей структуры,. на информационные входы которых

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

17 формируется единичный сигнал, ко- 40 торый проходит через элемент И 7 на все элементы И 10(1)-10(В) и сбрасывает в нулевые состояния триггеры

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

1 ° ° е,a) е

Во втором цикле работы устройетва модули моделирующей структуры, находящиеся в возбужденном состоянии, выдают из реверсивного регистра 2 сдвига через элементы И-ИЛИ 14 на информационный выход 21 последовательный двоичный код веса, начиная с младшего разряда, т.е. младшими разрядами вперед. Выдача двоичного кода из реверсивного регистра 2 сдвига осуществляется под действием тактовых импульсов генератора 24 импульсов и управляющей последовательности второго цикла, действующей на инверсном выходе триггера 31 блока 4 управления. Наимень- ший последовательный двоичный код, действующий, например, в К-м канале, поступает младшими разрядами вперед через элементы ИЛИ-НЕ 17 (К), ИЛИ 13 и HJIH-НЕ 16 на вход последовательного двоичного сумматора З,на другой, вход которого под действием тактовых импульсов генератора 24 импульсов блока 4 управления сдвигается с выхода регистра 1 сдвига последовательный двоичный код веса узла данного модуля моделирующей структуры. Суьыатор

3 выполняет последовательно во времени, начиная с младшего разряда, суммирование двоичного кода регистра 1 сдвига и наименьшего двоичного кода, поступающего по информационному входу 20 (К). Результат суммирования с выхода сумматора 3 записывается, начиная с младшего разряда, в реверсивный регистр 2 сдвига под действием тактовых импульсов генератора 24 импульсов и управляющей последовательности второго цикла, формируемой на инверсном выходе триггера 31 блока 4 управления.

Причем связь одного из входов элемента ИЛИ-НЕ 16 с прямым входом триггера 31 блока 4 управления обеспечивает передачу кодов через этот элемент только во время второго цикла работы устройства.

Во время передачи наименьшего двоичного кода с информационного входа 20(К) через элементы ИЛИ-HE 17 (K) и ИЛИ 13 в последнем и-м разряде второго цикла происходит установка триггера 5 данного модуля в единичное состояние, т.е. передача возбуждения от одного модуля моделирующей структуры к другому. Действительно, в п-м, (старшем) разряде наименьшего кода содержится нуль, который преобразуется при передаче через элемент ИЛИ-НЕ

17 (К) в единичный сигнал, устанавли-. вающий через элементы И 8 и ИЛИ 11, 1596344

12 триггер 5 данного модуля в .единичное состояние.

В дальнейшем устройство работает аналогичным образом.

Последовательный двоичный код веса

5 нячального узла графа передает воз-. буждение вычислительного процесса на другие модули моделирующей структуры, которые н первом цикле выделяют наименьший двоичный код из всех кодов, действующих на информационных входах 20(1)-20(В), а но втором цикле прибавляют к нажгеньшему двоичному коду вес узла да.иного модуля модели- 15 рующей структуры. Ненозбуждепные модули моделирующей структуры в процессе работы ньдают н первом цикле максимальный двоичный код — единицу в первом (старшем) разряде, поступающуюgp с выхода элемента И 37 блока 4 управления через элеме -. т 42 блока 4 управления и элемент И-ИЛИ 14 на информационный ньгход 21 данного модуля. По- . этому максимальны= двоичные коды, по-25 ступающие от невозбужденных модулей моделирующей структуры на информационные входы 20(1) — 20(В) данного модуля, не влияют на выбор наименьшего двоичного кода из всех кодов, поступающих от возбужденных модулей.

Если на все информационные входы

20(1)-20(В) данного модуля поступаloT максгпгальные двоичные коды от не возбужденных других модулей то дан35 ный модуль остается н ненозбужденНоМ состоянии, так как импульс п ãî разряда второго цикла с выхода элемента И 35, поступая через элемент

ИЛИ 42 блока 4 управления и элемент 40

И-ИЛИ 14 ненозб жденного модуля, проходит по входу 20(К) данного модуля на ньгход элемента ИЛИ-НЕ 17(К) н виде нулевого сигнала, который блокирует элемент И 8 и предотвращает Ус- 45 тановку триггера 5 данного модуля в едигычное состояние. В это время элемент ИЛИ-НЕ 1б блокируется импульсом

n-ro разряда второго цикла, поступающего с выхода элемента И 35 блока 4 управления.

В процессе моделирования триггер

33 блока 4 управления сохраняет единичное состояние, так как в процессе вычислений последовательные двоичные коды, сдвигаемые младшими разрядами вперед с выхода реверсивного регистра 2 сдвига, и двоичные коды, действующие на выходе сумматора 3, различны. Поэтому на выходах элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 15 модулей формируются единичные сигналы, которые поступают на входы элемента

ИЛИ 41 блока 4 управления и через элемент И 36, открытый но втором цикле сигналом инверсного выхода триггера 31, устанавливают триггер 32 в единичное состояние до момента действия импульса n-ro разряда второго цикла на выходе элемента И 35..В результате элемент И 38 во время действия импульса и-го разряда второго цикла закрыт нулевым сигналом инверсного выхода триггера 32, и триггер

33 сохраняет в процессе. вычислений единичное состояние.

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

20(В) такой же наименьший двоичный код, который был вьделен на предыдущем (Р-1)-м шаге вычислений. В каждом модуле моделирующей структуры сумма наименьшего двоичного кода, выделенного по входам 20(1)-20(В), с двоичным кодом веса узла данного мо— дуля, сдвигаемого с выхода регистра 1 сдвига, íà P-м шаге вычислений равна сумме, выделенной на предыдущем (P

-1)-м шаге вычислений и хранящейся и реверсивном регистре 2 сдвига. На вых<--ге элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 15 всех модулей моделирующей структуры действует во время вторых циклов ну-. левые сигналы, и триггер 32 блока 4 управления устанавливается в нулевое состояние импульсом первого разряда распределителя 25 импульсов ° Импульс

n-ro разряда второго цикла, действующий на выходе элемента И 35, устанавливает через элемент И 38 триггер 33 в нулевое состояние. Единичный сигнал, формируемый на инверсном выходе триггера 33 блока 4 управления, поступает через ключ 19 в модуль,содержащий конечный узел графа. Если в этом модуле наименьший двоичный код действует по Т-му входу и триггер 6 (Т) находится в единичном состоянии, то единичный сигнал с выхода ключа 19 проходит через элементы

13

14

1596344

ИЛИ 12, И 9 (К) на индикационный выход 23 (T) и далее поступает на

1 один из индикационных входов 22(1)

22(В) предыдущего модуля моделирующей структуры. Если в этом модуле наименьший двоичный код действует по

К-му входу и триггер 6 (К) находится в единичном состоянии, то единичный сигнал индикации 23 (К) и далее рас- 10 пространяется по модулям моделирующей структуры от конечного узла графа к начальному узлу вдоль кратчайшего пути, 1 оторому соответствует наименьшая сумма весов узлов графа.

Двоичный код, пропорциональный длине кратчайшего пути, формируется в процессе моделирования в реверсивном регистре 2 сдвига модуля, содержащего конечный узел графа. После окончания вычислений наименьшая сумма весов rpaAa между начальным и конечным узлами выдается во время второго цикла под действием тактовых импульсов генератора 24 импульсов блока 4 уп- 25 равления из реверсивного регистра 2 сдвига через элемент И-ИЛИ 14..на информационный выход 21 модуля, содержащего конечный узел графа.

Таким образом, в общем виде работа устройства может быть представлена следующим образом (фиг.5).

Перед началом работы обнуляют регистр 48, в блок 46 задания матрицы смежности заносят информацию о топологии графа, в каналы блока 50 заносят коды весов вершин графа; те же коды подают на входы 51. Один из разрядов регистра 48, который соответствует номеру начальной вершины пути, уста- 40 навливают по входу 52 в единичное состояние. При этом коммутатор 49 выдает на свои выходы состав вершин, смежных с опрошенными, а коммутатор

56 выдает на свой (К,М)-й информацион-45 ный вход (К = 1,...,В; M = 1,...,В) код, поступивший на его К-й информационный вход, если К-й информационный вход подключен и есть разрешение ,на подключение К-го информационного входа на M-й информационный .выход, тем самым на (К,М)-й информационный выход передается вес пути, накопленный К-м каналом блока 50. Через время, достаточное для завершения указанных операций, на вход 55 устройства

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

ИЛИ) информацию, поступившую íà его информационный вход, тем самым в состав достигнутых включаются .новые вершины.

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

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

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

1,...,В, где  — количество вершин в графе) подключен к К-му информационному входу коммутатора смежных вершин и к входу подключения К-го информационного направления коммутатора инцидентных дуг, выход значения (К,M) ão элемента блока задания матрицы смежности (М = 1,...,В) подключен к входам разрешения подключения

К-го информационного входа на М-й информационный выход коммутатора смежных вершин и коммутатора инцидентных дуг и к входу признака наличия (К,M)-, é дуги блока определения кратчайшего маршрута, выход признака принадлежности (К,М)-й дуги кратчайшему маршруту которого является выходом признака принадлежности (К,М)-. и дуги;. множеству дуг кратчайшего пути усдройства, о т л и ч а ю щ е е с я тем, тем, что, с целью повышения быстродей16 t596344

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

К-го канала мндгоканального накапли" вающего блока выбора минимальной суммы, информационный выход К-ro канала которого подключен к К-му информационному входу коммутатора инцидентных дуг, (K,M)-й информационный выход ко- gp торого подключен к К-му входу второго слагаемого М-го канала многоканального накапливающего блока выбора минимальной суммы, К-й выход позиции минимальной суммы M-ro канала которого подключен к входу признака принадлежности (К,М)-й. дуги множеству дуг кратчайшего маршрута блока определения кратчайшего маршрута, M-й вход заданий конечной вершины маршрута которого является M-м входом задания конечной вершины графа устройства, первый и второй тактовые входы которого подключены соответственно к входу . . признака записи регистра и к тактовому входу многоканальноro накапливающего блока выбора минимальной суммы, выход признака отсутствия изменений которого подключен к входу опроса конечной вершины блока определения кратчайшего маршрута.! 596344

15 96344 г, Фие. 4

Составитель А.Мишин

Редактор Л.Веселовская Техред Л.Олийньп< Корректор М.Иароши

Подписное

Заказ 2911

Тираж 567

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ CgCP

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

Произв дственно-издательский комбинат "Патент", r Ужгород, ул. Гагарина, 101