Модель ветви для определения экстремальных потоков в сетях

Союз Советских Социалистических Республик(72) Авторы изобретения В. Федотовинской С А. Г. Додонов, В, В. Федотов, Ни Я. Я, фенюкнститут электродинамики АН У 1) Заявитель(54) МОДЕЛЬ ВЕТВИ ДЛЯ ОПРЕДЕЛЕ ЭКСТРЕМАЛЬНЫХ ПОТОКОВ В СЕТ Изобретение относится к области электронного моделирования и может быть использовано при построении цифровых специализированных вычислительных устройств для решения задач определения экстремальных потоков в сетях.Известно устройство для определения экстремальных путей в сетях 11, содержащее линии задержки и аналоговые элементы. Этим устройством невозможно решать задачи в минимальном потоке.Наиболее близкой по технической сущности к изобретению является модель ветви для определения экстремальных потоков в сетях 21, содержащая узлы регистрации величины потока, каждый из которых состоит из счетчика, первый вход которого непосредственно подключен к выходу первого элемента И, а второй вход счетчика через элемент ИЛИ соединен с выходами второго и третьего элементов И, первые входы первого и второго элементов И объединены и подключены к первому полюсу узла регистрации величины потока, первый вход третьего элемента И соединен со вторым полюсом узла регистрации величины потока, выход счетчика подключен ко входу элемента НЕ и к первому входу четвертого элемента И, выход которого соединен с третьим полюсом узла регистрации величины потока, первые полюса узлов регистрации величины потока объединены и подключены к первому полюсу модели, вторые полюса узлов регистрации величины потока 5 объединены и соединены со вторым полюсом модели, четвертые полюса узлов регистрации величины потока объединены и подключены к третьему полюсу модели, пятые полюса узлов регистрации величины по тока объединены и подключены к четвертому полюсу модели, шестые полюса узлов регистрации величины потока объединены и подключены к пятому полюсу модели, третьи полюса первого и второго узлов регист З рации величины потока соединены соответственно с шестым и седьмым полюсами модели.Описанная модель так же не обеспечивает возможность определения величины ми нимальпого потока. Целью изобретения является расширение функциональных возможностей.Поставленная цель достигается тем, что вмодель ветви введены выходной выпрями тель, дополнительные элементы И и триггер, и в каждый узел регистрации величины потока - пятый, шестой и седьмой элементы И, выпрямитель и триггер, причем выход дополнительного триггера подключен 30 к первому входу первого дополнительногоэлемента И и к седьмым полюсам узлов регистрации величины потока, вход дополнительного триггера подключен к выходу второго дополнительного элемента И, первый вход которого соединен с восьмым полюсом модели, второй вход второго дополнительного элемента И соединен с восьмыми полюсами узлов регистрации величины потока, первый вход третьего дополнительного элемента И подключен к девятому полюсу первого узла регистрации величины потока, выход третьего дополнительного элемента И соединен с девятым полюсом модели, второй вход третьего дополнительного элемента И подключен к десятому полюсу модели, к девятому полюсу второго узла регистрации величины потока и ко второму входу первого дополнительного элемента И, выход которого непосредственно соединен с одиннадцатым полюсом модели, а через выходной выпрямитель подключен к двенадцатому полюсу модели и к десятым полюсам узлов регистрации величины потока, причем первые входы пятого и шестого элементов И каждого узла регистрации величины потока объединены и подключены к одиннадцатому полюсу соответствующего узла, одиннадцатые полюса узлов регистрации величины потока соединены соответственно с тринадцатым и четырнадцатым полюсами модели, второй вход пятого элемента И каждого узла регистрации величины потока подключен к четвертому полюсу соответствующего узла, второй вход шестого элемента И соединен с пятым полюсом соответствующего узла, выходы пятого и шестого элементов И подключены к триггеру, выход триггера первого узла регистрации величины потока подключен ко вторым входам первого, четвертого и к одному входу седьмого элементов И и к восьмому полюсу соответствующего узла, другие входы седьмого элемента И соединены с выходом элемента НЕ и с шестым и двенадцатым полюсами соответствующего узла регистрации величины потока, выход седьмого элемента И первого узла регистрации величины потока непосредственно соединен с девятым и через выпрямитель - с десятым полюсами соответствующего узла, вторые входы третьего и второго элементов И первого узла регистрации величины потока подключены к тринадцатому и четырнадцатому полюсам соответствующего узла, выход триггера второго узла регистрации величины потока подключен ко вторым входам второго и четвертого и к первому входу седьмого элементов И и к двенадцатому полюсу соответствующего узла, второй и третий входы седьмого элемента И второго узла регистрации величины потока соединены с шестым и десятым полюсами соответствующего узла, четвертый вход седьмого элемента И второго узла регистрации величины потока объединен с 10 15 20 25 30 35 40 45 50 55 60 65 первым входом третьего элемента И и подключен к выходу элемента НЕ и к девятому полюсу соответствующего узла, второй и третий входы третьего элемента И соединены со вторым и седьмым полюсами соответствующего узла, выход седьмого элемента И через соответствующий выпрямитель подключен к тринадцатому полюсу второго узла регистрации величины потока, четырнадцатый полюс которого соединен с выходом соответствующего счетчика, двенадцатый полюс первого и тринадцатый полюс второго узлов регистрации величины потока об ьединепы и подключены к пятнадцатому полюсу модели.Структурная схема модели ветви изображена на чертеже.Она содержит узлы 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, чем производит блокировку входа модели ветви, После этого проверяется наличие пути из10 начального узла сети с хотя бы одной ветвью с ненулевой нижней границей пропускной способности, Для этого на полюсах 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 моделей ветвей, находящиеся в единичном состоянии, будут определять путь из начального узла сети к коне гному, проходящий по крайней глере через одну ветвь с ненулевой нижней границей пропускной способности. По этому пути пропускается поток такой величины, чтобы во всех ветвях выполнялись ограниче 15 2 О 25 30 35 4 О 45 50 55 60 65 ния, на,.оженные снизу. Прц этом нижняя граница пропускной способности ветвей этого пути, записанпая в реверсивном счетчике 31, становится равной нулю, а избыток потока ветви над нижней границец пропускной способности записывается в счетчики 30.Это происходит следующим образом. В моделях ветвей, принадлежащих выбранному пути, разрешение, снимаемое с единичного выхода триггера 5, поступает на первый вход элемента И 21. Если в счетчике 31 модели ветви запцсана ненулевая нижняя граница пропускной способности, то через элемент НЕ 29 сигнал поступит на второй вход элемента И 21 и затем на полюс 44. Прц поступлении тактовых импульсов на полюса 39 всех моделей ветвей эти импульсы поступят сначала на вход элементов И 11 ц И 18, затем, пройдя через элемент И 18 ц элемент ИЛИ 24, импульсы поступят на вход счетчика 31, уменьшая запцсанную там нижнюю границу пропускной способности ветви. Как только она станет равной цуло, эти импульсы перестанут поступать ца вход счетчика 31, так как выход этого счетчика через элемент НЕ 29 заблокирует вход элемента И 18. Кроме того, тактовые импульсы начнут поступать через элемент И 11 ц элемент ИЛИ 23 на вход реверсивного счетчика 30. При этом в счетчике 30 будут накапливаться импульсы, характеризующие величину избытка потока в ветви, Импульсы на полюс 39 поступают до тех пор, пока есть сигнал на полюсе 44, хотя бы одцоц модели ветви, сигнализирующцй о том, что по крайней мере в одной из ветвей выбранного пути поток меньше нижнсй границы. Как только на полюсах 44 пропадет сигнал, прекращается подача тактовых импульсов на полюс 39.Если после этого в сети есть сигнал на полюсе 45, хотя бы у одной модели ветви, что характеризует наличие ветви с ненулевой нижней границей пропускной способности, то процеди ра поиска пути и увеличение потока, описанная выше, повторяется,Если таких ветвей нет, то допустимый поток построен ц его величина равна суммарному числу импульсов, поступивших на полюса 39,С целью минимизации построенного допустимогопотока отыскивается путь из на. чальцого узла сети в конечный, проходящий только по ветвям с ненулевым избытком потока. Для этого устанавливаются в единичное состояцие все триггеры 3 и 4 и проверяется наличие пути от начального узла сети к конечному. При этом подается импульс в начальный узел сети и разрешение ца полюса ЗЗ всех моделец ветвей. Если в счетчике 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 содержимое станет равным нулю. Если при этом в счет 510 15 20 25 30 35 40 45 50 55 60 65 чике 30 записан нуль, то его сигнал, пройдя элемент И 12, появится на полюсе 42.Аналогично, если в счетчике 31 записан пуль. то сго сигнал, пройдя элемент И 19, появится на полюсе 46,Появление сигналов на одном из полюсов 42 и 46 прекращает поступление импульсов на полюса 35. После этого опять проверяется наличие пути от начального узла к конечному, если такой путь имеется, то минимизация потока продолжается аналогично описанной выше до тех пор, пока такого пути не будет. После исчезновения пути от начального узла к конечному минимальный поток построен, и его суммарная величина меньше величины допустимого потока на количество импульсов, поступивших на полюс 35.Построение максимального потока происходит аналогично минимизации допустимого потока. При этом перед решением задачи в счетчики 30 и 31 записываются максимальныс границы пропускных способностей ветвей в соответственном направлении,Для направленной ветви в счетчик, соответствующий обратному направлению, записывается нуль, Далее работа устройства осуществляется, как и при минимизации допустимого потока, с тем различием, что числа, записанные в реверсивных счетчиках 30 и 31, имеют смысл максимальной границы пропускной способности ветви в соответствующем направлении, а не избыток потока.Суммарное количество импульсов, поступивших при этом на полюсе 35, равно суммарной величине максимального потока,Введение новых элементов и связей позволяет при помощи рассматриваемой модели решать задачи по определению величины максимального и минимального потоков в сетях, которые имеют большое значение при распределении информационных потоков по каналам связи, при проектировании каналов связи, при распределении грузопотока по транспортным линиям и т. д. Формула изобретенияМодель ветви для определения экстремальных потоков в сетях, содержащая узлы регистрации величины потока, каждый из которых состоит из счетчика, первый вход которого непосредственно подключен к выходу первого элемента И, а второй вход счетчика через элемент ИЛИ соединен с выходами второго и третьего элементов И, первые входы первого и второго элементов И объединены и подключены к первому полюсу узла регистрации величины потока, первый вход третьего элемента И соединен со вторым полюсом узла регистрации величины потока, выход счетчика подключен ко входу элемента НЕ и к первому входу четвертого элемента И, выход которого соединен с третьим полюсом узла регистрации ве 640302 10личины потока, первые полюса узлов регистрации величины потока объединены и подключены к первому полюсу модели, вторые полюса узлов регистрации величины потока объединены и соединены со вторым полюсом модели, четвертые полюса узлов регистрации величины потока объединены и подключены к третьему полюсу модели, пятые полюса узлов регистрации величины потока объединены и подключены к четвертому полюсу модели, шестые полюса узлов регистрации величины потока объединены и подключены к пятому полюсу модели, третьи полюса первого и второго узлов регистрации величины потока соединены соответственно с шестым и седьмым полюсами модели, отличающаяся тем, что, с целью расширения функциональных возможностей за счет определения величины минимального потока, в нее введены выходной выпрямитель, дополнительные элементы И и триггер и в каждый узел регистрации величины потока пятый, шестой и седьмой элементы И, выпрямитель и триггер, причем выход дополнительного триггера подключен к первому входу первого дополнительного элемента И и к седьмым полюсам узлов регистрации величины потока, вход дополнительного триггера подключен к выходу второго дополнительного элемента И, первый вход которого соединен с восьмым полюсом модели, второй вход второго дополнительного элемента И соединен с восьмыми полюсами узлов регистрации величины потока, первый вход третьего дополнительного элемента И подключен к девятому полюсу первого узла регистрации величины потока, выход третьего дополнительного элемента И соединен с девятым полюсом модели, второй вход третьего дополнительного элемента И подключен к десятому полюсу модели, к девятому полюсу второго узла регистрации величины потока и ко второму входу первого дополнительного элемента И, выход которого непосредственно соединен с одиннадцатым полюсом модели, а через выходной выпрямитель подключен к двенадцатому полюсу модели и к десятым полюсам узлов регистрации величины потока, причем первые входы пятого и шестого элементов И каждого узла регистрации величины потока объединены и подключены к одиннадцатому полюсу соответствующего узла, одиннадцатые полюса узлов регистрации величины потока соединены соответственно с тринадцатым и четырнадцатым полюсами модели, второй5 10 15 20 25 30 35 40 45 50 55 вход пятого элемента И каждого узла регистрации величины потока подключен к четвертому полюсу соответствующего узла, второй вход шестого элемента И соединен с пятым полюсом соответствующего узла, выходы пятого и шестого элементов И подключены к триггеру, выход триггера первого узла регистрации величины потока подключен ко вторым входам первого, четвертого и к одному входу седьмого элементов И и к восьмому полюсу соответствующего узла, другие входы седьмого элемента И соединены с выходом элемента НЕ и с шестым и двенадцатым полюсами соответствующего узла регистрации величины потока, выход седьмого элемента И первого узла регистрации величины потока непосредственно соединен с девятым и через выпрямитель - с десятым полюсами соответствующего узла, вторые входы третьего и второго элементов И первого узла регистрации величины потока подключены к тринадцатому и четырнадцатому полюсам соответствующего узла, выход триггера второго узла регистрации величины потока подключен ко вторым входам второго и четвертого и к первому входу седьмого элементов и к двенадцатому полюсу соответствующего узла, второй и третий входы седьмого элемента И второго узла регистрации величины потока соединены с шестым и десятым полюсами соответствующего узла, четвертый вход седьмого элемента И второго узла регистрации величины потока объединен с первым входом третьего элемента И и подключен к выходу элемента НЕ и к девятому полюсу соответствующего узла, второй и третий входы третьего элемента И соединены со вторым и седьмым полюсами соответствующего узла, выход седьмого элемента И через соответствующий выпрямитель подключен к тринадцатому полюсу второго узла регистрации величины потока, четырнадцатый полос которого соединен с выходом соответствующего счетчика, двенадцатый полюс первого и тринадцатый полюс второго узлов регистрации величины потока объединены и подключены к пятнадцатому полюсу модели.Источники информации,принятые во внимание при экспертизе 1, Авторское свидетельство СССР Мо 432508, кл. 6 06 Р 15/20, 1974.2. Васильев В. В, и др. Гибридные модели задач оптимизаций. М., Наукова Думка, 1974, с. 78,640302 Составитель И. Загорбининаактор Б, Герцен Техред А, Камышникова Корректор Л. Корого Типография, пр. Сапунова. 2 аз 2223/7 Изд.782 Тираж 799НПО Государственного комитета СССР по делам изобретений113035, Москва, Ж, Раушская наб., д. 4/5 Подписноеткрытий