В пт бi-. • я г. псггг-йрt45jbl teyhlf iamp;

Союз Советских Социалистических Республиксвидетельства,ависимое М. Кл, 6 061 15 Г 2 1499640/18-2 Заявлено ОЗ,Х 11,1 аявкиприсоединением Государственныи комитет Совета Министров СССР па делам изаоретений и открытийнор итет УДК 681.333 (088,.8) 973. Бюллетень23 описанпя 10.ХН.973 Опубликовано 23.ЧДата опубликован Авторы)зобретеьн елев и А, М. Плахотишин А. А. Илю Заяви гсл амен осковскии ордена Трудового Кр инженерно-физический ин ог ту ОРТНОЙ СЕ ДЕ ГИ ТР Изобретение относится к области вычислительной техники. Известны модели дуги транспортной сети, содержащие триггер, элементы И, элементы задержки, элемент НЕ и реверсивный счетчик.Все известные модели моделируют работу ориентированных дуг графов, имеющих неотрицательную длину.В предложенном устройстве указанные недостатки исключены. 10Модель дуги отличается от известных тем, что в ней единичный и нулевой входы триггера через первый и второй элементы И подключены к выходу третьего элемента И, соединенного входами с выходами реверсивного счетчика, а выходом через элемент НЕ - со входами четвертого и пятого элементов И, импульсные входы которых соединены с шиной тактирующих импульсов, а третьи входы соединены с соответствующими входами задания ориентации дуги, нулевой выход триггсра соединен со входами шестого и седьмого элемента И и четвертым входом четвертого элемента И, второй вход второго элемента И через первый элемент за держки подключен к выходу модели дуги, который соединен со входом второго элемента задержки, выход четвертого элемента И и второй вход первого элемента И подключены ко входу модели дуги, ко торыи соединен со входом третьего элемента задержки, выход которого через восьмой элемент И соединен с суммирующим входом реверсивного счетчика, а через седьмой элемент И и четвертый элемент задержки - с его вычитающим входом, единичный выход триггера сосдинсн со вторым входом восьмого, первым входом девятого и четвертым входом пятого элемента И, выход которого подключен к выходу модели дуги, выход второго элемента задержки через девятый элемент И соединен со входом четвертого элемента задержки и через шестой элемент И подключен к суммирующему входу реверсивного счетчика, который присоединен ко входу задания величины вектора, единичный и нулевой входы триггера соединены с соответствующими входами задания направления вектора.Схема модели дуги транспортной сети приведена на чертеже, Модель содержит реверспвный счетчик 1, вход задания величины вектора 2, триггер 3, входы задания ориентации дугп 4 и 5, элементы задержки 6 - 9, элемент И О, элемент НЕ 11, элементы И 12 - 19, индикатор 20, вход модели дуп 1 21, выход модели дуги 22, входы задания направления векторов 23 и 24, шину тактовых нмпульсов 25.Логика работы модели дуги описывается следующим алгоритмом определения экстремальных путей в транспортных сетях.Пусть цмеется исходная транспортная сетьХ, А, где Л - множество узлов, А - множество дуг. Кажой дуге (х, у)Л, А 1 соответствует ее длина а (х, у) (если (х, у) - неориентированное ребро, то а(х,у) = - а(у,х),причем а(х,у) ъожет быть как положительна,так и отрицательна.Присвоим каждому узлу х сети Л, А потенциал П(х), причем П(хо) =О, где хо - узел,из которого ищется кратчайший путь в остальные узлы сети. В качестве П(х) для остальных узлов возьмем целое число, заведомобольшее длины кратчайшего пути из хо в х,Считаем какое-либо распределение потенциалов допустимым, если П(х) )П(х), гдеПгпп (х) - дл Р на кратчайшего пути из хц В хТогда задача состоит в определении Поц(х)для всех хЛ. Для каждой дуги или ребрарассмотрим величину:д(х,у) = д(у,х) =П(х) + а(х,у) - П(уа(х,у) = - а(у,х)и придадим ей ориентацию:от х к у, если П(х) + а(х,у) - П(У) ( Оот у к х, если П(х)+а(х,у) - П(У).ОТаким образом, каждой дуге или ребру(х, д) = (у, х) ставится в соответствие векторд(х, у). Будем называть вектор д(х, у) активным, если:а) (х, у) - ребро,б) (х, у) - дуга и ее ориентация совпадает с направленисм д(х У)Рассмотим множество Ъ узлов сети Л, А таких, что у1, если в у входит хотя бы одинактивный вектор. На каждом шаге процессаопределения кратчайшего пути будем одновременно понижать на единицу потенциалывсех узлов уГ Используя эту процедуруконечное число раз, в результате получаетсяП(х) =Пь(х) для хУ, причем после каждого шага процесса распределение потенциалов остается допустимым. От шага к шагу будут меняться значения д (х, у), ориентациявекторов д (х, у), само множество Р, т. е, активность векторов.Поставим в соответствие узлу хо потенциалП(хо)=О, а всем остальным узлам сети одини тот же потенциал По,гдеП 1 ) Пд (х) для хе%,Тогдад(хо х) = П - а(хх) для (хх)еЛ,Я(х,у) = а(х,у) для х,ухТаким образом, по исходной сети Л, А) получим сеть из векторов д(х, у). Вычислительный процесс нахождения кратчайшего пути в У, А с помощью векторов д (х, у) состоит из однотипных шагов.На каждом шаге вычитаем по единице из модулей векторов д(х, у), входящих в узлы 15 20 25 30 35 40 45 55 60 65 4у 1, и добавляем единицу к модулям всех векторов д(х, у), выходящих из узлов у ЯГ, Если на с-ом шаге дсп(х, у) =О, тоРа) да+(х, у) =1 и д(+(х, у) направлен от х к у, если на -ом шаге хР, а УЯ 1 и направлен от у к х, если на с-ом шаге х Р, уК, б) д+(х, у) =О, если на -ом шаге либо х Р и у Р, либо х Р и УК Процесс окончен, когда ни один из векторов д(х,у) не будет активным (Ъ=ф). При этом для всех дуг или ребер, принадлежащих дереву кратчайших путей, выполняется д(х, у) =О, и наоборот, если какой-нибудь путь (дерево) состоит из дуг, для которых д(х, у) =О, этот путь кратчайший (дерево кратчайших путей). Определение, путей максимальной длины (критических путей) по данному алгоритму сводится к выделению кратчайших путей, если для всех дуг исходной сети в качестве длины взять величину - а(х, у), т. е. изменить ее знак на противоположный.Модель дуги транспортной сети работает следующим образом, Величина д(х, у) записывается в реверсивный счетчик 1 по входу задания величины вектора 2. Направление вектора определяется состоянием триггера 8, а ориентация дуги задается потенциалами по входам задания ориентации дуги 4 и 5 (если (х, у) - ребро, то по этим входам подается отпирающий потенциал).Опишем работу модели дуги на ряде примеров1, Пусть (х,у) - ребро, вектор д(х,у) направлен от х к у (триггер 8 в состоянии 1, элементы И И, 15 открыты, а элементы И 16, 17 закрыты) и д(х, у) =1. Тогда элементы И 12, 18 закрыты потенциалом с выхода элемента И 10, элеменпгы И 18, 19 опкрыты по потенциальным входам, соединенным со входами задания ориентации дуги 4, 5 и выходом элемента НЕ 11, но элемент И 18 открыт потенциалом с единичного выхода триггера 8, а элемент И 19 закрыт по потенциальнсму входу, соединенному с нулевым выходом триггера 8. Если один из элементов И 18 или 19 открыт по всем своим потенциальным входам, то вектор д(х, у) - активный. Его активность проявляется при поступлении иъпульса по шине тактовых импульсов 25, который проходит элемент И 18 и поступает на выход модели дуги 22 (узел у). В тот же момент на выход модели дуги 22 (узел у) поступают импульсы и с других дискретных моделирующих элементов, если соответствующие векторы актввы и направлены в узел у. Все этц импульсы подаются одновременно (по шинам тактовых импульсов 25 каждого цз дискретных моделирующих элементов) и совпадают в узле у, образуя одинимпульс, который поступает на вход элемента задержки 9. В то же время импульс со входа модели дуги 21 (узла х), который попадает на нее, если хГ, постпает на вход элемента задержки б, затем на импульсный вход элемента И 14 и на вход сложения реверсивного счетчика 1, в результате чего к ,о(х, у) добавляется единица. Импульс из узла у попадает на вход вычитания реверсивнэго счетчика 1 на барс позже и единица вычитается из д(х, у). В результате вновь получаем д(х, у) =1. Рассмотрс случай, когда х 1 г и у .2. Если х Р, а уя 1, то д(х, у) уменьшается на единицу, если х Р, а у 1 - ,о(х, у) на единицу увеличивается, если ху и у 1 -- д(х, у) не изме,няется.Рассмотрим случай, когда д(х, у) =О. Тогда элементы И 18, 19 заперты потенциалом с выхода элемента НЕ 11, а элементы И 12, 13 открыты с выхода элемента И 10. Состояние триггера 3 в данный момент роли не играет, так как если хЬ,уЯ ), импульс входа модели дуг 21 (узла х) прежде всего проходит элемент И 12 и устанавливает триггер 3 в И, а если х Ъ, у Ъ, импульс с выхода модели дуги 22 (узла у) попадает (задерживаясь в элементе задержки 8 на 1) на вход элемента И 13, проходит его и устанавливает триггер 3 в 0. В обоих случаях импульс попадает только на вход сложения реверсивного счетчика 1. Получаем вектор д(х, у) (д(х, у) =1), направленный в ту или иную сторону в зависимости от того, из какого узла (х или у) пришел импульс,Пусть теперь о(х, у) =О, х Ъ и у К Тогда импульс со входа модели дуги 21 (узла х) устанавливает триггер 3 в 1, а через время 1 импульс с выхода модели дуги 22 (узла у) установит его в 0. Через время 21, импульсы поступят на входы элехентов И 14, 15,1 б,17 и пройдут через элементы И 1 б, 17, поэтому к содержимому реверсивного счетч 1 ка 1 сначала прибавится, а потом из него вычтется (через 1 с) по единице, т. е. д(х,у)=0.Таким образом при,нахождении кратчайших путей в реверсивные счетчики 1 надо задать пачальныс значения векторов д(х,у), по входу задания ориентации дуги 4 устанавливают опирающий потенциал, если (х, у) направлена от х к у, если (х,у) направлена от у к х, то отпирающий потенциал будет на входе задания ориентации дуги 5, если (х, у) = (у, х) ребро, то опирающий потенциал будет на обоих входах задания ориентации дуги 4 и 5. Триггер 3 устанавливаются в 0, если (х, у) дуга и д(х,у) направлен от х к у или (х,у) ребро,и в 1 с;ли д(х, у) направлен от у к х. После этого по шинам тактовых импульсов 25образющих исслсд с 1 ю сеть,псдают серию импульсов с астотой (1( до тех пор, пока состояние2 п+ ,смодели нс будет изменяться (т. е, Р= ф и импульсы нс появятся ни в одном узле сети).Дерево кратчайших путей фиксируется по нулевому коду в реверсивных счетчиках 1 или по загора 1 Пю лампочки 20. Режим определения критических путей отличается от описанного режсма определеия кратчайших путей только лишь установивсо 1 триггеров 3 в состоя- НИЯ, ПРОТИВОПЭЛОЯСИЫЕК 232 ИНЫМ ВЫШЕ.Предмет изобретенияМодель дуги транспортной сети, содержа щая тригер, элементы И, элементы задержки, элемент НЕ и реверсивный счетчик, отличаОщаяся тем, что, с целью расширения круга решаемых задач, в ней единичный и нулевой входы триггера через первый и второй 25 элементы И подключены к выходу третьегоэлемеснта И, соединенного входами с выходами реверсивного счетчика, а выходом через элемент НЕ - со входами четвертого и пятого элементов И, импульсные входы которых соед 1 Псны с шиной т 2 ктпрующпх импульсов, а третьи входы соединены с соответствующими входами задания ориентации дуги, нулевой выход триггера соединен со входами шестого и седьмого элемента И и четвертым входом четвертого элемента И, второй вход второго элемента И через первый элемент 32 ДЕРЖКИ ПОДКЛЮсЕИ К ВЫХОДУ МОДЕ,1 И ДУГИ, который соединен со входом второго элемента задеркки, выход четвертого элемента И и 40 второй вход первого элемента И подключены ко входу модели дуги, который соединен со входом третьего элемента задержки, выход которого через восьмой элемент И соединен с суммцпр ющим вх дом резерсивного счетчи ка, а через седыой элемент И и четвертыйэлемент задержки - с его вычитающим входом, единичный выход триггера соедшен со вторым входом восьмого, первым входом девятого и четвертым входом пятого элемента И, 50ВЫХОД КОГОРОГО ПОДКЛЮЧЕН К ВЫХОДТ МОДЕЛИ дуги, выход второго элемента задержки через девятый элеме 1 т И соединен со входом четвертого элемента задержки и через шестой элемент И подключен к суммирующему входу реверсивного счетчика, который присоединен ко входу задания величины вектора, единичный и нулевой входы триггера соединены с соотвстствуОиПми входами задания направления вектора.Заказ 3214/1 Изд. Мо 873 Тираж 647 Подписное ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий Москва, Ж, Раушская наб., д. 4/5 Типография, пр. Сапунова, 2