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

. соециненьвременных соответст единицы с ветви гра объединен ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТЧРЫТИ ОПИСАНИЕ АВТОРСКОМУ СВИД(46) 30.10.83. Бюл; И 2 40 (72) В, К. Попков и В, К. Репин (71) Научно-исследовательский, проектиоконструкторский и технологический институт комплектного электропривоаа (53) 681.333(088.8)(56) 1. Авторское свидетельство СССР % 470811, кл.06 - 15/20 1975,2. Авторское свипетельство СССР Ж 422002, кл, Я 06 Я 7/48, 1974 (прототип) .(54)(57) Устройство для модля, РОВАния кРАтчАЙших путей нА ГРАФАХ, соаержвшее блок из п мопелей ветвей по числу ветвей моделируемого графа, каждая из которых состоит из зваатчиков адресов начального и кднеч ного узлов, формирователя временных интервалов, элемента И и триггера, блок формирования топологии, содержащий первый и второй элементы И, элемент ИЛИ и элемент НЕ, генератор импульсов, первый и второй выходы которого подключены к первому вхоцу первого элемен та И блока формирования топологии и первому вхоау второго элемента И био ка формирования топологии, выход эле мента ИЛИ блока. формирования топологии поаключен к второму входу первого элемента И блока формирования тополо гии и через элемент НЕ - к второму входу второго элемента. И блока формырования топологии, выхоц второго эле мента И блока формирования топологии соединен с информационными вхоцами формировв телей временных интервалов кажаой модели ветви, выхоцы моделей ветвей поцключены к соответствующим вхопам элемента ИЛИ блока формироввния топологии, о т л и ч а ю щ е е с ятем,-.что, с целью повышения, быстродействия устройства, в блок формирования топологии дополнительно введеныгруппа иэ 11 элементов И (гае И - чиоло моаелей ветвей) и узел выаеленияепиницы старшего разряда коцв адресаветви графа, а в мдели ветвей - группы иэ.в элементов И (гпе 1 т 1 - числоразрядов адреса узла графа), причемкаждый.звцатчик впреса начального иконечного узлов каждой моцели ветвисоцержит регистр аареса и схему сравнения, первые вхоцы схем сравнения,1являющиеся вхоаами зацатчиков адресовузлов, объединены и поцключены к выходам элементов И групп кажаой моцели,ветви, вторые вхоцы схем сравнения зацатчиков адресов начальных узлов соепинены с выхоаами регистров вцреса начальных узлов, а выхоаы - с управляюшими вхоцами формирователей временных интервалов, вторые входы схем сравнениязацатчиков апресов конечных узлов подключены к выхоаам регистров апресов коночных узлов и первым входам элементов И групп соответствующей моделиветни, выходы схем сравнения зацатчиков ацресов конечных узлов квжаой мо дели ветви соединены с вхоцами триг- геров, выхоцы которых подключены к 3: первым вхоаам элементов И соответству: кзцей ивели ветви вторые входы которыхс выходами формирователейинтервалов, а выхоцы - свуюшим вхоаом узла вьшелениятаршего разряда кода ацресафа блока формирования топологии,ным с оцноименньм входомэлемента ИЛИ блока формирования топо логии, выходы узла выделения единицы старшего раэряца кода ацреса ветви графа соединены с первыми входами элементов И группы блока формирования топологии, вторые входы которых подключены к вьлоду первого элемента И блока формированиятопологии, в выходы соединены свторыми входами элементов И группсоответствующих моделей ветвейграфа.20 Наиболее близким по технической сущности к предлагаемому является устройство цля моделирования сетевых графиков, соцержашее блок управления,Изобретение относится к вычислительной технике, в частности кустройствам для моделирования кратчайших путей на графах.Известна модель ветви графа, содер жашая генератор импульсов, формирова тель временного интервала, выход которого поцключен к информационному входу первого элемента И, выход которого соединен с единичным вхоцом первого триггера, единичный выход которого поцключен к первому входу второго элемента И, выхоц которого соединен с соответствуюшим входом первого элемента ИЛИ, выхоц которого подключен к входу первого инвертора и к первому входу третьего элемента И, выход которого поцключен к первому вхоцу второго элемента ИЛИ, выхоц которого соединен с первыми вхоцами блоков задания начального и конечного адресов, блок управления, первый вхоц которого поцключен к второму вхоцу четвертого элемента ИЛИ, второй выход соединен с.вторым входом второго элемента ИЛИ, первый выход генератора импульсов под- ключен к второму входу третьего элемента И, второй выхоц генератора импульсов соединен с первым входом сець мого элемента И, второй вход которого 30 подключен к выходу первого инвертора, выход сецьмого элемента И соединен с первым вхоцом формирователя временного интервала, выход блока зацания началь ного адреса подключен к третьему входу пятого элемента И, второй вход которого соединен с вторым вхоцом четвертого , элемента И ЦОднако устройство не позволяет моделировать кратчайшие пути на графах. 40первый выхоц которого подключен к первому входу первого элемента ИЛИ блока формирования топологии, блок моделей ветвей по числу работ сетевого графика, каждая из которых выполнена в вице зацатчиков ацресов, выходами соединенных с элементами И, причем выхоц первого элемента И соединен с входом формирователя временных интервалов, вход второго элемента И соединен через инвертор с первым вхоцом элемента ИЛИ, к второму входу которого поцключен выхоц второго элемента И, генератор импульсов, первый и второй выходы которого подключены соответственно к второму входу первого элемента И каждой модели ветви и к первому вхоцу первого элемен та И блока формирования топологии, второй вход которого соецинен с вхоцом инвертора блока формирования топологии, кажцая моцель ветви содержит триггеры, входы которых соединены с формирователем временных. интервалов, причем второй вхоц первого триггера поцФключен к первому вхоцу второго элемента И, к второму входу которого и к третьему вхоцу первого элемента И подключены выходы второго триггера, входы зацатчиков адресов каждой модели ветви соединены с выходом первого элемента ИЛИ блока формирования топологии, содержащего второй элемент ИЛИ, поцключенный через инвертор к второму элементу И и последовательно соединенные третий элемент И и третий элемент ИЛИ, выход и вход которого поцклю чены соответственно к входу и второму выходу блока управления, причем первый выход генератора импульсов соединен с вторым вхоцом второго элемента И блока формирования топологии, выход которого подключен к входу формирователя временных интервалов каждой моцели ветви, вход блока управления соецинен с чет 3 1081 вертым входом первого элемента И каждой моцели ветви, выход первоготриггера каждой модели ветви подключен к входу второго элемента ИЛИ блока формирования топологии, а выхоц второго элемента ИЛИ каждой модели ветви соединен с входом третьего элемента И блока формирования топологии 2Недостатком устройства я.ляется низкое быстродействие эа счет больших заъ рот времени на моделирование адресов при .формировании топологии исследуемого графа.Цель изобретения - увеличение быстродействия устройства при моцелированяи 15кратчайших путей на .графах.,г.Указанная цель достигается тем, что в устройство, цля моцелирования краъчайших путеф на графах, соцержашееблок из п,моцелей ветвей по числу ветвей моцедируемого графа, каждая из которых состоит иэ эадатчиков адресов начального и конечного узлов, формирователя временных интервалов, элемента И и триггера, блок формирования топологии, . содержащий первый и второй элементы И, элемент ИЛИ и элемент НЕ, генератор импульсов, первый и второй выходы кото 1 рого подключены соответственно к первому входу первого элемента И блока формирования топологии и первому входу второго элемента И блока формирования топологии, выход элемента ИЛИ блока формирования топологии подключен к второму входу первого элемента И ао ка формирования топологии и через зле мент НЕ - к второму вхоцу второго элемента И блока формирования топологии,выхоц второго элемента И блока формирования топологии соединен с информацион ными входами формирователей временнык интервалов каждой модели ветви, выходы моделей ветвей поцключены к соответ ствующим вхоцам элемента ИЛИ блока формирования топологии, в блок формиро 45 вания топологии дополнительно введены группа иэ,Ф 1 элементов И (где и - числомоцелей ветвей) и узел выделения еця . ницы стариего разряцакоде адреса вет ви графа, в моцели ветвей - группы изп 5 О элементов И (гце В - число разрядов едресв узла графе), причем каждый задатчик адреса начального н конечного узлов каждой модели ветви содержит регистр адреса и схему сравнения, первые 55 входы схем сравнения, являющиеся вхо дами эацатчиков адресов узлов, объединены и поцключены к выходам эдемен,тов И групп кажцой модели ветви, вторые входы схем сравнения эацатчиковадресов начальнык узлов соединены с выходами ре гис тров адреса начальных узлов,ф 4а выходы - с управляюшимя входами фонмирователей временных интервалов, вторые входы схем сравнения зацатчиковадресов конечных узлов подключены квыходам регистров адресов конечных уэлов и первым вхоцам элементов И группсоответствующей моцели ветви, выходысхем сравнения эадетчиков ацресов конечных.уэлов каждой модели ветви соединены с входами триггеров, выходы оторых поцкдючены к первым входамэлементов И соответствующей моделиветви, вторые входы которых соединеныс выходами формирователей временныхинтервалов, а выходы - с соответствующим входом узла вьщеления единицыстаршего раэряца кода ацреса ветвиграфа блоха формирования топология,обьединенным с одноименным входомэлемента ИЛИ блока формирования топологии, выходы узла выделения единицыстаршего разряда кода адресе ветви графасоединены с первыми входами элементов И группы блока формирования топологии, вторые входы которых подключены к выходу первого элемента И блокаформирования топологии, а выхоцы соецинены с вторыми входами элементов Игрупп соответствующих моделей ветвейграфа,На фиг. 1 дана функциональная схемаустройства для моделирования кратчайших путей на графах; на фиг. 2 - пример исполнения устройства цдя моделирования кратчайших путей на графе, имеющем четыре ветви и четыре узда нафиг. 3 - пример исследуемого графамина фиг. 4 - временная циаграмма рабош.устройства при моцедировании кратчайнк.го пути в графе, привеценном нафиг, 3,Устройство (фиг. 1) содержит блок из и моцелей ветвей 1 по числу ветвей моделируемого графа, каждая иэ которых выполнена в вице зацатчиков 2 ацресов начальных узлов и эацетчиков 3 адресов конечв .; узлов, формирователя 4 временных интервалов, элемента И 5, триг гера 6 и группы 7 элементов И по числу разрядов кодов адресов узлов графа;блок 8 формирования топологии, состоящий из группы 9 элементов И, элемен та ИЛИ 10, элемента И 11, адемента НЕ 12 и элемента И 13; генера% 10515тор 14 импульсов, эадатчики 2 адресовначальных узлов всех моделей выполненыв виде регистра 15 апреса начальногоузла.и схемы 16 сравнения кода начального уэпа, каждый задатчик 3 адресаконечного узла выполнен в виде регистра 17 адреса конечного узла и схемы 18сравнения кода адресов конечных узлов,Кроме того, в устройство входит узел 19выделения единицы старшего разряда кода адреса ветви графа.Дпя пояснения работы прецлагаемогоустройства на фиг. 2 изображен примервыполнения устройства цля моделированиякратчайших путей на графе с максимальъным чиспом узлов и ветвей - цо четыре,Это устройство имеет четыре моцеливетви 1, разрядности регистра 15 апреса начапьного узла, регистра 17 аареса конечного узла, при этом схемы 16и 18 сравнения кодов - четырехвхоцовыеи группа 7 элементов И состоит из двухэлементов И. Узел 19 выцепенияединицы старшего разряда кода ад,реса ветви графа для лучшей иллюслрации принципа цействия представлен ввице групп (й) элементов ИЛИ 20элементов НЕ 21, элементов И 22, гдеи - число моцепей ветвей. При этом элемент ИЛИ, 10 (фиг. 1) исключен, таккак его заменяет группа поспецовательновкпюченных элементов ИЛИ 20,Работа устройства рассматриваетсяпля схемы на фиг. 2 на примере графа,приведенного на фиг. 3.Первоначально в устройство заносится35топология исследуемого графа путемустановки регистров 15 и 17 задатчиковадресов в соответствующее состояние,Например, в регистр 15 задатчика 2 ад 40реса начапьного уэпа модели первой ветви заносится коц "1", в запатчик 3 адреса конеччого узле в регистр 17 заносится коц "2". Б формирователи 4 временныхинтервапов кажпой модели ветви зано 45сятся коды, пропорционапьные весам ветвей исследуемого графа (на фиг, 3обозначены в знаменатепи, поц ноМером ветви). Триггеры 6 всех моцелейустаналиваются в состояние, соответствующее уровню погической единицы наих выходах. При этом на выхопе формирователя 4 и, следовательно, на выходеэлементов И 5 всех моделей ветвейуровень логического нупя. 55Для запуска устройства на обьеаиненные вхоцы зацатчиков 2 и 3 адресов всех моделей ветвей, т.е. на адресную шину устройства, подается код начального узла исследуемого графа - коп 1 . При этом срабатывают схемы 16 сравнения кодов апресов начальных узпов модепей первой и второй ветвей. формирователи 4 временных интервалов этих моцепей, подучив импульсы от схем 16 сравнения копов, поцготавпиваются к работе, Так как сигкапа готовности с выхоцов элементов И 5 моделей ветеей еше не поступало и на выходе последнего элемента ИЛИ группы 20 уровень логического нуля, а спеаоватепьно, на выходе элемента НЕ 12 - уровень погической ециницы, то сигналы измеритепьной серии с первого выхода генератора 14 импульсов (зпюра О, фиг, 4) поступают через эпемент И 13 (зпю- раЬ, фиг. 4) на информационные вхоцы формироватепей 4. Пои поступлениикажцого импульса измерительной сериина вход формирователя 4 его соцержимое уменьшается на единицу. При поступлении третьего импульса срабатывают формирователи 4 моцепей первой и второй ветви, на их выходах, а слеповатепьно, на выходах эпементов И 5 моделей первой и второй ветви появляется сигнал уров.ня логической единицы (соответственно зпюры 7 и , фиг. 4). Эти си;Гнапы, проходя на выхоц послецнего зпемента ИЛИ группы 20 и палее на выход злемечта НЕ 12, запрешают аапькейшеепрохождение импульсов измерительной серии ка первые вхоаы формирователейвременных интервалов, С выхода поспеднего элемента ИЛИ группы 20 сигнал готовности поступает на первый входэлемента И 11, разрешая прохождение импупьсов опроса моцепей ветвей с второго выхоца генератора 14 импупьсов(эпюра Ь, фиг. 4) на выход элемента И 11 блока формирования топологии(эпюраЖ, фиг. 4). С выхода этого эп мента сигкап опроса поступает на вторые вхоцы группы 9 элементов И. С пругой стороны сигнал готовности моцели первой ветви уровня логической еди- ницы с первого вхоца узле 19 вьшеления единицы старшего разряда кода ветви поступает на ее первый выход, так какна всех выходах элементов ИЛИ группы 20 присутствует уровень погической единицы, а на выходах элементов НЕ группы 21 - уровень логического нуля, ко.торый препятствует прохождению сигнапов готовности от остальных моделей на выхопы узда 19, Импульс опроса через первый эпемект И группы 9 посту 7 10818 пает на вторые входы группы 7 элементов И моцели первой ветви (эпю ра , фиг. 4), при этом на адресной шане появляется коц 3" конечного адреса первой модели ветви.5Этот коц фиксируется схемой 18 сравнения копов этой же модели первой ветви, при этом устанавливается в нуль триггер 6 и снимается сигнал готовности моцели первой ветви на 10 выходе элемента И 5. Одновременно с этим срабатывает схема 18 сравнения ,кодов адреса конечного узла модели тре-, тьей ветви, блокируя через триггер 6 модели появление сигнала готовности 15 ветви, лежашей не на кратчайшем пути. Оцновременно срабатывает схема 16 сравнения коцов адреса начального узла модели четвертой ветви, подготавливая к работе формирователь 4 временных: 20 интервалов модели этой ветви.Однако наличие сигналов готовности на выходе модели второй ветви (эпюра, фиг, 4) препятствует началу измерительной серии импульсов и проца жается опрос слецующей моцели (эпюрай, фиг. 4), На втором выходе узла 19 присутствует уровень логической ециницы, так как на выходах всех элементов НЕгруппы 21, кроме первого,- уровень логической единицы. Поэтому сигнал опроса пройдет через второй элемент И группы 9 и поступит на вход опроса модели второй ветви (эпюра и, фиг. 4). При этом на адресной шине появится коц 2 " - адрес конечного узла второй ветви.Схема 18 сравнения кодов конечного узла зацатчика 3 модели этой ветви срабатывает и снимает сигнал готовности. 40 Оцновременно с этим срабатывает задатчик 2 ацреса начального узла модели третьей ветви, подготовив к работе формирователь 4 модели этой ветви. 43 8Однако появление сигнале готовностимоцели было заблокировано при опросе модели первой ветви,После опроса всех моделей, с котьрых пришли сигналы готовности, навыхоцах формирователей 4 вновь появляется серия измерительных импульсов(эпюра 5, фиг. 4).После второго импульса сработает, формирователь моделитретьей ветви, однако сигнал готовностис ее выхоца не поступает, так как этаветвь лежит не на кратчайшем пути, Припоступлении третьего импульса сработаетФормирова гель модели четвертой ветви(эпюра М, фиг. 4), через последний элемент ИЛИ группы 20 (эпюраЖ, фиг. 4)этот сигнал поступает на первый входэлемента И 11 и через четвертый элемент И группы 9 по импульсу опроса свторого выхода генератора 14 (эпиюрао,фиг. 4) происхоцит опрос четвертой. модели ветви (эпюра Л, фиг. 4). При опро 1се модели этой ветви на адресной шинеустройства появляется коц "4 - адресконечного узла модели ветви, которыйявляется адресом конечного узла исслецуемого графа, В этот момент работаустройства прекращается, При этом сумма импульсов измерительной серии, поступивших на вход формирователей временных интервалов (эпюра 6, фиг. 4)пропорциональна кратчайшему расстояниюмежду заданными узлами исследуемогографа.Таким образом, в рассмотренном устройстве реализуется волновой процессраспространения сигналов цля моделирования кратчайшего пути в графе, Приэтом передача управления от модели одной ветви к.другой осуществляется заодин такт работы генератора импульсов.Это позволяет цостигнуть высокогобыстродействия устройства по сравнениюс известным, 1061843Заказ 8667/48 Тираж 706 Поцписн ВНИИПИ Госуцарственного комитета СССР по цепам изобретений и открытий 113035, Москва, Ж, Раушская наб., ц. 4/