Устройство для моделирования кратчайших путей на графах Советский патент 1983 года по МПК G06F15/173 

10 элемента ИЛИ блока формирования топологии, выходы узла выаеления еаиницы старшего разряца копа адреса ветви ( графа соединены с первыми входами элемент он И группы блока формирования топологии, вторые вкойы 43 которых подключены к выкопу первого элемента И блока формирования топологии, а выкоды соединены с вторыми вводами элементов И групп соответствующих моделей ветвей грАфа.

УСТРОЙСТВО ДЛЯ МОДЕЛИ РСеАНИЯ КРАТЧАЙШИХ ПУТЕЙ НА ГРАФАХ, соцержащее блок из Л моаепей ветвей по числу ветвей моделируемого графа, каждая из которых состоит из зацатчиков ацресов начального и кйнеч ного узлов, формирователя временных интервалов, элемента И и триггера, блок формирования топологии, содержащий первый и второй элементы И, элемент ИЛИ и элемент НЕ, генератор импульсов, первый и второй выходы которого под- ключены к первому входу первого элемён« та И блока формирования топологии и первому входу второго элемента И блока формирования топологии, выход эле- мента ИЛИ блока формирования тополо гни подключен к второму входу первого элемента И блока формирования тополо гии и через элемент НЕ - к второму входу второго элемента И блокд фор«1И рования топологии, выход второго эле-ь мента И блока формирования топологии соединен с информационными входами формирователей временных интервалов каждой модели ветви, выходы моделей ветвей подключены к соответствующим входам элемента ИЛИ бложа формирова ния топологии, отличающееся тем.гчто, с целью повышения.быстродействия устрюйства, в блок формирования топологии дополнительно введены группа из элементов И (где П - число моделей ветвей) и узел выделения единиць старшего разряда кода адреса ветви графа, а в ветвей - группы из in элементов И (где W - число разрядов адреса узла графа), причем каждый задатчик адреса начального и конечного узлов каждой модели ветвн содержит регистр адреса и схему сравнения, первые входы схек сравнения, j .с являющиеся входами задатчиков адресов узлов, объединены и подключены к выходам элементов И групп каждой модели ветви, вторые входы схем сравнения задатчиков адресов начальных узлов соединены с выходами регистров адреса начальных узлов, а выходы - с управляк шими входами фор лирювателей временных интервалов, BTOfH ie входы схем сравнения-задатчиков адресов конечных узлов под ключены к выходам регистров адресов ко, вечных узлов и первым входам элемен:л тов И групп соответствующей модели м ветви выходы схем сравнения задатчиков адресов кс«ечных узлов кажд модели ветви соединены с входами тртггеров, ВЫХОДЫ которых подключены к первым входам элементов И соответствующей ветви, вторые входы которых соединены с выходами формирователей временных интервалов, а выходы - с соответствующим входом узла выделения единицы старшего разряда кода адреса ветви графа блока формирования топологии, объединенным с однсжменным вхором

Изобретение огаосится к вычислительной технике, в частности к устройствам для моделирования кратчайших путей на графах.

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

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

Наиболее близким по технической сущности к предлагаемому яштяется устройство для моделирования сетевых графиков, содержащее блок управления.

первый выход которого подключен к первому входу первого элемента ИЛИ блка формирования топологии, блок моделей ветвей по числу работ сетевого графика, каждая из которых выполнена в виде задатчиков адресов, выходами соединенных с элементами И, причем выход первого элемента И соединен с входом формирователя временных интервалов, вход второго элемента И соединен через инвертор с первым входом элемента ИЛИ, к второму входу которого подключен вых второго элемента И, генератор импульсов, первый и второй выходы кото1эого подключены соответственно к второму входу первого элемента И каждой модели ветви и к первому входу первого элемента И блока формирования топологии, второй вход которого соединен с входом инвертора блока формирования тополе- гии, каждая модель ветви содержит триггеры, входы которых соединены с фор- . мирователем временных, интервалов, причем второй вход первого триггера подключен к первому входу второго элемента И, к второму входу которого и .к третьему входу первого элемента И подключены выходы второго триггера, входы задатчиков адресов каждой модели ветви соединены с выходом первого элемента ИЛИ блока формирования топологии, содержащего второй элемент ИЛИ, I .

подключенный через инвертор к второму элементу И и последовательно соединенные третий элемент И и третий элемент ИЛИ, выход и вход которого подключены соответственно к входу и второму выходу блока управления, причем первый выход генератора импульсов соединен с входом второго элемента И блока формирования топологии, выход которого подключен к входу формирователя временных интервалов каждой модели ЕЮТВИ, вход блока управления соединен с четвертым вхоцом первого элемента И каждой моцели ветви, выход первого триггера кажаой модели ветви поаклю ен к вхоцу второго элемента ИЛИ блока формирования топологии, а выход второ- j го элемента ИЛИ каждой модели ветви соединен с входом третьего элемента И блока формирования топологии 2 .

Недостатком устройства Я;,ляется низкое быстродействие за счет больших aaiv ю рвт времени на моделирование адресе при формировании топологии исследуемого графа.

41ель изобретения - увеличение быстродействия устройства при моделировании )5 кратчайших путей на .графах.

Указанная цель достигается тем, что в устройство, для моделирования кратчайших путе на графах, содержащее. блок из м. моделей ветвей по числу ветвей-моделируемого графа, каждая из которых состоит из задатчиков адресов начального и ксннечного узлов, фо ядирователя временных интервалов, элемента И .5 и триггера, блок формирования топология,

содержащий первый и второй элементы И, элемент ИЛИ и элемент НЕ, генератор импульсов, первый и второй выходы которого подключены соответственно к первому входу первого элемента И блока формирования топологии и первому входу второго элемента И блока формирования топологии, выход элемента ИЛИ блока формирования топологии подключен к второму входу первого элемента И бло- 5 ка формирования топологии и через элемент НЕ - к второму входу второго

элемента И блока формирования топологии,, выход второго элемента И блока формирования топологии соединен с информацией ными входами формирователей временных интервалов каждой модели ветви, выхоаы моделей ветвей подключены к соответ ствуюшим входам элемента ИЛИ блока формирования топологии, в блок формиро вания топологии дополнительно.введены группа из .Ц элементов И (где П - число

моделей ветвей) и узел выцеленяя еав НИНЫ старшего разряда кода адреса вет« ви графа, в fcMieли ветвей - группы изITJ элементов И (где ГЛ- число разрядов адресе узла графа), причем каждый задатчик адреса начального и конечного узлов каждой модели ветви содержит {егвстр адреса и схему сравнения, первые55 входы схем сравнения, являющиеся вхо пам:и задатчиков адресов узлов, обье аинены и подключены к выходамэпемея-г

тов И групп каждой модели ветви, вторые входы схем сравнения задатчиков адресов на.чальных узлов соединены с выуходами регистров адреса начал ых узлов, i а выходы - с управляющими входами фор мирователей временных интерваж в, вторые входы схем сравнения задатчиков адресов конечных узлов подключены к выходам регистров адресов ксиечных уэлов и первым входам элементов И групп соответствующей модели ветви, выходы схем сравнения задатчиков адресов конечных узлов каждой модели ветви соединены с входами триггеров, выходы которых подключены к первым входам элементов И соответствующей модели ветви, вторые входы которых соединены с выходами формирователей временных интервалов, а выходы - с соответствующим входом узла выделения едннипы старшего разряда кода адреса ветви графа блока формирования топологии, объединенным с одноименным входом элемента ИЛИ блока формирования топологии, выходы узла выделения единицы старшего разряда кода адреса ветвя графа соединены с первыми входами элементов И группы блока формирования топологии, вторые входы которой подключены к выходу первого элемента И блока формирования топологии, а выходы соединены с вторыми входами элементов И групп соответствующих моделей ветвей графа.

На фиг. 1 дана функиисжальная схема устройства для моделирования кратчайших путей на графах; на фиг. 2 - пример исполнения устройства для моделирования кратчайших путей на графе, имеющем четыре ветви и четыре узла; на фиг. 3 - пример исследуемого графа; на фиг. 4 - временная анаграмма работы устройства при моделировании кратчайшего пути в графе, приведенном на фиг, 3.

Устройство . 1) содержит блок из И Моделей ветвей 1 по числу ветвей моделируемого графа, каждая из которых выполнена в виде задатчиков 2 адресов начальных узлов и задатчиков 3 адресов ксжечнс,. узлов, формирователя 4 временных интервалов, элемента И 5, тржп 6 и группы 7 элементов И по числ разрядов кодов адресов узлов графа; блок 8 формирования топологии, состоящий из группы 9 элементов И, элемента ИЛИ 1О,-зд емента И 11, элемента НЕ 12 и элемента И 13; генератор 14 импульсов, эацатчкки 2 вцресов начальных узлов всех моделей выполнены в виде регистра 15 адреса начального узла, и схемы 16 сравнения кода начального узла, каждый запатчик 3 адреса конечного узла выполнен в виде jferHC, pa 17 адреса конечного узла и схемы 18 сравнения кода адресов конечных узлов. Кроме того, в устройство входит узел 19 выделения единицы старшего разртда кода адресаветви графа. Для пояснения работы предлагаемого устройства на фиг. 2 изображен пример выполнения устройства цля моделировани кратчайших путей на графе- с максималь- ным числом узлов и ветвей - по четыре. Это устройство имеет четыре модели ветви 1, разрядности регистра 15 адреса начального узла, регистра 17 конечного узла, при этом схемы 16 и 18 сравнения кодов - четырехвхоцовые и группа 7 элементов И состоит из двух элементов И. Узел 19 выделения единицы старшего разряда кода ад™ ,реса ветви графа для лучшей иллюст- р«ации принципа действия представлен в виде групп (м-1) элементов ИЛИ 20 элементов НЕ 21, элементов И 22, где П - число моделей ветвей. При этом эле мент ИЛИ 1О (фиг. 1) исключен, так как его заменяет группа послецовательн включенных элементов ИЛИ 2О. Работа устройства рассматривается для схемы на фиг. 2 на примере графа, приведенного на фиг. 3. Первоначально в устройство заносится топология исследуемого графа путем установки pei-истров 15 и 17 за датчиков адресов в соответствуюиюе состояние. Например, в регистр 15 зацатчика 2 адреса начального узла модели первой вет,зй заносится код 1, в задатчик 3 адре са конечного узла в регистр 17 заносит ся коа 2. В формирователи 4 временнь интервалов каждой модели ветви заносятся коды, пропорциональные весам вет вей исследуемого графа {на фиг. 3 обозначены в знаменатели, под номером ветви). Триггеры 6 всех моделей устаналиваются в состояние, соответствующее уровню логической единицы на их выходах. При этом на выходе форм и- рователя 4 и, следовательно, на вьхходе элементов И 5 всех моделей ветвей уровень логического нуля. Лля запуска устройства на объединенные входы за датчиков 2 и 3 адресов всех моделей ветвей, т.е. на адресную шину устройства, подается коц начального узла исслепуемого графа . коп 1. При этом срабатывают схемы 16 сравнения кодов адресов начальных узлов моделей первой и второй ветвей. Формирователи 4 временных интервалов этих моделей, получив импульсы от схем 16 сравнения кодов, подготавливаются к рвботе. Так как сигнала готовности с выходов элементов И 5 моделей ветвей еще не постлшало и на выходе последнего элемента ИЛИ группы 20 урозень логического нуля, а слеаова1тельно, на выходе элемента НЕ 12 - уровень логической единицы, то сигналы измерительной серии с первого выхода :генератора 14 импульсов (эпюра а , фиг. 4) поступают через элемент И 13 (эпюра Ь , фиг. 4) на информационные входы формирователей 4. При псхзтуплении каждого импульса измерительной серии на вход формирователя 4 его соцержимое уменьщается на единицу. При поступлении третьего импульса срабатывают формирователи 4 моделей первой и второй вет- ви, на их выходах, а следовательно, на выходах элементов И 5 моаелей первой и второй ветви появляется сигнал уров- -ня JIOгичecкoй единицы (соответственно эпюры 1 и, фиг. 4). Эти сигналы, проходя на выход г оследнего элемента ИЛИ группы 20 и далее на выход элемента НЕ 12, запрешаюг дальнейшее прохождение импульсов измерительной серии ка первые входы формирювг;гелей временных интервалов. С. последнего элемента ИЛИ группы 20 сигнал готовности поступает на первый вход элемента И 11, разрешая прохождение импульсов опроса моделей ветвей с .второго выхода генератора 14 импульсов (эпюра.В , фиг. 4) на выход, элемента И 11 блока формирования топологии (эпюраЖ, фиг. 4). С выхода этого элемента сигнал опроса поступает на вторые входы группы 9 элементов И. С другой стороны сигнал готовности модели первой ветви уровня логической еди ницы с первого входа узла 19 выделения единицы старшего разряда кода шгтви поступает на ее первый выхоа, так как на всех выходах элементов ИЛИ группы 20 присутствует уровень логической единицы, а на выходах элементов НЕ группы 21 - уровень логического нуля, который препятствует прохождению сигналов готовности от остальных моделей на узла 19. Импульс опроса первый элемент И группы 9 постуает на вторые вхоаы группы 7 эле- , ентов И модели первой ветви ( , фиг. 4), при этом на ааресной появляется код 3 конечного адреса первой модели ветви.5

Этот код фиксируется схемой 18 равнения кодов этой же модели первой ветви, при этом устанавливается в уль триггер 6 и снимается сигнал готовности модели первой ветви на10

выходе элемента И 5. Одновременно с этим срабатывает схема 18 сравнения

кодов адреса конечного узла модели тре-. тьей ветви, блокируя через триггер 6 модели появление сигнала готовностиts

ветви, лежащей не на кратчайшем пути. Одновременно срабатывает схема 16 сравнения кодов адреса начального узла модели четвертой ветви, подготавливая к работе формирователь 4 временных : 20 интервалов модели этой ветви.

Однако наличие сигналов готовности на выходе модели вторсЛ ветви (эпюра g , фиг. 4) препятствует началу измерительной серии импульсов и продол- 25 жается опрос следующей модели , фиг. 4). На втором выходе узла 19 присутствует уровень логический единицы, так как на выходах всех элементов НЕгруппы 21, кроме первого,- . JQ уровень логической единицы. Поэтомусигнал опроса пройдет через второй элемент И группы 9 и поступит на вход опроса модели второй вегви (эпюра и, фиг. 4). При этом на адресной шине появится код 2 - адрес конечного узла второй ветви.

Схема 18 сравнения кодов конечного узла задатчика 3 модели этой ветви срабатывает и снимает сигнал готовности. . Одновременно с этим срабатывает задатчик 2 адреса начального узла модели третьей ветви, подготовив к работе формирователь 4 модели этой ветви.

Однако появление сигнала готовности модели было заблокировано при опрогсе модели первой ветви.

После опроса всех моделей, с которых пришли сигналы готовности, на выходах формирователей 4 внов появляется серия измерительных импульсов (эпюра Ь, фиг. 4).После второго импульса сработает,формирователь модели третьей ветви, однако сигнал готовности с ее выхода не поступает, так как эта ветвь лежит не на кратчайшем пути. При поступлении третьего импульса сработает формирователь модели четвертой вёгви (эпюра k , фиг. 4), через последний элемент ИЛИ группы 20 (эпюра, фиг. 4) этот сигнал поступает на первый вход элемента И 11 и через четвертый элемент И группы 9 по импульсу опроса с второго выхода генератора 14 (эпиюра5 фиг. 4) происходит опрос четвертой, модели ветви (эпюра л , фиг. 4). При опросе модели этой ветви на адресной шине устройства появляется код 4 - адрес конечного узла модели ветви, который является адресом коночного узла исследуемого графа. В этот момент работа устройства прекращается. При этом сумма импульсов измерительной серии, поступивших на вход формирователей временных интервалов (эпюра 6 , фиг. 4) пропорциональна кратчайшему расстоянию между заданными узлами исследуемого графа.

Таким образом, в рассмотренном уст ройстве реализуется волновой процесс распространения сигналов для моделирования кратчайшего пути в графе. При этом передача управления от модели одной ветви к.другой осушествляется за Ьдин такт работы генератора импульсов. Это позволяет достигнуть высокого быстродействия устройства по сравнению с известным.

IТ-il

I rrzn fTzn-КтСШ

МД LriiT4 tr

r44Ch iirzrHrzrmJtrLH-H

r-til j

IS.I

9иг.

е

9

s

т

.

гп

3

и

. «

ftl