Устройство для определения максимальных путей в сетевых графах

Устройство для определения максимальных путей в сетевых графах

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК

„„SU 1320812 А 1 (511 С 06 F !5/20

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4017146/24-24 (22) 04.02.86 (46) 30.06.87. Бюл, N 24 (72) В,В. Райский и В,В. Сергеев (53) 681,325 (088,81 (56) Авторское свидетельство СССР

9 798854, кл. С 06 F 15/20, 1978.

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

Р 995094, кл. G 06 F 15/20, 1981, (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

МАКСИМАЛЬНЫХ ПУТЕЙ В СЕТЕВЫХ ГРАФАХ (57) Изобретение относится к вычислительной технике и может быть использовано для нахождения максимальных путей в сетевых графах без контуров и петель, Цель изобретения — расширение области применения за счет нахождения всех максимальных путей.

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

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

1 12081 2 т

30

-тl

Изобретение от«осктся к иычис IEI" тельной технике и может бь:,ть Hc«o)E:— зовано для решения на грас1>ях без кс;- .— туров и петель задач опр»,»,елен«я маK" симальных путей.

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

На чертеже представлен;- струк".урная схема устройства, Устройство содержит «аддиагональную матрицу 1 моделей дуг,, элементы которой состоят из тртлггера 2, и: рВого 3 к второго 4 элементов И, p 2«IIy элементов ИЛИ-НЕ 5, группу элементов

ИЛИ б, группу элементов И 7, гру tll счетчИков 8, групгту элеме:ттон И Э., группу счетчиков !О„ груп:ту блок )B элементов И 1, гOyI« y Tp,lr I epoB 1 2, группу элеме«. ов И 13, блок 14 выбс ра максимального кода., ге«ератор 1к распределитель 16 импульсов„ э те-мент И 17, элемент 11(1И 1. 1, груп".у элементов И 19, групггу эл»мен"oB

ИЛИ-НЕ 20, группы 2I к 2? тркггеэон„

Сначала в единичное со(тоянке устанавливают триггеры 2, где в .а-.:— рице смежности графа запксаны 1".0б«;— ляют счетчики 10 к все тркгl еры,.кром( триггера 12,, который уст 1«явлкв нот в состояние . 8 стетчикк 8 за сй, () сят код, соответствующий колич»с гву кмпульсОН > дополн51ютттих в е а B»plUHI до полной емкости счетчиков. На вы-ходах блока 121 прксутству:0т "0, Устройство работает сл;)дующим образом, С подачей пускового cигналя и:1пульсы генератора 1. ;. по"T;II«10! на входы счетчиков 10 к 8„,,1ссле и рсполненкя котс1)огo зякpbl«1(ттся э. I мент И 9 . В счетчик=- 10:, фи<сит) руется вес и-й Вр.рхптны и .,якритнаются элементы И 4 — го =T-o)U,ç:;;I татрлцы 1.

Закрытие укязаннь х эле лен-.oí lp;..— водит к тому, что «и выходе одно гс или нескольких элем» нтов ИПИ-HI. 3 появляется едктткчный поте:«ткал,, обуславливаюттий о гкр1-ттие;)днокме -1-ных элементов И 7 к тоступле IHC импульсов генератора I5 ня. 13ходы с.)ответствутощих счет413xo« 8 KoTI)p",и начинают счет км:I у:тт,сов Далее у - тработает т -.х же, заполнении с те чика 8. IIo(тål-.е««э все 13ольтнее число с т етчтлттов 8 «c ) еполняется. Зятем 3я кнвер; «ых вы сд:..х триггеров 22 появляется нулевой

1тсте«пиал вниду п»репо:тнения всех

" -.етчиков 8. Поя«:тенке нулевого погеттцкала HB выход» злеме«та ИЛИ 18

Обуславливает пер< брос в единичное состояние триггера 12, открьгшле

;-.IåìåHTà И 17 к поступление импульс((в «а тактовый вход распределителя 16. Б счетчика:< 10 фиксируются .ходы максимальных путей из вершин графа в его конечную вершину.

Импульс с первого выхода распределителя 16 проходит через элемент

13 на и-орые «ходы элементов И 3 моделей дуг первой строки матрицы

1 H далее на входы тех элементов И 3, которые отттрытbI 11o IUep«o входу

f едкничными потетгциалами триггеров

2,. Через cooтветстнующке элементы .IЛИ 6 импульсы пр входят на вторые в):оды элеме :-UoB И .11 к открывают Hõ, гак что коды с cooT«eтствующих счет-:l1xoB 10 поступаю г на входы блока

1(т, который выдяе г единичный сигнал

«и тот выход, котзрый соответствует максимальному коду среди всех вход«вх кодов,если нл входе присутсти ) ет несколько одлнаково максимальг тх кодов, тс едк личные сигналы выди 0тся EIÿ «с» сОО- 13етстBv!0UIHe Выхо— .111), Пусть . лакскмзльный кОд присут сгнует «а третьем входе Олока 14 (13хсды и выходы О.пока 14 «умеруются .-.о второго Ilc n 1 -Й,, . Тогда единкчттый сигнал появляется на. третьем вы ходе блока 14 и проходят через элемент И 19,, открытый единичным поте«циалом " выхода элемента НЕ 20

2 тта вход триггера 12, к перебрасывает его в единичное состояние, что осуслаВГткнает Открьтттлp элемента

И 13, для тэетьегo ныхоця распреде.тктеля 16.

:;-)Оме того, е кни-1«ый «стен)ткал с

1.)етьегo выходя бп>ка 14 перебэасынает в ед«lгкчное сocTîÿ«èå триггер 21, .

Импульс со BT()р() гс 3b хода распреде кителя 1 6 .1 е;;) ез э;темент И 1 3, не проL ходит, 51мгт )JII c " Tp Q., Bf I о выхода распределителя 16 ттроход:.тт через зле)те«т И 13,. т.а вторые «ходы всех элеме«тов И 3 третьей строки матрицы

Далее ycтрсйcT«о работает так же, кяк прк пода-:å сит «ала на вторые . xogbI элетле«тс« И 1 пе,)вой строки

МОТРИПЫ !, Б РЕЗУт« I BТЕ, IIOC 1Е ПРОхожде«кя кмп . ли си "; I гс Вт>(хода

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

Состояния триггеров 21 копируют состояния триггеров 12, Последнего не будет при наличии в 1О графе двух или более одинаковых критических путей, Тогда на каком-то шаге (или шагах) на входы блока 14 поступают несколько максимальных кодов, и единичные сигналы появляются не на одном, а на двух или несколь ких выходах блока 14 одновременно, Тогда в единичное состояние перебрасываются все соответствующие триггеры 21, а из триггеров 12-только один,20 номер которого наименьший, Пусть, например, единичные сигналы :появляются на третьем и шестом выходах блока 14.Тогда на всех входах элемента ИЛИ-HF 20> присутствует нулевой потенциал, а на выходе — единипъ и потенциал, который открывает элемент И 19 для прохождения единичного сигнала с третьего выхода блока 14 на вход триггера

12, который перебрасывается в еди— ничное состояние. В это время на одном из входов элемента ИЛИ-HF 20 присутствует единичный потенциал.

Поэтому на выходе данного элемента 35 присутствует нулевой потенциал, закрывающий элемент И 19

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

Такие триггеры 21 указывают вершины, через которые проходят другие пути та — кой же длины, как и первый найденный кри— тический путь. При необходимости нахождения таких путей поступают следующим образом. Отмечают номер Н находящихся в единичном состоянии триггеров 12 и 21, 1 за которым следует т-й триггер 21, находящийся в единичном состоянии в отличие от состояния триггера 12,.

Приводят устройство в исходное состояние, Однако триггер 22 с номером

Н сразу устанавливают в единичное состояние, фиксируя тем самым в счетчике !О с номером H код "О . Запус1. 4

: nI a ъ с трой ство» работу. Fсли зультате получают совпадение состояний всех одноименных триггеров . !2 и

21, то по епи«ичным состояниям триггеров 12 определяют вершины нового критического пути равной величины.

Если же в к вь аходятся триггеры

21, состояние которых не совпадает с состоянием одноименных триггеров

12, то находят номер триггера 22, который, как и триггер 22 с номером

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

Устройство для определения мак симальных путей в сетевых графа - co держащее наддиагональную матрицу моделей дуг, три группы элементов И, группу блоков элементов И, группу элементов ИЛ!1, первую группу элементов ИЛИ вЂ” HE, две группы счетчиков, первую группу триггеров, блок выбора максимапь«ого кода, элемент ИЛИ, элсмент И и генера,ор импульсов, причем каждый элемент 1-й строки

j-го столбца (i=-I...,n-1, j=i+I. ° .n где и — количество времени в графе) наддиаго«альной матрицы моделей дуг содержит триггер и два элемента

ИЛИ, первые входы которых соединены с выходом триггера соответствующего элемента матрицы, выход первого элемента И i é строки j --го столбца (З=п) матрицы соединен с i-м входом

j-го элемента И 1И группы, выход которого соединен с первыми входами элементов И б- ока j — и группы, выходы которых соединены с соответствilo шик входами блока определения максимального кода, выход второго элемента И i-й строки )-ro столбца матрицы соединен с )-м входом 1-го элемента ИЛИ-IIF. первой группы, выход которого соединен с первым входом

i ãî элемента И первой группы, выход которого соединен со счетным входом соответств -:огарево счетчика первой группы, выходы элементов И с первого по и-й второй группы соединены со счетными вха,",ам«соответствующих счетчиков второй группы, выход i-го триггер . (i n-1) первой группы соединен с первым входом 1 го элемента И третьей группь, выход которого соединен с вторым входом первого элемента

i32Ãßi2

1-й строки каждого столбца> тзыход генератора импульсов соедин.н с первым входом элемента И, пеэвый гыхоц блока определения максималь:!ого кода соединен с входом вто-.!or o тркг! ера первой группы, о т и к ч а lo rri e e с я тем, что, с целью paclrrrper-,rra области применения за счет:тахождения всех максимальных путей, в него введены вторая и третья группы тркг- !!) геров, вторая группа элеменгов И И-11!", четвертая группа элементов И и распределитель импульсов., причем ."-ыхог генератора импульсов соединен с. первыми входами элементов И первой и 1.; второй групп, выходы переполнен!ля счетчиков первой гругтпы соецттнены с входами соответствующттх три-геров второй групгты триггеров, v:.".зсрсные выходы которых соединелы с. вторымк I) входами соответствуюгтих элемен оВ

И второй Групг!ы вторыми входамк всех элементов И соответствут>гттет о столбца матркцы и соо": в етс т ".уто!!>тлмк входами элемента ИЛИ„ выхсц которо-. го соединен с входом l:ервого трктг= ра первой группы, выход которо! о соо— динен с первым входом первого ;.!тте ента И третьей группы., 1<. — и выход блока определения максимального кода .!> и (k 2,...,n — 3) соединен с первым вхо! т и k 1-гс пл! .лепт» И четг>ертой! группы и k 1-и .-. .холотл 1с-го элемента

1Б1И вЂ” НЕ второй групп >l, выход которого соединен с вторым входом,.ë-,åìå;ròë

Л четвертой руины., пертть.=,"! выход бт ока определения максимального код".

g с! ецинен с -м ттхо lob! -no эпе:!ента

>1:Л1-HE (8=1,, „и-31 в-.opov гру!тпы > и-2-й выхбд блока о!!рецелентля макдинен с первым

ilта И, выход в этой ",ðóïïû соескмальногс кода с ic вхо том и-3-гс элема

1 --го элемента > чет вк!:>eн с входом f+2рс и группы, .выходы ! !» < сима I b Ho r ñ к ода го триггера втоб.;т-с ка опрецеленкя лоезкнет, вхо— дами соответс. ву-сшт-х триггероь третьей гругпты, =;bl> о,,:!"- . --го тркгг..— ра гретьей гр !ппы со=дкнен с первым р О "том п о элемстт! c. И i pH!>!т! Гp >> !r b. к ттервым вхопом б: î à опреде.т"-ния мт!кскг"ума, выход г е: >е- !Tg И соедн ро! о соединpIK с втc pb!,"ì входамк со о т B E ò с т В ующк х э л с,м а н т о В I ! р е Г ь ек

l руины, (г;1,!-A выход распределителя импульсов соедине; с входом т!"! анова генератора;гяп>ульсотт

«т>од запуска котор го, соеди-! еll с входом эа! усKB устройст—!

;е: с входом распрсд=лктсля импуль.сот! выходы с:тервс г э пс и — 2-й котоСоставiaT .!ь съ, .)i pi.i!

l ;

Редактоо И. Касарда Тсхред Я,Глугенкс

Заказ 2б60/32 Гира.к 673

Б11 111ПИ 1 асударственного комитета ССС по делам изобретений и открь.гий

113035, 11осква, ri-35, Раупск ii наб,,.

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