Устройство для исследования путей в графах Советский патент 1982 года по МПК G06F15/173 G06G7/122 

(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ПУТЕЙ В ГРАФАХ

1

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

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

Недостатками устройства $юляются невозможность определить ранние и поздние моменты наступления событий и низкое быстродействие при определении минимального пути.го

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

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

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

Целью изобретения является повышение быстродействия устройства.

Поставленная цель достигается тем, что в устройство, содержащее матрицу (П X п ) триггеров формирования дуг графа и генератор тактовых импульсов, выход которого соединен с первым входом элемента И, второй вход которого является входом в устройство, введены по числу триггеров формирования дуг элементы И дуг, по числу столбцов матрицы элементы ИЛИ, элементы задержки, регистры, первые, вторые и третьи группы элементов И, группа элементов ИЛИ, многовходовый сумматор, узел выбора максимума, дешифратор, элемент НЕ и реверсивный счетчик, вход которого по; ключен к выходу элемента И, третий вход которого через элемент НЕ подключен к выходу устройства и к выходу реверсивного счетчика, выход которого соединен с входом дешифратора, -ый ( 1, 2,..., Ц ), которого подключен через элемент задержки к управляющему входу элемента И первой группы i -го столбца, к управляющему входу элемента И третьей группы i -го столбца и к первым входам элементов И дуг -1 -ой строки, выход каждого триггера формирования дуги соединен с вторым входом элемента И дуги, выход каходого из которых подключен к входу элемента ИЛИ одновременно, i -го столбца, выход которого соединен с управляющим входом элемента И второй группы i -го столбца выход которого подключен к соответствующему входу узла выбора максимума, выход которого соединен с первым входом многовходового сумматора, выход . KOToJDoro подключен к информационньтм входам элементов И первой группы, выход элемента И первой группы -ого столбца соединен с входом регистра -о столбца, выход которого подключен к информационному входу элемента И второй группы 1 -ого столбца и к информационному входу элемента И третьей группы. 1 -ого столбца, выходы элементов И третьей группы соединены соответственно со входами элементов ИЛИ группы, выходы которых подключены к второму входу многовходового сумматора. На фиг. 1 представлена структурная схема устройства; на фиг. 2 - узел выбора максимума. Устройство содержит (фиг. 1) матриvy 1 однородных ячеек размером П х п. J-. где П - максимальное число узлов модул руемого графа, йключающую триггеры фо мирования дуг 2 и элементы И 3 дуг. Кроме того, устройство содержит по чис лу столбцов матрицы элементы ИЛИ 4, первую группу элементов И 5, элемент задержки 6, регистр 7, вторую 8 и третью 9 группу элементов И, группы элементов ИЛИ 10, сумматор 11, генерато тактовых импульсов 13, элемент И 13, элемент НЕ 14, реверсивный счетчик 15, дешифратор 16, узел выбора максимума 17, вход устройства 18 и выход устройства 19. Узел 17 выбора максимума (см.. 2) содержит выходные элементы ИЛИ-НЕ 2Oi 202,..., m поразрядные 21;|, 212, .... 21, группы элементов И и ИЛИ 21,,, 22 состоящие из элементов ИЛИ 23 и элементов И 24, входные шины 25, 25nin выходные шинь 26,(, 2б2, ..., 26, и 27, 27, ... I 27ji. Устройство работает следующим образом. Первоначально в матрицу 1 заносится информация о топологии моделируемого графа (сети). При этом триггеры 2, моделирующие ветви графа, устанавливаются в единичное состояние. Соответствутоший триггер 2 определяется пересечением строки с номером, равным номеру конечного узла моделируемой ветви, и столбца с номером, равным номеру ее начального узла, В регистры 7 заносятся коды чисел, соответствующие весам вершин. Информация о графе заносится в модель в обычном порядке, при котором наименьший номер (первый) имеет начальная вершина, а наибольший - конечная вершина. В счетчик 15 заносится код числа вершин. Такое занесение исходной информации о графе позволяет использовать для расчета максимальных путей процедуру динамического программирования (см. ниже пример). С появлением пускового сигнала на входе 18 устройства элемент И 13 обеспечивает прохождение счетных импульсов с выхода генератора 12 на вход счетчика 15 (так как на втором управляемом входе элемента И 13 будет высокий потенциал с выхода элементаНЕ 14, вход которого подключен к второму выходу счетчика 15 выхода, на котором появляется сигнал нулевого состояния счетчика 15). С пержого выхода счетчика код поступает на; вход дешифратора 16, в результате чего на одном из выходов деш1фратора 15 появляется высокий потенциал. Появление высокого потенциала на одном из выходов дешифратора обеспечивает подачу высокого потенциала науправялемые входы соответствующего столбца элементов И 9 и элементов задержки 6, а также элементов И 3 одноименной строки матрицы 1. В случае, если триггеры 2 в данной строке находятся в единичном 594 состоянии, то через элементы И 3 и ИЛИ 4 высокий потенциал с этих триггеров 2 подается на управляемые входы соответствующих элементов И 8, что в свою очередь обеспечивает подачу кодов с регистров 7 на входы узла 17. Узел 17 обеспечивает выбор из поступивших на ее вход кодов максимального числа и подачу его на первый вход сумматора 11. Одновременно, на второй вход сумматора 10 ды 11 подается код с выбранного регистра 7 через соответствующий элемент И 9 и rpfynny элементов ИЛИ 1О, Результат с сумматора 11 через открытую группу элементов И 5 (к этому моменту времени на управляемом входе элементов И 5 будет высокий потенциал с выхода элемента задержки 6) поступает на вход регистра 7. На этом этап формирова шя кода максимального пути для одной отдельной вершины заканчивается. На вход счетчика 15 поступает очередной импульс в результате чего содержимое счетчика 15 уменьшается на единицу, jnosTOMy на выходе дешифратора 16 возбу ается очередная шина и процесс формирования величины максимального пути для очередной вершины графа происходит аналогично Вычислительный продесс продолжается до тех пор, пока, на счетчике 15 не появляется нулевой код, в результате чего появляется высокий потенциал на выходе устройства 19 и входе элемента НЕ 14. Следовательно, на выходе элемента НЕ 1 дет нулевой потенциал, после чего прекращаётся подача счетных импульсов с выхода генератора 12. Узел выбора максимума 17 работает следующим образом. На входные шины 25 узла 17 поступает П чисел, каждое из которых представ- лено Д1 разр$эдами, с выходов регистров 7 через группы элементов И 8. В первый момент анализируются старшие разряды. Если хотя бы один из разрядов Ч1к;ел равен 1, то иа выходе 26.; (в старшем разраде) формируется О, который вырабатъшае т сигнал запрета для каждого из чисел. При этом, если разряд -1 -с-о числа равен О, то все числа не проходят через элементы И i -ой группы пертюго узла п еноса Если старший разряд -го числа равен 1, то -i -ое число проходит через элементы И н -ой группы первого поразрядного узла переноса. Если старшие разряды всех чисел равны О, то на выходе элемента ИЛИ-НЕ 26 формируется 1, которая дает разрешение 8 на прохождение всех л чисел через элементы И первого поразрядного узла переноса 21,. Таким образом, на выходе элементов И 24 группы 22 формируются прямые коды чисел, начиная со второго по m -ый. Вторалм элементом ИЛИ-НЕ 2б2 совместно с элементами ИЛИ 23 поразрядного узла переноса 212 иализируются вторые по старшинству разрял чисел таким же образом, как и страшшс разрядов. На выходе элемента ИЛИ-НЕ 26 формируется второй по старшинству разрвд экстремального числа, а на выходах элементов И 24 формируются коды чисел, начиная с третьего по п -ый и т. д. Таким образом, на элементах ИЛИ-НЕ 26 формируется обратный код экстремаль кого числа. Позиционный код номера экст ремального числа получается путем совпадения всех П сигналов запрета, сформированных в каждом i -ом поразрядном узле переноса. При сигналах запрета, равным 1, на вьгходе комбинационной схемы формируется также позиционный код с 1 в разряде, соответствующем экстремальному коду. Работа устройства при опредшении наиболее ранних моментов наступления событий идентична работе устройства при слределении величин максимальных путей для всех вершин в графе. Разница лишь в том, что матрица смежности грифа заносится в матричную модель сети с предварительным транспортированием относительно главной диагонали матрицы, Таким образом, предлагаемое устрой ство за счет введения дополнительных элементов с новыми связями обеспечивает существенное повышение быстродейст вия по сравнению с известным. Быстродействие предлагаемого устройства зави- сит только от числа П вершин в графе и не зависит от величины кодов длительноети вершин графа. Формула изобретения Устройство для исследования путей в графах, содержащее матрицу П х ц триг-f геров формирования дуг графа и генератор тактовых импульсов, выход которого соединен с первым входом элемента И, второй вход которого является входом устройства, отличающееся тем, что, с целью повышения быстродействия, в него введены по числу триггеров формирования дуг элементы И дуг.

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

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

Источники информации, принятые во внимание при экспертизе

1.Авторское сввдетельство СССР № 640314, кл. Q 06 О 7/122, 1978.

2.Авторское свидетельство СССР по заявке № 2587569/18-24,

кл G Об F 15/20, 1978 (прототип).

2St