Модель ветви графа Советский патент 1979 года по МПК G06F15/173 

1

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

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

Недостатком этой модели является невозможность моделирования минийаксных и максиминных путей на графе.

Наиболее близкой по технической су;щности к данному изобретению является модель.ветви графа, содержащая генератор импульсов, формирователь временного интервала, выход которого пЬдШйче к информационному входу первого элемента И, выход которого соединение единичным входом первого триггера, единичный выход которого подключен к перво2.

му входу второго элемента И, выход которого соединён с соотвётствующим вхЬ дом первого элемента ИЛИ, выход которого подключен ко входу первого инвертора и к первому входу третьего элемента И, выход которого подключен к первому входу второго элемента ИЛИ, выход которого соединен с первыми входами бяо-«ов задания начального и конечного адресов, выход блока заданий конечного адреса соединен с его входом и с первым входом четвертого элемента И, выход которого подключен к единичному входу второго триггера, нулевой выход которого соединен со вторым входом

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

мента ИЛИ, выход которого подключен к Первому В.оду четвертого элемента ИЛИ, выход которого соединен с блоком управпення и со вторым входом четвертого эЯемента И,, первый выход блока уп- равнения подключен ко второму входу четвертого элемента ИЛИ, второй выход блокауправления соединен со вторым входом втчэрого элемента ИЛИ, первый выход генератора импульсов подключен ко второму входу третьего элемента И, второй выход генератора импульсов соединен с первым входом седьмого элемента И, второй вход которого подключен .к выхбду первого инвертора, выход сед±мого элемента И соединен с первым входом формирователя временного интервала, выход блока задания начального адреса подключен к третьему входу пятого элемента И, второй вход которого соединен со вторым входом четвертого элемента И 2|.

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

. Это достигается тем, что в предлагаемое устройство введены восьмой элемент И, второй инвертор и счетчик .вход которого подключен к выходу пятого элемента Ник вхоод второго инвертора, выход счетчика соединен со вторым входом формирователя временного интервала, выход второго инвертора

подключен ко второму входу ВОСЬМОТО

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

На -чертеже показана -предлагаемая модель.

Она состоит из элементов И 1-6, инвертора 7, счетчика 8, блока задания начального адреса 9, блока задания конечного адреса 10, триггеров 11, 12 формирователя временного интервала 13

На чертеже также обозначены модель Ветви 14, блок автоматического формирования топологии 15, блок управления 16, генератор импульсов 17, элементы ИЛИ 18-21, элементы И 22, 23, инвертор 24, входы модели ветви 25-27, выходы модели ветви 28, 29, группы входов блока автоматического формирования топологии 30,31, входы блока автоматического формирования топологии 32-35, выходы блока автоматического формирования тополот-ии 36-38, выходы генератора импупьсов 39, 4О, вход блока управления 41, выходы блока управления 42,43.

.Работа модели ветви рассматривается на примере реализации следующей вхо ной функции ветви

X MavtKcvdl,(1)

где входная функция рассматриваемо

1 -и ветви, выходящей из J -го узла графам

Q, t3 , С , d - в ыходные функции ветвей, входящих в -ый узел графа. FfycTb изображенная на чертеже модель, ветви 14 является моделыо i -и ветви графа, а для записи -го узла в блоках задания начального и конечных адресов отведены два разряда: т-ый и (№+ 1)-ый. Тогда до начала работы в блоки задания конечных адресов .моделе а-и иЬ-й ветвей заносится по одной единице в hi-и разряд, в блоки задания конечных адресов моделей С -и ч d -и ветвей заносится по одной единице в (П1+ 1)т-ый разряд, а в блок задания начального адреса модели 1-й ветви заносится две единицы - в ж-ый и (1п+1)-ый разряд. В блок задания конечного адреса модели i-ой ветви заносится единица в рарряд, соответствующий номеру узла, в который ьходит i-я ветвь. В счетчик 8 заносится чиспо N-2, .где К-емкость счетчика. В формирователи .временных интервалов всех ветвей заносятсдлины ветвей, а триггеры 11,12 устанавливаются в нулевое состояние,

П/сть, далее, длины ветвей таковы, что среди рассматриваемых ветвей первой оканчивается Q-я ветвь, второй 1з-я, третьей - с-я и четвертой - d -я.

Работа устройства paccмвтpивaeтcя начиная с момента окончания О-и ветви.

Сигнал с выхода 28 модели о)-и ветви (на чертеже не показана) поступае в блок- автоматического формирования топологии .15 на один из входов ЗО элемента ИЛИ 18, к остальным входам ко.торого присоединены одчюименные выходы других моделей ветвей, как не изображенных на чертеже, так и 1-ой. .Пройдя через элемент ИЛИ 18, сигнал поступае на вход инвертора 24, который вырабатывает запрет на одном из входов элемента И 22. Второй вход элемента И 22 соединен со входом 32 бпокэ автоматического формирования топологии и далее 56 с выходом 39 генератора импульсов 17 поэтому серия импульсов ГИ1 бопьиде не поступает на входы 25 Bfcex моделей ветвей. Oднoвpe feннo с выхода эле мен- та ИЛИ 18 на один из входов элемента/ И 23 поступает разрешение, и через элемент И 23, второй вход которого сое динен совходом 33 и далее - с выходом 40 генератора импульсов 17, серия им пупьсов ГИ2 через элемент ИЛИ 20 поступает по выходу 37 на входы 26 всех моделей ветвей. Имульсы серии ГИ2 одновременно сдвигают содержимое всех блоков задания адресов. Сигнал с выхода блока задания начапьного адреса 9 поступает на первый вход элемента И 2. Сигнал с выхода бло ка задания конечного адреса модели ветви поступает на выход 29 соответствующей модели ветви, который соединен с одним из входов 31 элемента ИЛИ 19, к остальным входам которого присое динены одноименные выходы всех .моделей ветвей, и с выхода элемента ИЛИ 19, котчэ эый соединен со входом этгемента ИЛИ 21, указанный сигнал поступает на выход38, и далее - на вход 27 рассматриваемой ti -и модели ветви, соединённый со вторым входом элемента И 2, и на одноименные входы остальных вет Вей. Так как третий вход элемента И 2 соединен с нупевыКг выходом триггера 11, находящегося в нулевом состоянии, то сигнал с выхода блока задания начапьного адреса 9 пройдет через элемент И 2 f увеличит содержимое счетчика 8 на . Выходной сигнал инвер Тора 7 запретит прохождение этого единич ного сигнала через элемент И 6 в блок задания начального адреса 9. Сигнал с выхода блока задания конечного адреса модели |з-и ветви поступает на первый аход элемента И 3 соответствующей модепи ветви; поскольку на входах 27 всех моделей ветвей присутствуют разрешающир сигналы, то в моделях ветвей Q и t) (т.е. в тех моделях, где на выходе блока вадания конечного адреса присутствуют единичные сигналы), выходной сигнал элемента И 3 установит в единичное состояние триггер 11, выходной сигнал которого запретит прохождение единичного сигнала с выхода триггера 12 через элемент И 5 на выходе 28 (для модели d-и ветви), и запретит установк в единичное состояние триггера 12 6т элемента И 1 (для модели ветви). 6 Нулевой сигнал с выхода 2В через ВХОД 30 блока автоматического форм рования топологии поступает на вход элемента ИЛИ 18 и на первый вход элемента И 23, чем запрещает поьтуппение серии ГИ2 на входы 26 всех моделей ветвей. Одновременно единичный сигнал с выхода инвертора 24 разрешает поступление импульсов серии ГИ1 с выхода 39 генератора импульсов 17 через элемент И 22 па Входы 25 всех моделей ветвей. В тех моделях ветвей, где присутствуют разрешающие сигналы на входах формирователей временных интервалов, последние производят счет импульсов серчи ГИ1. Единичный сигнал на выходе формирователя временного интервала Ь-й ветви не установит триггер 12 этой ветви в единичное состояние, так как на втором входе схемы И 1 Ь-й ветви присутствует запретлаюший сигнал с выхода триггера 11 той же ветви. Поэтому импульсы серии ГИ1 по-прежнему постудают с выхода 36 на входы 25 всех моделей ветвей. Триггер 11 с-й ветви находится Б нулевом состоянии, поэтому выходной сигнал формирователя временного интервала этой ветви через элемент И 1 установит триггер 12 в единичное состояние; этот единичный сигнал пройдет на выход 28 и далее - на рдин из входов 30 блока автоматического формирования топологии. Последний прекратит подачу импульсов серии ГИ1 на входы 25 всех моделей и начнет подачу импульсов серии ГИ2 на входы 26. Сигнал с выхода блока задания конечного адреса с-й ветви через элемент И 4 пройдет на выходы 29 этой же ветви, а оттуда - на один из входов 31 элемента ИЛИ 19 и через элемент ИЛИ 21 на вход 27 всех моделей ветвей. Со входа 27 с-й ветви этот сигнал через, лемент И 3 устанавливает в единицу триггер 11. Следовательно, на второй вход элемента И 2 модели 14 i -и ветви поступает разрешающий сигнал; на третьем входе этого же элемента также присутствует разрешение с нулевого выхода триггера 11. Таким образом, сигнал с Bbixffaa блоКа задания начального адреса 9 через элемент И 2 пройдет на вход . счетчика 8; сигнал переполнения с выхода последнего поступает на вход формирователя -временного интерва6па 13, и поспений начинает отсчет им-. пульсов серчи ГИ1, поступающих на первый вход формироватепя 13. Перезапись единицы в бпок задания начального адреср запрещается инвертором 7, После отсчета числа импульсов . серии ГИ1, пропорционального дпине 1-й ветви, сигнап с выхода формирователя 13 устанавливает в единицу триггер 12; единичный сигнап через элемент И 5 поступает на выход 28 i -и модели ветви Суммарное число импульсов серии ГИ1, отсчитанное измерительным счетчиком, входящим в состав блока управпе ййй, от момента начапа ветви до момента начапа i -и ветви, пропорциойально произведению длин ветвей а и с, что соответствует реализации функции (1 1Г|Ж у1аЭ1ЙШь1Х йыше соотношениях между длинами ветвей. Рассматриваемая модель благодаря йведению дополнительных блоков позволяет расширить функЦйЬнйлЬнь © возможности модели за счет отыскания минимаксных и максиминных путей в графах Формула изобретения Модель ветви графа, содержащая гене ратор импупьсов, формирователь временйОго интервала, выход которого подключен к инфорШцйонНОму взсбду inlpBoro элемента И, выход которого соединен с единичным взсодом первогчэ триггера, единичный выход которого подключен к MpSQW входу второго элемента И, выхо которого соединен с соответствующим входом первого элемента ИЛИ, выход ко торого подключен ко входу первого инвертора и к первому входу третьего элемента И, выхОд которого подключен к первому входу второго элемента ИЛИ, выход которого соединен с первыми входами блО1сов задания начального и конечного адресов, выход блока задания конеч ного адреса соединен с его входом и с первым ВХОДО.М четвертого элемента И, которого подключен к единичному Входу второго триггера, нулевой выход Kotoporo соединен со вторым входом вто рого элемента И, со вторым входом перв 68 го эпемента И и с ггервым входом пятого элемента И, июстой элемент И, первый вход которого соединен с единичMbiM выходом первого триггера, второй вход шестого эпемента И подключен к выходу блока задания конечного адреса, выход ufecToro эпемечта И соединен с соответствующим входом третьего элемента ИЛИ, выход которого подключен к первому входу четвертого элемента ИЛИ, выход которого сюединен с блоком управления и со вторым входом четвертого элемента И, первый выход блока управления подключен ко второму вхо1зу четвертого элемента ИЛИ, второй выход блока управлбни я соединен со вторым входом второго элемента ИЛИ, первый выход генератора импульсов подключен ко второму входу третьего элемента И, второй выход генератора импульсов соединен с первым входом седьмого элемента И, вход которого подключен к выходу первого инвертора, выход седьмого элемента И соединен с первым входом формирователя временного интервала, выход блока задания начального адреса подключен к третьему входу пятого эле-, мента И,.второй вход которого соединен со вторЫ / входом четвертого элемента И, о г л и ч а ю щ а я ся тем, чго, с целью расширения функциональных возможностей 3. счет определения минимаксных Или максиминных путей в графеj в устройство введены восьмой элемент И, второй инвертор и счетчик, вход которого подключен к выходу пятого элемента И и к вхойу второго инвертора, выход счетчика соединен со вторым входом формирователя временного интервала, выход второго инвертора подключен ко второму входу восьмого элемента И, выход которого соединен со вторым входом блока задания начального адреса, первый вход восьмого элемента И подключен Ктретьему входу пятого элемента И. Источники информации, принятые во внимание при экспертизе 1,Авторское свидетельство СССР № 422002, кл. Q 06 Q 7/48, 1974. 2.Авторское свидетельство СССР № 470811, кл. G Об F 15/20, 1975.