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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК аш 1 32081 2 6 Р 5/20 ГО ПО ОПИСАНИЕ ИЗОБРЕТ:" т= СВИДЕТЕЛЬСТВ ОРСН Р 24В,В, Серге етельство СССРГ 15/20, 1978.ельство СССРР 15/20, 1981,ОПРЕЙЕЛЕНИЯВ СЕТЕВЫХ ГРАе 6(57) Изобретение от лительной технике и пользовано для нахо ных путей в сетевых сится к вычисожет быть исждения максимальграфах без конту АРСТВЕННЫЙ КОМИТЕТ СССРЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(54) УСТРОЙСТВО ЙЛЯМАКСИМАЛЬНЫХ ПУТЕЙФАХ ров и петель, Цель изобретения - расширение области применения за счетнахождения всех максимальных путей.Устройство содержит матрицу 1 моделей дуг, состоящих каждая из триггера и двух элементов И, две группыэлементов ИЛИ-НЕ, группу элементовИЛИ, четыре группы элементов И, двегруппы счетчиков, группу блоков элементов И, блок выбора максимальногокода, генератор и распределитель импульсов, элемент И,элемент ИЛИ,три группы триггеров. Цель достигается за счетнахождения вершин всех существующихмаксимальных критических путей изначальной в конечную вершину сетевого графа. 1 ил.4 р 50 лп Изобретение отосктся к вычисли тельной технике и моьет бь:ть использовано для решения на графах без ксив туров и петель задач определения мак симальньх путей,Цель изобретения - ра.п.крзие осласти применения за счет ахождеиявсех максимальных путей.На чертеже представлен;: струк"урная схема устрайс пва,Устройство содержит наддиаганальную матрицу 1 моделей дуг., элементь.которой состоят из трлггера 2, первого 3 и второго 4 элементов И, группуэлементов ИЛИ-НЕ 5, группу элементовИЛИ б, группу элеметов И 7, гру:игусчетчИков Я, группу элемегтсв И Э.,группу счетчиков О групзу блоковэлементов И 1, группу триггеров 12группу элеменав И 13, блок 1 Выбсра максимального колл., геератор 13к распределитель 16 импул: сав, э темент И 17, элемент 1 ПИ 1,1, группуэлементов И 19, групгг, элеменпавИЛИ-НЕ 20, группы 21 к 22 триггеровСначала в единичное са:таяниеустанавливают триггеры 2, где в .Кат -рице смежности графа запксаны 1",Обуляют счетчики 10 к все тркг еры,крометриггера 12 который уст яилив 1 отв состояние . 8 счетчики 8 за .с,сят кад, соответствующий каличес пвуИМПУЛЬСОВ у ДОПСЛН 51 ЮЩИХ ВЕСЕ ВЕРШИдо полной емкости счетчиков, На вы-.ходах блока 1 А присутствуот "0,Устройство работает следующимобразом,С подачей пускового сигнала импульсы генератора 1 1 пост 5 ают нзвходы счетчиков 10 к 8, после и реполнения которого закрыв зится эл"мент И 9 , 8 счетчике 10:, фккскруется вес и-й верпп",ны и .,якрь.иаются элементы И- го столбца матрлцы 1,Закрытие укязанньх элементов р -водит к таму, что а выходе ОднО.Сили нескольких элементов ИЛИЕ 5паяВляется едкичый патециал,абуславливающий открытие сдноимел. -ных элементов И 7 и постулепке импульсов генератора 15 ня. ходы сзответствуощих счетчиков 8 кстс 1 т;:еначинают счет импульсов 1 алее утрокстВО работает т ак жекак призаполнении счз ива 810.тегезвсе большее числа счетчиков Я сеполняется. Зятем ия ивереых иы.сДсх триггеров 22 появляется нулевойатенкап вниду переполнения всехс:.етчиков 8, Пояиленке нулевого попе)циала на выход элемента ИЛИ 18обуславливает переброс в единичноеастсяние триггера 12, открьгшлеэлемента И 17 к поступление кмпульсв а тактавьй в:,"од распределителя 1 б, Б счетчиках 10 фиксируютсяходы максимальных путей из вершинграфа в его конечную вершину,Импульс с первого выхода распределителя 16 роходкт через элемент13 на Вторые входы элементов И 3моделей дуг первой строки матрицы1 и далее на Входы .ех элементов И 3,которые открыты пс первому входуедкничными потенциалами триггеров2,. Через соответствующие элементы:1 ЛИ 6 импульсы пр зходят на вторыевходы элемекгтав И .11 к открывают кх,так чта коды с соответствующих счетчиков 10 поступаю и на входь блока1, который выдяе и единичный сигнали тст выход, который соответствуетмаксимальному коду среди всех входьх кодов ,если нл входе присутсти апет несколько адлнакава максимальых кодов, тс едк ли-ные сигналы выдаются ня исе ссо. ВетстВуОшие Выхо - дь). Пусть максимальный код присутс.иует а третьем входе слака 1 ч (ихадь и вьходы сзока 14 умеруются сс второго пс и-й). Тогда единичый сигнал появляется на. третьем выходе блока 1 ц и проходят через элемент И 19 открытый единичным патециалом " Выхода элемента НЕ 20га вход триггера 12, к перебрасыизет его В единичное состояние, чтоасуславлквает открытке элементаИ 13 для прохождения импульсаВтзетьега Выхаця распределителя 16,.оетьего выходя бзока 14 перебэасыиает в едкикое состояние триггер 21Импульс сс итсрсгс вь:хода распредекителя 16 через эпемент И 13, не проходит. И;пульс " третьео выходараспределителя 16 ирахадкт через элемет И 13, иа Вторые входы всех элематав И 3 третьей строки матрицы 1.Далее устройство работает так же,кяк при подаче си ала на вторыевходы элеметси И 3 первой строкиматрицы , Б реву-п:тате, пас,"е прахзщеи 5 имппи си Г --- гс Выхода132 ОВраспределителя 1 б и последующегоостанова генератора 15 единичныесостояния триггеров 12 указывают вер -шины, через которые проходит в графемаксимальный критический путь от начальной первой до конечной и-й вершины.Состояния триггеров 21 копируютсостояния триггеров 12,Последнего не будет при наличии в 10графе двух или более одинаковых критических путей, Тогда на каком-тошаге(или шагах) на входы блока 14поступают несколько максимальныхкодов, и единичные сигналы появляются не на одном, а на двух или нескольких выходах блока 14 одновременно,Тогда в единичное состояние перебрасываются все соответствующие триггеры 21, а из триггеров 12-только один,20номер которого наименьший,Пусть, например, единичные сигналы :появляются на третьем и шестом выходах блока 14,Тогда на всехвходах элемента ИЛИ-НЕ 20 присутствует нулевой потенциал, а на выходе - единичный потенциал, которыйоткрывает элемент И 19 для прохождения единичного сигнала с третьеговыхода блока 14 на вход триггера3012 з, который перебрасывается в еди -ничное состояние. В это время наодном из входов элемента ИЛИ-НЕ 20присутствует единичный потенциал .Поэтому на выходе данного элемента 35присутствует нулевой потенциал,закрывающий элемент И 19В результате работы устройствапри наличии двух одинаковых критических путей (или нескольких таких путей) состояния некоторыхтриггеров 21 не совпадают с состояниями одноименных триггеров 12.Такие триггеры 21 указывают вершины,через которые проходят другие пути та - 5кой же длины, как и первый найденный кри -тический путь. При необходимости нахождения таких путей поступают следующимобразом.Отмечают номер Н находящихся вединичном состоянии триггеров 12 и 21,1за которым следует т-й триггер 21,находящийся в единичном состояниив отличие от состояния триггера 12,.Приводят устройство в исходное состояние, Однако триггер 22 с номеромН сразу устанавливают в единичноесостояние, фиксируя тем самым в счетчике О с номером Н код "О , Запус 4ъстройстцо . работу, Если в результате получают совпадение состояний всех одноименных триггеров . 2 и 21, то по единичным состояниям триггеров 12 определяют вершины нового критического пути равной величины, Если же вновьаходятся триггеры 21, состояние которых не совпадает с состоянием одноименных триггеров 12, то находят номер триггера 22, который, как и триггер 22 с номером Н, надо установить в единичное состояцие после приведения устройства в исходное состояние. Затем вновь запускают устройство.юормулаизобретенйя Устройство для определения максимальных путей в сетевых графах, содержащее наддиагональную матрицу моделей дуг, три группы элементов И, группу блоков элементов И, группу элементов ИЛ 11, первую группу элементов ИЛИ - НЕ, две группы счетчиков, первую группу триггеров, блок выбора максимгпьцого кода, элемент ИЛИ, элсмент И и генератор импульсов, причем каждый элемент 1-й строки 3-го столбца (1.=-1,п, 3=1+1 п, где и - количество времени в графе) наддиагоцальной матрицы моделей дуг содержит триггер и два элемента ИЛИ, первые входы которых соединены с выходом триггера соответствующего элемента матрицы, выход первого элемента И 1-й строки 3 -го столбца (3=п) матрицы соединен с 1.-м входом 3-го элемента И,1 И группы, выход которого соединен с первыми входами элементов И блока 3-й группы, выходы которых соединены с соответствуюццк входами блока определения максимального кода, выход второго элемента И 1.-й строки 3-го столбца матрицы соедицен с 3-м входом 1-го элемента ИЛИЕ первой группы, выход которого соединен с первым входом -го элемента И первой группы, выход которого соединен со счетным входом соответствующего счетчика первой группы, выходы злемецтов И с первого по и-й второй группы соединены со счетными входамц соответствующих счетчиков второй группы, выход 1.-го триггера (;Фп) первой группы соединен с первым входом 1.-го элемента И третьей группы, выход которого соединен с вторым входом первого элемента1-й строки каждого столбца., выход генератора импульсов соедин и с первым входом элемента И, первый гыхоц блока определения максималь:согс коц соединен с входом второго тригч ера первой группы, о т и к ч а ю щ е е с я тем, что, с целью расщ 1 лреькя области применения за счет нахождения всех максимальных путей, в него введены вторая и третья группы тркг геров, вторая группа элеменгов ИИЕ четвертая группа элементов И и распределитель импульсов причем выхог генератора импульсов соединен с. первыми входами элементов И первой и 15 второй групп, выходы переполнения счетчиков первой групгсы соецкпс.ны с входами соответс.твующих триггеров второй группы триггеров, кпзсрсные выходы которых соединены с. вторымк 20 входами соответствуюгкх элементов И второй группы, вторыми вхсдамквсех элементов И соответствующе: о столбца матркцы и соо":ветствующкмк входами элемента ИЛИ выхсц которого соединен с входом первого трк.гера первой группы, выход которо 1 о сос. - динен с первым входом первого эле, ента И третьей группы 1. - й выход блока определения максимального кода.О (1 си - 3) соединен с первым вхо сом 1 с 1 гс огас:опт И четГертойгрппы и 1 с 1-и входом 1 с ГО элемента1111 И - НЕ второй группы, выход которого соединен с вторым входом элементаЛ четвертой группы, перль.-й выходблока определения максимального кодасоединен с 1-и вхоло л -го э по лента11:11-НЕ (8=1 и) второй гру.пы.и-й выход блока определенля макдинен с первым1 с . выхог,веэтой группы ссескмальногс кода сое входом и-гс элема Г- го элемента И чет пкнен с входом г+2" рс й группы, выходы максимального кода го триггера втоблска опрецеленкя орэкне,- " вхо -дами соответствуснпх триггероьтретьей группы, вьп о гт.1 го тркгг. -ра гретьей гр бэппы согцкнен с первымвходом г, - го элемспгта И первый группь.к первым вхопом б:.ока определения1 аксю "ума. выхоц эг е;ента И соедкро 1 о соединены с втс:ыми входамксоответствующих элс,ментов И третьекруппы, (п)-.л выход распределителяимпульсов соедине; с входом саанова генератора ипульсов ход запуска котор.го соедк еп с входом эа уска устройст -.;е: с входом распрсделктеля импульсот выходы с:;ервс го пс и - 2-Й котоГСостанитель с, З рппРедактоо И. Касарда Техред Я,ГлугенксЗаказ 2660/32 тираж 672 Б 11 ИИПИ 1 асударственного комитета ССС по делам изобретений и открь.гий 113035, адоскин, Ж, Раупская наб Производстненно-полиграфпнеское предприятие, г, ы оро, у. Проектная, ч