Модель ветви для определения экстремальных потоков в сетях Советский патент 1978 года по МПК G06F15/173 

1

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

Известно устройство для определения экстремальных путей в сетях 1, содержащее линии задержки и аналоговые элементы. Этим устройством невозможно решать задачи в минимальном потоке.

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

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

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

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

к первому входу первого дополнительного элемента И и к седьмым полюсам узлов регистрации величины нотока, вход дополнительного триггера подключен к выходу второго донолнительного элемента И, первый вход которого соединен с восьмым нолюсом модели, второй вход второго дополнительного элемента И соединен с восьмыми нолюсами узлов регистрации величины потока, первый вход третьего дополнительного элемента И подключен к девятому полюсу первого узла регистрации величины потока, выход третьего дополнительного элемента И соединен с девятым нолюсом модели, второй вход третьего дополнительного элемента И подключен к десятому полюсу модели, к девятому полюсу второго узла регистрации величины потока и ко второму входу первого дополнительного элемента И, выход которого неносредственно соединен с одиннадцатым полюсом модели, а через выходной выпрямитель подключен к двенадцатому полюсу модели и к десятым нолюсам узлов регистрации величины потока, причем первые входы пятого и шестого элементов И каждого узла регистрации величины потока объединены и подключены к одиннадцатому полюсу соответствующего узла, одиннадцатые полюса узлов регистрации величины нотока соединены соответственно с тринадцатым и четырнадцатым полюсами модели, второй вход пятого элемента И каждого узла регистрации величины потока подключен к четвертому полюсу соответствующего узла, второй вход шестого элемента И соединен с пятым полюсом соответствующего узла, выходы пятого и шестого элементов И нодключены к триггеру, выход триггера первого узла регистрации величины потока подключен ко вторым входам первого, четвертого и к одному входу седьмого элементов И и к восьмому полюсу соответствующего узла, другие входы седьмого элемента И соединены с выходом элемента НЕ и с шестым и двенадцатым полюсами соответствующего узла регистрации величины нотока, выход седьмого элемента И первого узла регистрации величины потока непосредственно соединен с девятым и через выпрямитель - с десятым полюсами соответствующего узла, вторые входы третьего и второго элементов И первого узла регистрации величины потока подключены к тринадцатому и четырнадцатому нолюсам соответствующего узла, выход триггера второго узла регистрации величины потока подключен ко вторым входам второго и четвертого и к первому входу седьмого элементов И и к двенадцатому полюсу соответствующего узла, второй и третий входы седьмого элемента И второго узла регистрации величины потока соединены с шестым и десятым нолюсами соответствующего узла, четвертый вход седьмого элемента И второго узла регистрации величины потока объединен с первым входом третьего элемента И н подключен к выходу элемента НЕ и к девятому полюсу соответствующего узла, второй и третий входы третьего элемента Н соединены со вторым и седьмым полюсами соответствующего узла, выход седьмого элемента И через соответствующий выпрямитель подключен к тринадцатому полюсу второго узла регистрации величины потока, четырнадцатый полюс которого соединен с выходом соответствующего счетчика, двенадцатый полюс первого и тринадцатый полюс второго узлов регистрации величины иотока объединены и подключены к пятнадцатому полюсу модели. Структурная схема модели ветви изображена на чертеже. Она содержит узлы 1, 2 регистрации величины потока, триггеры 3, 4, дополнительный триггер 5, элементы И 6-19, дополнительные элементы И 20-22, элементы ИЛИ 23, 24, выпрямители 25, 26, выходной выпрямитель 27, элементы НЕ 28, 29, счетчики 30, 31, нолюеа модели 32-46. Модель ветви для определения экстремальных нотоков в сетях работает следующим образом. В начальный момент времени посредством полюсов 36 и 37 соседние модели ветвей соединяются между собой в соответствии с тонологией исследуемой сети. При решении задачи о минимальном потоке нижиие границы пропускных способностей ветвей записываются в счетчики 31, а счетчики 30 находятся в нулевом состоянии. Триггеры 3-5 всех моделей ветвей устанавливаются в нулевое состояние (установочные шины на чертеже не ноказаны). При определении минимального потока в начале определяется допустимый поток, удовлетворяющий ограничениям всех ветвей. С этой целью определяют произвольный нуть, содержащий хотя бы одну ветвь с ненулевой нижней границей нропускной способностн. Выбор указанного пути производится следующим образом. Устанавливаются в единичное состояние триггеры 3 всех моделей ветвей. Триггеры 4 и 5 остаются в нулевом состоянии. При наличии в сети ветвей с ненулевой нижней границей пропускной способности, о чем свидетельствует наличие сигнала хотя бы на одном из полюсов 45 моделей ветвей, производится просмотр всех ветвей сети в произвольно заданном порядке. Для этого подается сигнал на полюс 32, чем осуществляется выбор той или иной модели ветви. Подачей импульса на полюса 34 всех моделей ветвей триггер 3 выбранной модели ветви зстанавливается в нулевое состояние. улевое состояние триггера 3 снимает разрешение с входа элемента И 8, чем производит блокировку входа модели ветви. После этого проверяется налнчие пути из

начального узла сети с хотя бы одной ветвью с ненулевой нижней границей пронускной снособности. Для этого на полюсах 33 всех моделей ветвей подается разрешение, и в начальный узел сети имнульс иоступает, который, нроходя с полюса 36 через элемент И 8 и выпрямитель 25 па полюс 37, будет распространяться по сети. При этом тот же сигнал, нройдя элемент И 22, появится на полюсе 38 тех моделей ветвей, у которых в реверсивном счетчике 31 записана ненулевая нижняя граница проп ткной способности. Появление сигнала хотя бы на одном из полюсов 38 моделей ветвей свидетельствует о том, что есть путь от начального узла сети к хотя бы одной модели ветви с ненулевой нижней границей иронускной способпости. В этом случае выбранную ранее ветвь можно оставпть заблокированной по входу. В нротивном случае подачей имнульса на полюса 40 через элемент И 6 триггер 3 устанавливается в единичное состояние, чем снимается блокировка входа выбранной модели ветви. После просмотра всех моделей ветвей триггеры 3, оставшиеся в единичном состоянии, определяют участок пути от начального узла, содержан его только одну ветвь с ненулевым ограничением пропускной способности снизу. Путем подачи импульса па полюса 43 через элемепт И 20, если триггеры 3 соответствуюшнх этому участку моделей ветвей иаходятся в едипичном состоянии, устанавливаются триггеры 5 в единичное состояние.

После этого производится оиределение пути от модели ветви с ненулевой нижней границей иропускной способности, принадлежашей запомненному выше участку, до конечного узла сети. Для этого подается разрешение на полюса 33.

В моделях ветвей, принадлежашнх ранее запомпенному пути, сигпал с выхода триггера 5 проходит через элемент И 21 на полюс 44 н через выходной вынрямнтель 27 на полюс 37. Таким образом, нолюс 37 в модели ветви, которой заканчивается выделенный учаеток нути, будет являться генератором разрешения, так как у этой модели ветви на втором входе элемента И 21 есть разрешение, снимаемое через элемепт НЕ 29 с выхода счетчика 31. Это разрешение распространяется но сети в последующих моделях ветвей с полюса 36 на нолюс 37, как было описано ранее. Процесс запоминання этого участка пути осуш;ествляется аналогично описанному ранее. При этом триггеры 5 моделей ветвей, находящиеся в единичном состоянии, будут онределять нзть из начального узла сети к конечному, проходящий по крайней мере через ОДНУ ветвь с ненулевой нижней границей пропускной способности. По этому пути пропускается ноток такой величины, чтобы во всех ветвях выполнялись ограничения, наложенные сннзу. При этом нижняя граница пропускной снособности ветвей этого пути, записанная в реверсивном счетчике 31, становится равной нулю, а избыток потока ветви над нижней границей пропускной способности записывается в счетчики 30.

Это происходит следующим образом. В моделях ветвей, нринадлежащнх выбранному нутн, разрешение, снимаемое с единнчного выхода триггера 5, поступает на первый вход элемента П 21. Если в счетчике 31 модели ветви записана ненулевая нижняя граница нронускной снособности, то

через элемент НЕ 29 сигнал поступит на второй вход элемента П 21 и затем на полюс 44. При поступлении тактовых импульсов на полюса 39 всех моделей ветвей эти импульсы поступят сначала на вход элементов П И и И 18, затем, пройдя через элемент П 18 н элемент Р1ЛИ 24, имнульсы поступят на вход счетчнка 31, уменьщая запнеанную там нпжнюю границу пронускной снособности ветвн. Как только она станет

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

элемент И 11 н элемент ИЛИ 23 на вход реверсивного счетчпка 30. При этом в счетчике 30 будут накапливаться импульсы, характеризующие величину избытка нотока в ветвн. Имнульсы на нолюс 39 поступают до

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

пропадет сигнал, прекращается подача тактовых импзльсов на полюс 39.

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

Если таких ветвей нет, то донустимый поток построен и его величина равна суммарному чнслу имнульсов, ноступивших на полюса 39.

С целью минимизации построенного допустимого потока отыскпвается путь из начального узла сети в конечный, проходяЩнй только по ветвям с ненулевым избытком нотока. Для этого устанавливаются в единичное состояние все триггеры 3 и 4 и проверяется наличие нути от начального узла сети к конечному. При этом подается

импульс в начальный узел сети и разрешение на полюса 33 всех моделей ветвей. Если в счетчике 30 модели ветви записан ненулевой нзбыток нотока ветви, то с выхода этого счетчика через элемент НЕ 28

на вход элемента И 8 поступает сигнал, который будет разрешать прохождение импульсов с полюса 36 на полюс 37. Аналогично, при условии, что триггер 4 находится в единичном состоянии и в реверсивном счетчике 31 записан ненулевой избыток потока, сигнал, пришедший на полюс 37, передается на полюс 36.

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

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

После просмотра всех ветвей в обоих направлениях оставшиеся триггеры 3 и 4 в единичном состоянии определяют путь из начального узла в конечный по ветвям с ненулевым избытком. В ветвях этого пути поток з еньшается на величину минимального избытка потока, т. е. уменьшаются избытки потока в ветвях этого пути по направлению от начального узла к конечному. Одновременно увеличиваются избытки потока в тех же ветвях в противоположном направлении. Это происходит следуюш,им образом. На полюса 35 всех моделей ветвей подаются счетные импульсы. Предположим, что в рассматриваемой ветви остался в единичном состоянии триггер 3. Тогда сигнал с единичного выхода этого триггера выдаст разрешение на элементы И 9 и 16. В это же время на элементы И 10 и 17 подан запрет, так как триггер 4 находится в нулевом состоянии. Таким образом, счетные импульсы, поступаюш,ие на полюс 35, будут проходить через элемент И 9 на вход счетчика 30, уменьшая тем самым записанный в нем избыток потока, и одновременно через элемент И 16 импульсы поступают на вход счетчика 31, увеличивая тем самым записанный в нем избыток потока.

Аналогично, если в единичном состоянии остался триггер 4, а не 3, при поступлении импульсов на полюс 35 увеличивается содержимое счетчика 30 и уменьшается содержимое счетчика 31.

Поступление импульсов на полюс 35 должно прекратиться как только записанное в одном из счетчиков 30 или 31 содержимое станет равным нулю. Если при этом в счетчике 30 записан нуль, то его сигнал, пройдя элемент И 12, появится на полюсе 42.

Аналогично, если в счетчике 31 записан нуль, то его сигнал, нройдя элемент И 19, 5 появится на полюсе 46.

Появление сигналов на одном из полюсов 42 и 46 прекрагцает поступление импульсов на полюса 35. После этого опять проверяется наличие пути от начального

10 узла к конечному, если такой путь имеется, то минимизация потока продолжается аналогично описанной выше до тех пор, пока такого пути не будет. После исчезновения пути от начального узла к конечному мини15 мальный поток построен, н его суммарная величина меньше величины допустимого потока на количество импульсов, поступивших па полюс 35. Построение максимального потока происходит аналогично минимизации допустимого потока. При этом перед решением задачи в счетчики 30 и 31 записываются максимальные границы пропускных способностей ветвей в соответственном направлепии.

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

0 числа, записанные в реверсивных счетчиках 30 и 31, имеют смысл максимальной границы пропускной способности ветви в соответствующем направлении, а не избыток потока.

5 Суммарное количество импульсов, поступивших при этом на полюсе 35, равно суммарной величине максимального потока.

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

изобретения

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

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

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

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

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

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

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

Источники информации,

принятые во внимание при экспертизе

1.Авторское свидетельство СССР № 432508, кл. G 06F 15/20, 1974.

2.Васильев В. В. и др. Гибридные модели задач оптимизаций. М., «Наукова Думка, 1974, с. 78. -