Файл: Васильев, В. В. Гибридные модели задач оптимизации.pdf

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

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

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

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

Z-'max /шах ( t l— 1), (5.13)

где Lmax — максимальная длина пути в мультисети; п — число уз­ лов мультисети, число различных по длине путей в модели мульти­ сети (Л/д) должно удовлетворять отношению

Из сравнения выражений (1.11) и (5.14) следует, что число раз­ новеликих путей в дискретной модели мультисети может быть зна­ чительно (иногда на несколько порядков) меньше числа топологи­ чески различных путей на графе мультисети. Это позволяет сделать предположение о наличии большого числа равновеликих путей в указанной модели мультисети. Заметим, однако, что данное об­ стоятельство ни в какой мере не дает оснований для оптимизма в оценке метода переборов при определении пути заданной длины в мультисети, так как указанный путь может быть единственным. Наличие же множества равновеликих путей заданной длины в мультисети требует учета специфики выделения этих путей при моделировании.

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

133

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

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

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

В связи с изложенным при конструировании моделирующе­ го устройства для определения путей заданной длины следует предусмотреть следующее:

приоритетный выбор допусти­ мой длины искомого пути, т. е.

выбор подмножества равновеликих путей допустимой длины; приоритетный выбор длины каждой принадлежащей искомому

пути ветви, т. е. выбор одной или нескольких равновеликих ветвей в каждом цикле работы модели;

выделение (индикация) только таких ветвей, которые образуют единственный путь или подсеть равновеликих путей;

применение схемы индикации отсутствия решения за­ дачи.

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

134

где (Др) — квантор общности по p; Lp — длина р-го пути в муль­ тисети; Lx — выбираемая длина искомого пути; СЛ ^//) — квантор общности по іАу; Ѵ] — множество ветвей, оканчивающихся в

135

j-u узле и принадлежащих путям выбранной допустимой длины в мультисети; (/^-)*— выбираемая длина ветви.

Рассмотрим пример построения функциональных схем цифрового моделирующего устройства для определения путей допустимой или однозначно заданной длины в мультисети, общая блок-схема кото­ рого, изображенная на рис. 81, состоит из цифрового аналога муль­ тисети ЩАМ), устройства управления (УУ), генератора тактовых импульсов (ГИ) и блока питания (БП).

Функциональные схемы моделей ветви и узла при совмещенном

моделей узлов коммутируются между собой при топологическом наборе ЦАМ. Пример коммутации моделей ветвей и узлов для фрагмента мультисети, изображенного на рис. 83, а, показан на рис. 83, б, где МВ — модель ветви, М У — модель узла.

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

Устройство управления, структурная схема которого приведена на рис. 84, содержит следующие основные узлы: управляющий цифровой автомат (УЦА), предназначенный для выработки и рас­

136

пределения управляющих сигналов; задатчик пределов длины пути (ЗД) — для задания и запоминания кодов, соответствующих до­ пустимым значениям длины искомого пути; запоминающий счетчик импульсов (ЗС) — для вычисления и запоминания фактической дли­ ны искомого пути; операционный счетчик импульсов (ОС) — для оперативных вычислений в процессе работы устройства; узел сравне­ ния (УС) — для сравнения выходного кода запоминающего счет­ чика с выходными кодами операционного счетчика и задатчика длины пути; узел индикации отсутствия решения (ИОР) — для

Рис. 84

сигнализации об отсутствии в данной мультисети пути заданной до­ пустимой длины; узел индикации длины пути (ИДП) — для ви­ зуального отображения числа, соответствующего фактической длине искомого пути.

В качестве ЗС и ОС могут быть использованы суммирующие счетчики импульсов, каждый из которых обладает емкостью, со­ ответствующей максимальной длине пути в мультисети, и позволяет осуществлять последовательный счет импульсов тактового генера­ тора, поступающих на вход, а также вывод информации о содержи­ мом в параллельном коде. Параллельный выходной код запоминаю­ щего счетчика управляет узлом индикации длины пути, а выход переполнения (выход импульсов переноса старшего разряда) — узлом индикации отсутствия решения.

Задатчик пределов длины пути представляет собой устройство, содержащее два регистра чисел, которые позволяют осуществлять запись и вывод в параллельном коде информации о максимальной (L + AL) и минимальной (L — AL) допустимых длинах искомого пути.

Узел сравнения может быть выполнен на логических схемах совпадения, осуществляющих поразрядное сравнение параллельных кодов, и состоит из трех независимых каналов: канала сравнения кода ЗС с кодом ОС (Кі), канала сравнения кода ЗС с кодом регистра

1 3 7

минимальной длины пути ЗД {К2) и канала сравнения кода ЗС с кодом регистра максимальной длины пути ЗД (Кз)•

Узлы индикации отсутствия решения и индикации длины пути могут содержать любые электронные управляемые индикаторы.

Рассмотрим работу моделирующего устройства при определении пути допустимой длины в мультисети.

В исходном состоянии на задатчике пределов длины пути уста­ новлены соответствующие коды, триггер модели конечного узла мультисети в единичном состоянии, все остальные триггеры и ре­ гистры сдвига моделей ветвей и узлов, а также счетчики импульсов устройства управления — в нулевом состоянии, на шинах А, С, D, Е, F, L, N , Q — запрещающий потенциал.

После пуска на шину А подается разрешающий потенциал, а на вход модели начального узла мультисети — одиночный импульс, синхронизированный с импульсами тактового генератора («опра­ шивающий» импульс). Одновременно с этим разрешается поступле­ ние импульсов тактового генератора на входы запоминающего и опера­ ционного счетчиков устройства управления. Начинается «опрос» ЦАМ, состояние которого обеспечивает прохождение импульсных сигналов с функционального входа каждой модели узла через дизъюнктор 18 на вход регистра сдвига 13, с соответствующих выходов указан­ ного регистра — на входы моделей ветвей, выходящих из данного узла, и далее через конъюнктор 3 (по разрешению потенциала на шине А) и дизъюнктор 8 упомянутых моделей ветвей — на их функ­ циональные выходы.

При отсчете числа тактовых импульсов, соответствующего ми­ нимальной допустимой длине искомого пути, по сигналу из узла сравнения о совпадении выходного кода запоминающего счетчика с кодом регистра минимальной допустимой длины задатчика длины пути УЦА выдает разрешающий потенциал на шину С.

Если задача имеет решение в интервале времени отсчета числа тактовых импульсов, соответствующего допустимой длине искомого пути, то на входе одной или нескольких моделей ветвей, входящих в конечный узел мультисети, появится импульс, который через конъюнктор 5 (по разрешению потенциала единичного выхода триггера 14 модели конечного узла) и конъюнктор 6 (по разрешению потенциала на шине С) поступит на единичный вход триггера 1 соответствующих моделей ветвей и установит его в единичное состоя­ ние. Одновременно по сигналу на шинеП УЦА подаст запрещающий потенциал на шины Л и С и запретит поступление импульсов на вхо­ ды счетчиков устройства управления.

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

Дальше УЦА осуществляет сброс регистров сдвига моделей уз­ лов и операционного счетчика устройства управления в нулевое

138