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

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

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

На чертеже представлена струк ур- ная схема устройства.

Устройство содержит наддиагональ- ную матрицу 1 дуг,, элементы которой cocTOfiT из триггера 2j первого 3 и второго 4 элементов И, i-pynrry элементов РШИ-НЕ 5, групп у элементов ИЛИ б, группу элементов И У, группу счетчиков 85 группу элементов И 9э группу счетчиков 10,, группу блокон элементов И I-, группу тригтеров 12,, группу элементов И 13, блак 14 выбо- ра максимального кодаj генератор 1Ь и распределитель 16 импульсов элемент И 17, элемент ШШ IB, группу элементов И 19j группу элементов ИЛИ-НЕ 20, груттпы 21 и 22 триггеэов„

Сначала в единичное состояние устананливают триггеры 2, где в i SaT- рице смежности графа записаны 1 „06iry- ляют счетчики 10 и все триггеры,кроме триггера 12,, который устанавлив,а1от в состояние l. В счетчики 8 зачо-- сят код, соответствующий количес-гву импульсов, дополняющих веса вершин до полной емкости счетчиков. На кы-- ходах блока 14 присутств:/1.от О .

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

С подачей пускового c гнaлa им- гтульсь генератора 15 поступают на

вход1з счетчиков

.и

8.

после П2рс

полнения которого закрывается э.из- мент И 9 , В счетч псе 10 п фиксируется вес п-й вершины к закрываю т- ся элементы И Др-го с тол б а матр:-1ЦЬ 1 .

Закрытие указанных элементов api водит к тому, что на выходе одного или нескольких элементов 3 появляется единичный потенциал, обуславливаю ДИ11 о-гкрытие одноимеа- ных элементов И 7 и поступление импульсов генератора 1 5 на иходь соответствующих счетчиков 8,, которые начинают счет импултзСОВо Далее устройство работает так же, как при заполнении счетчика 8. Постепенно все большее число счетчиков 8 пезе- полняется. Затем на инверсных выкс

25

30

40

50

22

ДйХ триггеров 22 появляется нулевой noTeinwan ввиду переполнеиия всех с;четчикоя 8, Появление нулевого по- ге)п;иала на выходе элемента ИЛИ 18 обуславливает переброс в едипичное состояние триггера 12, . открытие элемента И 1 7 и поступление импульсов на тактовый вход распределителя 16, В счетчиках 10 фик сируются лоды максимальных путей из вершин графа в его конечную вершину.

Импульс с первого выхода распределителя 16 проходит через элемент И 13 на вторые входы элементов И 3 моделей дуг первой строки матрицы 1 и далее на вход1)1 тех элементов И 3, которые открыть: по первому входу епиничными поте п;иалами триггеров 2, Через соответствующие элементы ИЛИ 6 импульсы проходят на вторые элеметов И Л 1 и открывают иХд так что коды с соответствующих счетчиков 10 поступают на входы блока который выдает единичный сигнал па тот выход, который соответствует максимальному коду среди всех вход- нь.х кодов (если на входе присутствует несколько од: 1наково максимапь- кодов 5 то единичные сигналы вы- дп отся на все соответствующие выходы) . Пусть максимальный код присутствует на третьем входе блока 14 (1 хода1 и выходы блока 14 нумеруются со второго по П-1--Й). Тогда единичный сигнал появляется на. третьем вы ходе блока 14 и проходит через элемент И открытый единичным потенциалом с элемента НЕ 20 , на вход трип ера 12 и перебрась - вает его в единичное состояние, что обуславливает открытие элемен та li 13,, для прохождения импульсов с третьего вы:х.ода распреде.чителя 16„ Кроме того, с -ллиничный потенциал с третьего выхода блока 14 перебрасы- ваеТ в единичное состояние триггер 2, ,

Импульс со HTop jro выхода распреде лителя 16 через элемент И 3„ не проходит. Импульс с третьего выхода распределите чя 16 проходит через элемент И 13 а вторые входы всех элементов И 3 третьей строки матрицы 1„ Д.злее устройст;ю работает так же, как при подаче сигч1ала на вторые входы элекентогз И 3 первой строки матрипы . В резугпггате, после прохождения импульса с п-|-го выхода

г-

31

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

Состояния триггеров 21 копируют состояния триггеров 12.

Последнего не будет при наличии в графе двух или более одинаковых критических путей. Тогда на каком-то шаге (или шагах) на входы блока 14 поступают несколько максимальных кодов, и единичные сигналы появляют ся не на одном, а на двух или нескол ких выходах блоКа 14 одновременно. Тогда в единичное состояние перебрасываются все соответствующие триггеры 21, а из триггеров 12-только один номер которого наименьший.

Пусть, например, единичные сигналы :появляются на третьем и шестом выходах блока 14,Тогда на всех входах элемента ИЛИ-НЕ 202 присутст- вует нулевой потенциал, а на выходе - единичный потенциал, который открывает элемент И 19j для прохождения единичного сигнала с третьего выхода блока 14 на вход триггера 12, который перебрасывается в единичное состояние. В это время на одном из входов элемента ИЛИ-НЕ 20 присутствует единичный потенциал. Поэтому на выходе данного элемента присутствует нулевой потенциал, закрывающий элемент И 19.

В результате работы устройства при наличии двух одинаковых кри-- тических путей (или нескольких та- ких путей) состояния некоторых триггеров 21 не совпадают с состояниями одноимегшых триггеров 12.

Такие триггеры 21 указывают вершины,

через которые проходят другие пути та

кой же длины, как и первый найденный критический путь, При необходимости нахождения таких путей поступают следующим образом .Отмечают номер Н находящихся в единичном состоянии триггеров 12 и 21 , за которым Следует т-й триггер 21, находящийся в единичном состоянии в отличие от состояния триггера 12. Приводят устройство в исходное состояние. Однако триггер 22 с номером Н сразу устанавливают в единичное состояние, фиксируя тем самым в счетчике 10 с номером Н код О. Запусt5

5

О ь ,20

35

,

4

ив . ткают ycTpoiicTBO в работу. Если в результате получают совпадение состояний всех одноименных триггеров . 12 и 21, то по еди 1ичным состояниям триггеров 12 определяют вершины нового критического пути равной величины. Если же вновь находятся триггеры 21, состояние которых не совпадает с состоянием одноименных триггеров 12, то находят номер триггера 22, который, как и триггер 22 с номером Н, надо установить в единичное состоя}гае после приведения устройства в исходное состояние. Затем вновь запускают устройство. Формула изобретения

Устройство для определения максимальных путей в сетевых графах, содержащее наддиагональную матрицу моделей дуг, три группы элементов И, группу блоков элементов И, группу элементов ШБ1, первую группу элементов ИЛИ - НЕ, две группы счетчиков, первую группу триггеров, блок выбора максимального кода, элемент -ШИ, элемент И и генератор импульсов, причем каждый элемент i-й строки j-ro столбца (,,.,п-1, .,.п, где и - количество времени в графе) наддиаго-иальной матрицы моделей дуг содержит триггер и два элемента РШИ, первые входы которых соединены с выходом триггера соответствующего элемента матрицы, выход первого элемента И i-й строки j-ro столбца () матрицы соединен с i-м входом j-ro элемента группы, выход которого соединен с первыми входами элементов И блока j-й группы, выходы которых coeдинe ГDI с соответствчто- входами блока определения максимального кода, выход второго элемента И i-й строки j-ro столбца матрицы соеди тен с j-м входом i-ro элемента ИЛИ-НЕ первой группы, выход которого соединен с первым входом i-ro элемента И первой группы, выход которого соедр.нен со счетным входом cooTBeTCTB --ouiero счетчика первой группы, выходы элементов И с первого по п-й второй группы соединены со счетными входами соответств по1чих счетчиков второй группы, выход i-ro триггера () первой группы соединен с первым входом i-ro элемента И третьей группы, выход которого соединен с вторым входом первого элемента

51

i-й строки каждого столбца выход генератора импульсов соединен с пер- вь1м входом элемента И, первый выхоц блока определения максимальтюгс коца соединен с входом второго триггера первой группы, о т п и ч а ю щ е е с я тем, что, с целью расширения области применения за счет лахояоде- ния всех максимальных путей, в него введены вторая и третья группы триг геров, вторая группа элементов ИЛИ-Н четвертая группа элементов Vf и распределитель импульсов., причем вькод генератора импульсов соединен с первыми входами элементов И первой и второй групп, выходы переполнения счетчиков первой группы соецинен 51 с входами соответствующих триггеров второй группы триггеров, инлзерснрле выходы которых соединенны с- вторыми входами соответствующих э,т;емен .гов И второй группьц вторь ми входами всех элементов И соответствз тощего столбца матрицы и соответств:у1ощими входами элемента ШШ., выход которо- го соединен с входом г ервого тригг е- ра первой группы, выход которого соединен с первым входом первого та И третьей т руппы, k-й выход блока определения максимального кода ( .... ,0-3) соединен с первым вхо

четвеотои

группы и гхоло - k-ro элемента I-|JM-HE второй группы; дзыход которого соединен с вторым 5ходом элеме 1та Н четвертой rpvnnbi, первьш выход блока определегшя каксимальпого кода соединен с -м входом К -го элемента гга;-НЕ 5 . .п-3)-второй группы. выход блока определения максимального кода соединен с первьм входом п-З-го элемента И,, выход - fro элемента И четвертой группы сое- с входом f+2--ro триггера второй ГРУППЫ; выходы блока определения максимального кода соедикеш-л с входами cooTBeTCTBv-:oiiD-:x триггеров третьей Г руппы, п-1-го триггера третьей группы соединен с первь м входом п-го элемента И первый группы и первым входом определения максимума, выход эгемепта К соеди- с входом распределителя импуль - совJ выходы с первого по п-2-й которого соединеш.т с В Орыг- Ш входаг-ги соответствующих эле маптов И третьей группы, (п-1)-й ,р, распределителя ш-игульсов соединеь с входом останова генератора и1-тульсов , вход запуска которого соеди- ПсМ1 с входом заг:уска устройства .

Составите:1Ь А ЗСФУП-: редактор И. Касарда Техред Н. Гл тдекко

Заказ 2660/52 Тираж 672Полгиснос

ВНИКШ-1 Государственного комитета . СССР

но делам изобретений и открытий ПЗОЗЗ, Москва, Ж-ЗЗ, Раушская наб,, Д. /-З

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

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