В ПТ Бi-. ..• я Г.ПС^Г'ГГ'-'^Йрt45jbl teyHLf i& Советский патент 1973 года по МПК G06F15/173 

Изобретение относится к области вычислительной техники. Известны модели дуги трансиортной сети, содержащие триггер, элементы «И, элементы задержки, элемент «НЕ и реверсивный счетчик. Все известные модели моделируют работу ориентированных дуг графов, имеющих неотрицательную длину. В предложенном устройст1ве указанные недостатки исключены. Модель дуги отличается от известных тем, что в ней единичный и нулевой входы триггера через первый и второй элементы «И подключены к выходу третьего элемента «И, соединенного входами с выходами реверсивного счетчика, а выходом через элемент «НЕ - со входами четвертого и пятого элементов «И, импульсные входы которых соединены с шиной тактирующих импульсов, а третьи входы соединены с соответствующими входами задания ориентации дуги, нулевой выход триггера соединен со входами шестого и седьмого элемента «И и четвертым входом четвертого элемента «И, второй вход второго элемента «И через первый элемент задержки нодключен к выходу модели дуги, который соединен со входом второго элемента задержки, выход четвертого элемента «И и второй вход первого элемента «И подключены ко еходу модели дуги, который соединен со входом третьего элемента задержки, выход которого через восьмой элемент «И соединен с суммирующим входом реверсивного счетчика, а через седьмой элемент «И и четвертый элемент задержки--с его вычитающим входом, единичный выход триггера соединен со вторым входом восьмого, первым входом девятого и четвертым входом пятого элемента «И, выход которого подключен к выходу модели дуги, выход второго элемента задержки через девятый элемент «И соединен со входом четвертого элемента задержки и через шестой элемент «И нодключен к суммирующему входу реверсивного счетчика, который присоединен ко входу задания величины вектора, единичный и нулевой входы триггера соединены с соответствующими входами задания направления вектора. Схема модели дуги транспортной сети приведена на чертеже. Модель содержит реверсивный счетчик 1, вход задания величины вектора 2, триггер 3, входы задания ориентации дуги 4 и 5, элементы задержки 6-9, элемент «И 10, элемент «НЕ 11, элементы «И 12- 19, индикатор 20, вход модели дуги 21, выход модели дуги 22, входы задания направления векторов 23 и 24, шину тактовых импульсов 25. Логика работы модели дуги описывается следующим алгоритмом определения экстремальных путей в транспортных сетях. Пусть имеется исходная тра«спо,ртиая сеть Л , Л, где Л - множество узлов, Л - множество дуг. Каждой дуге (х, у) Q {N, А соответствует ее дли.иа а (х, у) (если (х, у) -неориентированное ребро, то а(х,у):-а(у,х), приче м а(х,у) может быть как положительна, THiK и отрицательна. Присвоим каждому узлу х сети Л , Л нотенциал П(х), лричем П(, где Хо - узел, из которого И|Щется кратчайший путь в остальные узлы сети. В качестве П(х) для остальных узлов возьмем целое число, заведомо большее длины кратчайшего пути из Хо в х. Считаем какое-либо распределение потенциалов допустимым, если П(х)Пшш{х), где f7mm(x) -длина кратчайшего пути из Хо в х. Тогда задача состоит в определении Птт(х) для всех xQN. Для каждой дуги или ребра рассмотрим величину: g(x,y) - g(y,x) I Щх) + а(х,у) - /7((/)| а{х,у ) - - а(у,х) и придадим ей ориентацию: от: X к у, если Л(х) + а(х,у) - П(у) О, ot у к X, если П(х) + а(х,у)П(у)0. Таким образом, каждой дуге или ребру (х, g) (у, х) ставится в соответствие вектор g(x, у). Будем называть вектор g(x, у) активным, если: а)(х, у)- ребро, б)(х, у)- луга и ее ориентация совпадает с направлением g(x,y). Рассмотим множество V узлов сети Л , Л таких, что у Q V, если в у входит хотя бы один активный вектор. На каждом шаге процесса определения кратчайшего пути будем одновременно понижать на единицу потенциалы всех узлов у Q V. Используя эту процедуру конечное число раз, в результате получается П(х) (х) для XQN, причем после каждого шага процесса распределение потенциалов остается до-пустимым. От шага к шагу будут меняться значения g (х, у), ориентация векторов g (х, у), само множество V, т. е. активность векторов. По:ста.вИМ в соответствие узлу Хо потенциал П(хо) 0, а всем остальным узлам сети одш1 и тот же потенциал Я(°, где П(,;(х) для xeN. Тогда / () - ° а(Хо,х) для (д:„,д:)бЛ, 1 g(-,i/) а(х,у) для х,у дго. Таким образом, по исходной сети Л Л получим сеть из векторов (л:, у). Вычислительный процесс нахождения кратчайшего пути в Я, Л с помошью векторов g(x,y) состоит из однотипных шагов. На -каждом шаге вычитаем по единице из модулей векторов g(x, у), входящих в узлы УG V, и добавляем единицу к модулям всех векторов g(x,y), еыходящ 1х из узлов г/gl/. Если на г-ом шаге (x, у) , то а)g-(+(x, г/) 1 и §(+(л;, у) направлен от х к у, если па г-ом шаге XQV, а yQV и направлен от у к X, если на г-ом шаге A:gl/,(/gl/, б)((л;, у) 0, если на /-ом шаге либо X V н yQV, либо XQV и yQV. Процесс окончен, когда ни один из векторов g(x,y) не б}лет активным (). При этом для всех дуг или ребер, принадлежащих дереву кратчайших путей, выполняется g{x, у)0, и нао.борот, если какой-нибудь путь (дерево) состоит из дуг, для которых g(x, г/)0, этот путь кратчайший (дерево кратчайших путей). Определение лутей максимальной длины (критических путей) по данному алгоритму сводится к выделению кратчайших путей, если для всех дуг исходной сети в качестве длины взять величину -а(х, у), т. е. изменить ее знак на противоположный. Модель дуги транспортной сети работает следующим образом. Величина g,(x у) записывается в реверсивный счетчик У по входу задания величины вектора 2. Направление вектора определяется состоянием триггера 3, а ориентация задается потенциалами по входам задания ориентации дуги 4 и 5 (если (х, у)-ребро, то по эти.м входам подается отпирающий потенциал). Опишем работу модели дуги на ряде примеров. 1. Пусть (х, у)-ребро, вектор g(x,y) нанравлен от х к у (трнггер 3 в состоянии «1, элементы «И 14, 15 открыты, а элементы «И 16, 17 закрыты) и g(x, г/) 1. Тогда элементы «И 12, 13 закрыты потенциалом с выхода элемента «И 10, элементы «И 18, 19 открыты но потенциальным входам, соединенным со входами задания ориентации дуги 4, 5 ii выходом элемента «НЕ 11, но элемент «И 18 открыт иотепциалом с единичного выхода триггера 3, а элемент «Н 19 закрыт по потенциальному входу, соединенному с нулевым выходом триггера 3. Если один из элементов «Н 18 или 19 открыт по всем свонм потенциальным входам, то вектор g(x,y) - активный. Его активность проявляется при поступлении импульса по шине тактовых импульсов 25, который преходит элемент «Н 18 и поступает иа выход модели дуги 22 (узел у). В тот же момент на выход модели дуги 22 (узел у) поступают имнульсы и с других дискретных моделирующих элементов, если соответствующие векторы активны и .направлены в узел у. Все эти импульсы нодаются одновременно (по шинам тактовых имшульсов 25 каждого из дискретных моделирующих элементов) и совпадают в узле у, образуя один

импульс, который поступает па вход элемента задержки 9. В то же время импульс со входа модели дуги 21 (узла к), который попадает па нее, если xQV, поступает па вход элемента задержки 6, затем на импульсный вход элемепта «И 14 п па вход сложепия реверсивного счетч.ика 1, в результате чего к g(x, у) добавляется единица. Имлульс из узла у попадает на вход вычитапия реверсивного счетчика / на рс позже и едип1ица вычитается из g(x, у). В .результате вповь получаем g(x, у) . Рассмотре случай, когда XQV и yQV .

2. Если XQV, а г/g У, то g(x, у) уменьшается на единицу, если , а yQV-gix, у) на единицу увеличивается, если xQyiiyQV - -S( у) не изменяется.

Рассмотрим случай, когда g(x, у)0. Тогда элементы «И 18, 19 заперты потепциалом с выхода элемента «НЕ 11, а элементы «И 12, 13 открыты с выхода элемента «И 10. Состояние триггера 3 в даиный момент роли не играет, так как если xQV,yQ V, им.пульс входа модели дуги 21 (узла х.} прежде всего проходит элемеит «И 12 и устанавливает триггер 3 в «И, а если xg V, yQV, импульс с выхода модели дуги 22 (узла у) попадает (задерживаясь в элементе задержки 8 па /,J на вход элемента «И 13, проходит его и станаВЛ1И,вает триггер 3 в «О. В обоих случаях импульс попадает только на вход сложения реверсивного счетчика 1. Получаем вектор g(x, у) {§( У) ), направленный в ту или иную сторопу в зависимости от того, из какого узла (л; или у) пришел импульс.

Пусть теперь g(x, у) 0, xQ V и yQV. Тогда импульс со входа .модели дуги 21 (узла х) устапавл.ивает триггер 3 в «1, а через время /п импульс с выхода модели дуги 22 (узла у) установит его в «О. Через время 2tn импульсы поступят на входы элементов «И 14,15,16,17 и пройдут через элементы «И 16, 17, поэтому к содержимому реверсивного счетчика 1 сначала прибавится, а потом из него вычтется (через ) по едипице, т. е. g(x,y) Q. Таким образом при нахождении кратчайших путей .в реверсивные счетчики / падо

дать пачальные значения векторов g(x,y), по входу задания ориентации дуги 4 устанавливают опирающий потенциал, если (х,у направлена от д: к г/, если (х, у) направлена от у к X, то отпирающий потенциал будет на входе задания ориентации дуги 5, если х, у (t/, х ребро, то опирающий потенциал будет на обоих входах задания ориентации дуги 4 и 5. Триггер 3 устанавливаются в «О, если (х, у) дуга

и g(x,y) иаправлеп от х к у или (х,у) ребро.

и в «i если g(x,y) паправлеи от у к .v. После этого по шинам тактовых импульсов 25 всех схем, образующих исследуемую сеть, подают серию пмпульсов с частотой

1

до тех пор, пока состояние

2t,, + г;, с

модели не будет изменяться (т. е.- У 0 и импульсы не появятся пи в одиом узле сети).

Дерево кратчайших путей фпксируется по нулевому коду в реверсивных счетчнках / или по загоранию лампочки 20. Режим определения критических путей отличается от описанного режима определения кратчайш:их путей

только лишь становкой триггеров 3 в состояния, противоположные указанным выше.

Предмет и з о б р е т е н и я

Модель дуги транспортной сети, содержащая триггер, элемеиты «И, элементы задержки, элемент «ПЕ и реверсивный счетчик, отличающаяся тем, что, с целью расширения круга решаемых задач, в ней единичный и нулевой входы триггера через первый и второй

элементы «И подключены к выходу третьего элемента «И, соединенного входами с выходами реверсивно.го счетчика, а выходом через элемент входами четвертого и пятого элементов «И, импульсные входы которых соединены с шииой тактирующих имнульсов, а третьи входы соединены с соответствуюшими входами задания ориентации дуги, нулевой выход триггера соединен со входами шестого и седьмого элемента «И и четвертым

входом четвертого элемента «И, второй вход второго элемента «П через первый элемент задержки по.дключен к выходу модели дуги, который соединен со входом второго элемента задерж,ки, выход четвертого элемента «И н второй вход первого элемента «И подключены ко входу моделп дуги, который соединен со входом третьего элемента задержки, выход которого через восьмой элемент «И соединен с сумм;;;рующим входом резерсивного счетчнка, а через седьмой эле.мепт «Н н четвертый элемент задерж.кп - с его вычитающим входом, единичный выход триггера соединен со вторым входом восьмого, первым входом девятого н четвертым входом пятого элемента «И, выход которого подключеп к выходу модели дуги, выход второго элемента задержки через девятый элемент «Н соединен со входод четвертого элемента задержки и через щестой элемент «Н подключен к суммирующему входу реверснвиого счетчика, который присоединен ко входу задания велнчпны вектора, единичный и пулевой входы триггера с соответствующими входами задания направления вектора.