УСТРОЙСТВО для РЕШЕНИЯ ЗАДАЧИ О МАКСИМАЛЬНОМ Советский патент 1970 года по МПК G06G7/122 

Изобретение относится к области вычислительной техники; оно может быть использовано для расширения возможностей комбинированных специализированных машин при решеяии задачи о максимальном нотоке в сетях.

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

В предложенном устройстве между начальным и конечным полюсами модели сети включены параллельно источник тока и дополнительная модель ветви, служащая индикатором насыщенности сети.

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

первый вход .схемы «И соединен с выходом нуль-ограна, второй - с выходом триггера, а третий - служит третьим полюсом модели ветви, выход схемы «И соединен со входом счетчика, выход которого соединен со входом

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

Эти отличия устройства нозволяют новысить его точность и разреитающую способность.

На фиг. 1 показана схема модели ветви (MB); на фпг, 2-схема индикатора иасыщенности ветви (PlMB); на фиг. 3 и 4 - два варианта схел предложенного устройства.

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

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

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

Исключают из рассмотрения пасыщенпыс ветви.

Повторяют операции пн. 1, 2, 3 до тех пор, пока окажется невозможным определить хотя бы один нуть пз начала в конец сети.

Онределяют вершины (узль) сети, которые можно достигнуть по ненасыщенным путям. Количество последних обозначим х, а количество узлов, в которые нельзя иоиасть ю ненасыщенным путям,- X.

Ветви, нмеющие свои начала в х, а конць; в X, образуют минимальное сечение (разрез) сети, которое определяет величину максимального потока. Последняя может быть найдена либо как сумма потоков, насыпающих различные пути в соответствии с и. 2, либо как сумма величин п)опускных способностей ветвей, образующих .минимальное сечение.

Схемы модели ветви MB (см. фиг. 1) и индикатора насыщенности ветви ИНВ (см. фиг. 2) содержат элемент 1, моделирующий ветвь для рещения задачи о кратчайшем пути с высокой разрешающей способностью, нанрпмер с экзивалейтОМ отрицательного -сопротивления, нуль-орган 2 (индикатор тока, протекающего по ветви), ключ 3, схему «И 4, счетчик 5 (цифровая линия задержки с регулируемым коэффициентом пересчета), триггер 6, схему «И 7, диод 8, инвертор (схема 9 и схему «И 10.

11, по топологии повторяющая моделируемую сеть 12, ветвями которой, обозначенными пунктиром, являются схемы ИНВ; источник напряжения 13, изображающий логическую единнцу; дополннтельная модель ветви 14 (индикатор насыщенности сети); источник тока 15; триггер 16, схема «И /7; измерительный счетчик 18; импульсная схема «Р1ЛИ 19; формирователь (линня задержкн) 20; схема «И 21,

схема «PI 22, источник нитания Е и резисторы R диодно-логических схем «ИЛИ, образуе.мых в вершинах сети диодами 8 схем ИР1В ирп их соединении между собой.

Устройство работает следующим образом.

В исходном ноложении во всех моделях ветвей MB триггеры 6 устанавливаются в нулевое положение путем подачи сбросового сигнала на входы 23. Сигнал с нулевых выходов триггеров по шине 24 ноступает на вход

схемы «И 4 и удерживает ключи 3 в замкнутом состоянии.

В счетчики 5 заиосятся количества импульсов, моделирующие в донолнительном коде величииы пропускных способностей ветвей. Если

одновременно с задачей о максимальном потоке задача о кратчайшем пути на той сети не решается, то величина напряжения элемента 1 может быть установлена произвольной. В противном слу;йе она устанавливается

нропорциоиальиой продолжительности ветви задачи о кратчайшем пути. При отсутствии тока в ветви а-б выходиой сигнал нуль-органа 2 подает но шине 25 запрещающий потенциал на вход схемы «И 4.

Схемы моделей ветвей MB (см. фиг. 1) перед репгением задачн соедиияются между собой нолюсамн а и б в соответствии с тонологией сети. Полюсы 26 (входы схемы «И) объединяются по всей модели. К образовавшейся

иепи подключается еще одна модель ветви 14, длина которой в масштабе иапряжеиий больше самого длинного нути в сети, и источник тока 15. Ток последнего нотечет по кратчайшему пути сети. Так как в качестве элементов 1

использованы схемы с эквивалентами отрицательных сонротивлений, схема «И 4 будет обладать высокой разрешающей способностью и выделит единственный путь без разветвлений. В моделях ветвей этого пути иотечет ток источника 15, сработают нуль-оиганы 2 и подадут разрещающие потеициалы на схемы «И 4 по шипам 25.

Сигнал нуска модели, но/даиньи на вход 27, установит триггер 16 в единичное состояние,

выходной сигнал этого триггера откроет схему «И (вентнль) 17 и импульсы тактового генератора, подключенного к гочке 28, начнут поступать в измерительный счетчик 18 и на входы схем «И 4 моделей ветвей. Эти имиульсы, изображающие единицы потока, прои скаемого по сети, начнут заполнять счетчики 5 ветвей выбранного кратчайшего пути. Число этих импульсов будет соответствовать величиие потока, про 1ускаемого по выбранноСравняется с минимальной пропускной способностью одной из ветвей, образующих путь, счетчик 5 последней переполнится п сигнал переполнения по шине 29 установит триггер 6 в единичное состояние. Сигнал выхода триггера, появившийся на выходе 30, будет в дальнейшем использован в качестве сигнала насыщенности данной ветви; одновременно он же разорвет ключ и подаст запрещающий потенциал на схему «И 4 по шине 24.

Таким образом, по крайней мере одна пз ветвей кратчайшего пути окажется разорванной, и модель кратчайшего пути выберет следующий кратчайший путь, состоящий из ненасыщенных ветвей. До тех пор, пока не пропзойдет полное насыщение сети, модель будет работать аналогично. В момент насыщенпя ток источника 15 переключится на самый длипный путь сети, состоящий из одной ветви 14. Пропускная способность этой ветви становится равной нулю, поэтому на выходе 30 сразу появится сигнал, который установит триггер 16 в нулевое положение и остановит работу модели.

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

Индикацию ветвей сети, составляющих минимальное сечение (разрез), можно осуществить с помощью схемы, состоящей из индикаторов насыщенности ветвей, включенных в соответствии с топологией сети, причем выходы 30 схемы MB быть соединены с соответствующими входами 31 схемы // (см. фиг. 3).

Диоды 8 нри соединении ИНВ между собой вместе с сопротивлениями R и источником Е образуют схемы «ИЛИ/, включенные в вершинах сети. На полюс Н индикационной модели схемы 11 подключается источник напряжения 13, изображающий сигнал логической единицы. На выходе 32 схемы «И 10 появится сигнал принадлежности ветви минимальному сечению только в том случае, если вершина сети, к которой будет подключен полюс а, принадлежит множеству X, а верщина, к которой будет подключен полюс б,- множеству х.

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

Таким образом, схема 11, на полюс Н которой подается сигнал логической единицы, может рассматриваться не только как индикатор ветвей минимального сечения, но и как индикатор насыщенности путей в сети. Сигналы логической единицы появятся в вершинах модели сети, которые можно достигнуть, идя пз начала сети но ненасыщенным путям. В вершинах модели сети, которые, идя но ненасыщенным

путям, достигнуть нельзя, будут нулевые сигналы.

Характерной особенностью описанной модели является то, что точность н разрешающая

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

единственный путь.

При onncanini работы устройства предполагалось, что переходные процессы в схеме, образующей ненасыщенный путь, оканчиваются за время, меньшее периода импульсов геператора тактовой частоты. Это накладывает определенные требованпя к быстродействпю пульоргана 2 и ключей 3.

В том случае, когда в качестве этих элементов целесообразно применить нпзкочастотные

элементы, в частности электромеханические, в схему унравления модели необходимо ввестн элемеиты задержки.

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

Формирователь (линия задержки) 20 осуществляет задержку разрешающего потенциала схемы «И 22 всякий раз, ко. срабатывает один из триггеров 6 моделей ветвей или пусковой триггер 16. Это обеспечивается с помощью

импульсной схемы «ИЛИ 19, на входы которой 33, 34, 35 подаются сигналы с выхода 30 моделей ветве11. На входы 36 н 37 подаются импульсы тактового генератора с некоторым сдвигом, чтобы осуществить синхронизацню

пускового сигнала на в.ходе 27 и исключить явление «гонок в схеме унравления. В остальном работа схемы по это.му вариант} не отлнчается от работы описанных выше схем.

Предмет и з о б р е т е н п я

1. Устройство для решения задачи о максимальном потоке в сетл, содержашее моделп ветвей, соедпненные между собой нервыми н

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

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

ff26

un

ННб

a

v-:

х ----i

j

Лл

20

гт

J7 7