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

1,. . ,.„,.,..,,... ....ч,;.... ..:.:... Изобретение относится к области вычислительной техники и может быть использовано при построении цифровых специализированных машин для реше-. ния задач на моделях графов, содержа щих циклы. Известна Модель ветви сетево1 о графика, выполненная на логических элементах, с помощью которой можно решить задачу о минимальном потоке й сети {. Недостатком известного уст ройства является недостаточное быстродействие. Наиболее близким по технической сущности к рассматриваемому является модель ветви графа, выполненная на элементах. И, счетчиках, триггерах и инверторе 2. К основному недостатку этой модели следует отнести невозможность моделирования графов, содержащих циклы Целью изобретения является расширение класса решаемых згщач, за счет моделирования циклических участков. Это достигается тем, что в модель, содержащую счетчик импульсов, выход которого соединен с единичным входом первого триггера, нулевой вход которого подключен к выходу первого элемента И, первый вход которого соединей со входом сброса модели, выходной полюс которой через элемент НЕ соединен со вторым вйодом первого элемента И и одним из входов блока индикации, соответствующие входы которого подключены к входному полюсу модели, единичным выходам первого и второго триггеров и к кулевому выходу третьего триггера, входной полюс модели соединен с первым входом второго элементаИ, второй вход которого соединен со входом разрешающего потенциала модели, а третий вход подключен к нулевому выходу третьего триггера, единичный вход которого подключен к единичному выходу первого триггера, нулевой вход второго триггера подключен к выходу третьего элемента И, первый вход которого подключен ко входу синхронизации модели, второй вход - к единичному выходу третьего триггера, а третий к выходу счетчика регенерации, вход которого объединен со входом счетчика импульсов и подключен к выходу четвертого элемента И, один вход которого подключен ко входу тактовых импульсов модели, второй вход - к единичному выходу второго триггера,, дополнительно введены счетчик циклов. 7 ПЯТЫЙ элемент И и элемент ИЛИ, выход которого соединен с единичным входом второго триггера, а входы подключены соответственно к выходу второго эле мента И и циклического входу модели, который соединен с нулевым входом третьего триггера, единичный выход которого соединен с Циклическим выходом модели, первым входом пятого элемента И и входом счетчика циклов, выход которого соединен со вторым входом пятого элемента И, выход которого соединен с выходным полюсом модели. Функциональная схема модели представлена на чертеже.. Модель ветви графа содержит счетчин 1 импульсов, счетчик 2 регенерации, триггеры 3-5, элементы 6-9 И, элемент 10 НЕ, блок 11 индикации, входной полюс 12 модели, выходной по люс 13 модели, вход 14 разрешающего потенциала, вход 15 синхронизации, вход 16 сброса, вход 17 тактовых импульсов, циклический вход 18, элемент 19 ИЛИ, циклический выход 20, счетчик 21 циклов, элемент 22 И. Работает устройство следующим образом. . Модели, ве.твей соединяются между собой полюсами 12 и 13 в соответствии с топологией сетевого графика. В счетчики 1 при записи исходной инфор мации заносятся количества импульсов дополняющие продолжительность работ до полной емкости счетчиков. Счётчики-2 и триггеры 3, 4, 5 первоначально находятся в нулевом состоянии. Си нал, поданный на циклический вход 18 устанавливает триггер 3 в единичное состояние .и производит повторный запуск модели ветви, одновременно сигнал запуска по циклическому входу . сбрасывает триггер 5в нулевое состо яние, при этом появляется нулевой по .тенциал на выходном полюсе 13. Сигна выхода инвертируется элементом 10 НЕ поступает на элемент 8 И и после подачи импульса с генератора (на черте же не показан) на вход 1б сброса модели происходит сброс триггера 4 в н левое состояние. Таким образом, пода вая сигнал на циклический вход модели, можно каждый раз вызывать функционирование одной модели, не изменяя состояния других моделей ветвей, из.которых построена модель графа. Перед началом работы в счетчик циклов заносится число дополнением к которому служит заданное число цик лов, и каждый раз после появления сигнала на выходе триггера 5 и на вы ходе 20, содержимое счетчик 21 увеличивается на единицу и после отсчета заданного, числа циклов на выходе счетчика появится сигнал, который, попадая на вход элемента 22 И совмес но с выходным сигналом триггера 5 вы зывает появление сигнала на выходном 4 полюсе 13, что означает окончание функционирования модели. Таким образом модель ветви позволяет осуществить запуск заданное чис- ч ло раз циклических участков моделирут емого графа и отделить циклический участок модели графа от нециклического, изобретения Модель ветви графа, содержащая счетчик импульсов, выход которого соединен с единичным входом первого триггера, нулевой вход которого под- . ключен к выходу первого элемента И, Первый вход которого соединен со входом сброса модели, выходной полюс которой через элемент НЕ соединен со вторым входом первого элемента И и одним из входов блока индикации, соответствующие входы которого подключены к входному полюсу модели, единичным выходам первого и второго триггеров и к нулевому выходу третьего триггера, входной полюс модели соединен с первым входом второго элемента И, второй вход которого соединен со входом разрещающего потенциала модели, а третий вход подключен к нулевому выходу третьего триггера, еди.ничный вход которого подключен к едийичному выходу первого триггера, нулевой вход второго триггера подключен к выходу третьего элемента И, первый вход которого подключен ко входу синхронизации модели, второй вход - к единичному выходу третьего триггера, а третий - к выходу счетчика регенерации , вход которого объединен со входом счетчика импульсов и подключен к выходу четвертого элемента И, один вход которого подключен ко входу тактовых импульсов модели, второй вход - к единичному выходу второго триггера, отличающаяся тем , что, с целью расширения класса решаемых задач за счет моделирования циклических участков, она содержит счетчик циклов, пятый зЛёйент И и элемент ИЛИ, выход которого соединен с единичным входом второго триггера, а входы подключены соответственно к выходу второго элемента И и циклическому входу модели, .который соединен снулевым входом третьего триггера, единичный выход которого соединен с циклическим выходом модели, первым входом пятого элемента И и входом счетчика циклов, выход которого соединен со вторым входом пятого элемента И, выход которого соединен с выходным полюсом модели. Источ ники )ормаций, Принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 394793, кл, G Об F 15/20, 1971. 2.Васильев В. В. и Додонов А. Г. Гибридные модели зайач оптимизации. Киев, Hayкова Думка , 1974, с. 114, рис. 67 (прототип).,