В пт бi-. ..• я г.пс^г'гг'-'^йрt45jbl teyhlf i&
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Союз Советских
Социалистических
Республик
Зависимое от авт. свидетельства, №вЂ”
Заявлено ОЗ.XI1.1970 (№ 1499640/18-24}
М. Кл. 6 06f 1 5„i20 с присоединением заявки №
Приоритет—
Государственный комитет
Совета Министров СССР па делам изаоретений и открытий
Опубликовано 23.Ч.1973. Бюллетень № 23
Дата опубликования описанпя 10.XI1.1973
УДК 681.333 (088.,8) Авторы изобретения
А. А. Илюхин, А. П. Киселев и А. М. Плахотишин
Московский ордена Трудового Красного Знамени инженерно-физический институт
Заяви гель
ВПТУ
МОДЕЛЬ ДУГИ ТРАНСПОРТНОЙ СЕТИ
Изобретение относится к области вычислительной техники. Известны модели дуги транспортной сети, содержащие триггер, элементы
«И», элементы задержки, элемент «НЕ» и реверсивный счетчик.
Все известные модели моделируют работу ориентированных дуг графов, имеющих неотрицательную длину.
В предложенном устройстве указанные недостатки исключены.
Модель дуги отличается от известных тем, что в ней единичный и нулевой входы триггера через первый и второй элементы «И» под ключены к выходу третьего элемента «И», соединенного входами с выходами реверсивного счетчика, а выходом через элемент «HE» — со входами четвертого и пятого элементов «И», импульсные входы которых соединены с шиной тактирующих импульсов, а третьи входы соединены с соответствующими входами задания ориентации дуги, нулевой выход триггсра соединен со входами шестого и седьмого элемента «И» и четвертым входом четвертого элемента «И», второй вход второго элемента «И» через первый элемент задержки подключен к выходу модели дуги, который соединен со входом второго элемента задержки, выход четвертого элемента «И» и второй вход первого элемента «И» подключены ко входу модели дуги, который соединен со входом третьего элемента задержки, выход которого через восьмой элемент «И» соединен с суммирующим входом реверсивного счетчика, а через седьмой эле5 мент «И» и четвертый элемент задержки — с его вычитающим входом, единичный выход триггера сосдинсн со вторым входом восьмого, первым входом девятого и четвертым входом пятого элемента «И», выход которого подключен к выходу модели дуги, выход второго элемента задержки через де вятый элемент «И» соединен со входом четвертого элемента задержки и через шестой элемент «И» подключен к суммирующему входу реверсивного счетчика, который присосдинен ко входу задания величины вектора, единичный и нулевой входы триггера соединены с соответствующими входами задания направления вектора.
Схема модели дуги транспортной сети приведена на чертеже. Модель содержит реверспвный счетчик 1, вход задания величины вектора 2, триггер 8, входы задания ориентации дуги 4 и 5, элементы задержки 6 — 9, элемент
«И» !О, элемент «НЕ» 11, элементы «И» 12—
19, индикатор 20, вход модели дуп1 21, выход модели дуги 22, входы задания направления векторов 23 и 24, шину тактовых импульсов 25.
Логика работы модели дуги описывается следующим алгоритмом определения экстре30 мальных путей в транспортных сетях.
383053
Пусть имеется исходная транспортная сеть (A, А), где Л вЂ” множество узлов, А — множество дуг. Каждой дуге (х, у) я (Л, А) соответствует ее длина а (х, у) (если (х, у) — неориентированное ребро, то а(х,у) = — а(у,х), причем а(х,у) может быть как положительна, так и отрицательна.
Присвоим каждому узлу х сети (Л, А) потенциал 17(x), причем П(хо) =О, где xo — узел, из которого ищется кратчайший путь в остальные узлы сети. В качестве П(х) для осталbных узлов возьмем целое число, за ведомо большее длины кратчайшего пути из хо в х.
Считаем какое-либо распределение потенциалов допустимым, если П(х) = П„,;„(х), где
П„„„(х) — длина .кратчайшего пути из X() в х.
Тогда задача состоит в определении П; (х) для всех x Таким образом, каждой дуге или ребру (х, g) =(g, х) ставится в соответствие вектор О g(x, у). Будем называть вектор д(х, у) активным, если: а) (х, у) — ребро, б) (х, у) — дуга и ее ориентация совпадает с направлением g(x,у). Рассмотим множество V узлов сети (N, А) таких, что у (-: V, если в у входит хотя бы один активный вектор. На каждом шаге процесса определения кратчайшего пути будем одно|временно понижать на единицу потенциалы всех узлов у U. Используя эту процедуру конечное число раз, в результате получается П(х) =П;„(х) для хяУ, причем после каждого шага процесса распределение потенциалов остается допустимым. От шага к шагу будут меняться значения g (х, у), ориентация векторов g (х, у), само множество V, т. е. активность векторов. Поставим в соответствие узлу хо потенциал П(хо) =О, а всем остальным узлам сети один и тот же потенциал П о, где П< ) П,д,„(х) для хвЖ. Тогда я(х„х) = П(> — а(хо,х) для (х„х)еА (д(х,у) = а(х,у) для х,у +х,. Таким образом, по исходной сети (N, А) получим сеть из векторов g(x, у). Вычислительный процесс нахождения кратчайшего пути в (N, А) с помощью векторов р (х, у) состоит из однотипных шагов. На каждом шаге вычитаем по единице из модулей векторов g(x, у), входящих в узлы 65 у g V, и добавляем единицу к модулям всех векторо в g (х, у), выходящих из узлов у gV. Если на -ом шаге д<0(х, у) =О, то — > а) g + (õ, у) =1 и g + (x, у) направлен от х к у, если на i-ом шаге xqV, à ggV и направлен от у к х, если на i-ом шаге xg V, g @ V, б) дх - (õ, у) =О, если íà i-ом шаге либо х V и у V, либо х V u ggV. Процесс окончен, когда ни один из векторов д(х,у) не будет активным (V=ф). При этом для всех дуг или ребер, принадлежащих дереву кратчайших путей, выполняется о (х, у) =О, и наоборот, если какой-нибудь путь (дерево) состоит из дуг, для которых g(x, у) =О, этот путь кратчайший (дерево кратчайших путей). Определение, путей максимальной длины (критических путей) по данному алгоритму сводится к выделению кратчайших путей, если для всех дуг исходной сети в качестве длины взять величину — а(х, у), т. е. изменить ее знак на противоположный. Модель дуги транспортной сети работает следующим образом. Величина g (x, у) записывается в реверсивный счетчик 1 по входу задан 1я величины вектора 2. Направление вектора определяется состоянием триггера 8, а ориентация дуги задается потенциалами по входам задания ориентации дуги 4 и 5 (если (х, у) — ребро, то по этим входам подается отпирающий потенциал). Опишем работу модели дуги на ряде примеров. 1. Пусть (х, у) — ребро, вектор g(x, у) направлен от х к у (триггер 8 в состоянии «1», элементы «И» 14, 15 открыты, а элементы «И» 15, 17 закрыты) и g(x, у) =1. Тогда элементы «И» 12, 18 закрыты потенциалом с выхода элемента «И» 10, элементы «И» 18, 19 QTIK pbIты по потенциальным входам, соединенным со входами задания ориентации дуги 4, 5 и выходом элемента «НЕ» 11, но элемент «И» 18 открыт потенциалом с единичного выхода триггера,3, а элемент «И» 19 закрыт по потенциальнсму входу, соединенному с нулевым выходом трпггера 3. Если один из элементов «И» 18 или 19 открыт по всем своим потенциальным входам, то вектор g(x,у) — активный. Его активность проявляется при поступлении импульса по шине тактовых им пульсов 25, который проходит элемент «И» 18 и поступает на выход модели дуги 22 (узел у). В тот жс момент на выход модели дуги 22 (узел у) поступают импульсы и с других дискрегных моделирующих элементов, если соответствующие векторы активны и направлены в узел у. Все эти импульсы подаются одновременно (по шинам тактовых им пульсов 25 каждого из дискретных моделирующих элементов) и совпадают в узле у, образуя один 383053 импульс, который поступает на вход элемента задержки 9. В то же время импульc co Входа модели дуги 21 (узла х), который попадает на нее, если х(-. V, пост пает на вход элемента задержки б, затем на импульсный вход элемента «И» 14 и на вход сложения реверсивного счетчика 1, в результате чего к g(x, у) добавляется единица. Импульс из узла у попадает на вход вычитания реверсивнэго счетчика 1 íà t„, позже и единица вычитается из g(x, у). В результате вновь получаем g (x, у) = 1. Рассмотрс случай, когда хqV и у -. V. 2. Если х V, а у(-: V, то g(x, у) уменьшается на единицу, если х V, а у(-.- V — g(x, у) на единицу увеличивается, если х g у и у g V— — g(x, у) не изме.няется. Рассмотрим случай, когда g(x, у) =О. Тогда элементы «И» 18, 19 заперты потенциалом с выхода элемента «НЕ» 11, а элементы «И» 12, 18 открыты с выхода элемента «И» 10. Состояние триггера 8 в данный момент роли не играет, так как если xgV, у я V, импульс входа модели дуг!! 21 (узла х) прежде всего проходит элемент «И» 12 и устанавливает триггер 3 в «И», а если х U, у g V, импульс с выхода модели дуги 22 (узла у) попадает (задерживаясь .в элементе задержки 8 на 1„) на вход элемента «И» 18, проходит его и устанавливает триггер 3 в «0». В обоих случаях импульс попадает только на вход сложения реверсивного счетчика 1. Получаем вектор д(х, у) (д(х, у) =1), направленный в ту или иную сторону в зависимости от того, из какого узла (х или у) пришел импульс. Пусть теперь g(x, у) =О, х(-. U и у(-. V. Тогда импульс со входа модели дуги 21 (узла х) устанавливает триггер 3 в «1», а через время 4 импульс с выхода модели дуг!! 22 (узла у) установит его в «О». Через время 24 импульсы поступят на входы элех!енто в «И» 14, 15,1б,17 и пройдут через элементы «И» 16, 17, поэтому к содержимому реверсивного счетчика 1 сначала приба!вится, а потом из него вычтется (через t ) по единице, т. е. g(x, у) =0. Таким образом при,нахождении кратчайших путей в реверсивные счетчики 1 надо задать пачальныс значения векторов g(x, у), по входу задания ориентации дуги 4 устанавливают опирающий потенциал, если (х, у) направлена от х к у, если (х, у) направлена от у к х, то отпирающий потенциал будет на входе задания ориентации дуги 5, если (х, у) = (у, х) ребро, то опирающий потенциал будет на обоих входах задания ориентации дуги 4 и 5. Триггер 8 устанавливаются в «О», если (х, у) дуга > и g(x, у) направлен от х к у или (х,у) ребро, Il iB <<1>> С .,III а (Л, 1/) Нанрапчсп ОТ 1/ 1С Х. ПОСле этого по шинам тактовых импульсов 25 всех схем, образующих исследуемую сеть, псдают сер:1ю 11мпульсо в с 1астотой f(1 (до тех пор, пока состояние 2 „+- tl модели нс будет изменяться (т. е.. U= ф и импульсы нс появятся нн в одном узле сети). Дерево кратчайших путей фиксируется по нулевому коду в реверсивных счетчиках 1 нли по загора11ню лампочки 20. Режим определения критических путей отличается от описанного реж11ма определения кратча 1!I!IIx путей только лишь установкой триггеров 8 в состояния, прот11воположные < казанным выше. Предмет изобретения Модель дуги транспортной сети, содержа20 щая триггер, элементы «И», элементы задержк и, элемент «НЕ» и реверсивный счетчик, отлича/Ощаяся тем, что, с целью расширения круга решаемых задач, в ней единичный и нулевой входы триггера через первый и второй 25 элементы «И» подключены к выходу третьего элемента «И», соединенного входамн с выходами реверсивного счетчика, а выходом через элемент «НЕ» — со входами четвертого и пятого элементов «И», импульсные входы которых соедпнс1ы с ш;шой тактирующих импульсов, а третьи входы соединены с соответствующими входамп задания ориентации дуги, нулевой выход триггера соединен со входами шестого и седьмого элемента «И» и четвертым входом четвертого элемента «И», второй .вход второго элемента «И» через первый элемент задерж1с11 подклю 40 второй вход первого элемента «И» подключены ко входу модели дуги, который соединен со входом третьего элемента задержки, выход которого через восьмой элемент «И» соединен с сумм/,р3 ющ1!м входом p<3cpc!IBHoI о счетчи45 ка, а через седьмой элемент «И» и четвертый элемент задержки — с егo вычитающим Входом, единичный выход триггера соединен со вторым входом восьмого, первым входом девятого и чет вертым входом пятого элемента «И», 50 выход которого подключен к выходу модели дуги, выход второго элемента задержки через девятый элеме11т «И» соединен со входом четвертого элемента задержки и через шестой элемент «И» подключен к суммирующему вхо55 ду ревсрсив11ого счетчика, который присоединен ко входу задания величины вектора, единичный и нулевой входы триггера соединены с соотвстству1он!1!ми входами задания направления вектора. 383053 Составитель Г. Сорокин Редактор С. Авдеева Техред E. Борисова 1(орректоры: В. Петрова и E. Давыдкина Заказ 3214/1 Изд. № 873 Тираж 647 Подписное ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий Москва, Ж-35, Раушская наб., д. 4/5 Типография, пр. Сапунова, 2
