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

ступает на второй вход схемы совпадения И3 и устанавливает триг­ гер 7\ в нулевое состояние. Импульс после схемы совпадения, при­ шедший на выход И 3, установит триггер Т 3 в единичное состояние и подаст сигнал на остановку решения, так как первый сигнал, по­ явившийся в конечном городе и прошедший все города, и является решением задачи коммивояжера.

Состояние триггеров ветвей Т 3, входящих в конечный узел, укажет по какой ветви этот сигнал пришел.

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

В каждом промежуточном городе должна производиться запись признака данного города и задержка импульса, как указывалось ранее, на число 2mntma7L импульсов.

Эти операции осуществляются в модели промежуточного города^ функциональная схема которого приведена на рис. 94. Модель промежуточного города работает так. При поступлении на вход модели города сигнала его первый импульс устанавливает триггер Тг через схему совпадения в единичное состояние. При этом откры­ вается схема совпадения й 2 и в счетчик поступают импульсы от генератора тактовых импульсов ГИ.

Импульсы сигнала поступают также на схему разделения ИЛИ и после нее — на линию задержки города ЛЗУ. После того как счет­ чик отсчитает m импульсов, где m — номер города, на его выходе появится импульс, который поступает на схему разделения ИЛИ. Этот импульс, также как и импульсы сигнала, проходит в Л З У ,

153

После поступления на вход п-го импульса на его выходе появля­ ется сигнал, который устанавливает триггер 7\ в нулевое состояние. Таким образом, модель города устанавливается в исходное состояние

иждет прихода следующего сигнала.

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

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

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

Таким образом, время получения конфигурации пути коммивоя­ жера будет

Время решения задачи коммивояжера, как видно из формулы (*), не зависит от коэффициентов матрицы расстояний. По-видимо­ му, такие цифровые аналоги могут быть построены для решения задач небольшого объема (порядка 15—20 городов).

5.7. ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОЙ СВЯЗЫВАЮЩЕЙ СЕТИ НА ГРАФЕ С ПОМОЩ ЬЮ ЦИФРОВОЙ МОДЕЛИ

Среди множества комбинаторных задач теории графов достаточно часто встречается задача о нахождении оптимальной (максимальной или минимальной) связывающей сети, суть которой состоит в следующем [109, 171].

В конечном неориентированном графе G с известными длинами

154

На рис. 95 приведен пример задачи о нахождении кратчайшей (минимальной) связывающей сети. Числа, проставленные около ребер, равны их длинам L = 7, l!d = 8 и т. д. Жирной линией показана кратчайшая связывающая сеть, ее длина составляет 14 еди­ ниц. Заметим, что кратчайшая связывающая сеть не гарантирует кратчайших расстояний между какими-либо вершинами графа и, таким образом, эта задача отличается от задачи о кратчайшем пути. Например, кратчайший путь между вершинами а и b проходит по ребру а — Ь и составляет 7 единиц, тогда как по связывающей сети его длина равна 9 единицам.

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

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

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

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

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

155

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

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

Функциональная схема модели в первом варианте изображена на рис. 96. Каждая из моделей ребер (на рис. 96 показана схема модели ребра се) содержит ключ К, управляемый триггером Т с раздельными входами, схему совпадения И и цифровую линию задержки, например счетчик. Полюсы ключей моделей ребер соеди­ няются между собой в соответствии с топологией графа. К одному из узлов получившейся цепи подключается источник напряжения,, изображающий сигнал логической единицы. Все остальные узлы подключаются к многовходовой схеме типа Н Е — И, которая обра­ зует индикатор нарушения связности графа, моделью которого является набранная цепь. Счетные входы всех счетчиков объеди­ няются по всей модели и подключаются к схеме пуска и регенера­ ции, содержащей счетчик, триггер и схему совпадения И. Модель работает следующим образом.

В исходном состоянии триггеры моделей ребер находятся в еди­ ничном положении. Сигналы единичных выходов триггеров управля­ ют ключами К, удерживая их в замкнутом состоянии. Приі'.этом на­ пряжение источника э. д. с. существует во всех узлах цепи и сигнал нарушения связности на выходе схемы НЕ — И отсутствует. В счет­ чик моделей ребер предварительно заносятся количества импуль­ сов, пропорциональные длинам ребер в прямом коде, если нужно решить задачу о нахождении кратчайшей связывающей цепи, и в дополнительном коде — в противном случае.

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

При подаче сигнала пуска на единичный вход триггера подается разрешающий сигнал на вход схемы И узла пуска и регенерации,, и импульсы ГИг начинают поступать на счетные входы всех счетчи­ ков модели, которые образуют индикатор экстремальных сигналов. Таким образом, первым появится сигнал переполнения счетчика, соответствующего наиболее длинной (короткой) ветви. Этот сигнал переполнения установит триггер модели ребра (ветви) в нулевое положение и выключит из схемы рассматриваемое ребро по сигналу ГИ2. Если при этом не нарушится связность графа, схема НЕ — И не выдаст разрешающего потенциала и сигнал ГИ3 не изменит со-

156

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

157

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

Рис. 97

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

Например, пусть в счетчиках необходимо записать информацию о длинах 7 ребер графа: /х = 63, /2 = ls = 56, /4 = ... = /7 = 10.

1Б8