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

Триггер 1 и конъюнктор 11 образуют узел пуска, который по сигналу с кнопки «пуск» выдает на вход триггера 2 одиночный им­ пульс, синхронизированный с импульсами ГИ2. Переход на новый цикл работы моделирующего устройства осуществляется по сигналу у1 0 при условии нулевого состояния триггера 14 модели начального узла мультисети.

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

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

где і — порядковый номер ветви искомого пути, считая от началь­ ного узла мультисети; / — порядковый номер рабочего цикла моделирующего устройства; а( — число импульсов ГИг, соответ­ ствующее длине і-й ветви искомого пути; b — число ветвей искомого пути; а — число импульсов ГИи соответствующее длине искомого пути.

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

ь

Т = Щ і = .-<» + ■>+ » [«.],

гдe f — частота тактовых импульсов ГИ1, гц.

С целью расширения функциональных возможностей рассмот­ ренного моделирующего устройства дополним модель ветви рис. 82 узлом, схема которого изображена на рис. 89, где 22 — триггер; 23 — дизъюнктор; 24 — диод.

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

При исходном единичном состоянии триггеров 22 моделей вет­ вей работа моделирующего устройства соответствует приведенному ранее описанию. В этом режиме можно определять пути заданной

о

Уст.

Рис. 89

допустимой и минимальной длины (при определении пути мини­ мальной длины на задатчике длины пути устанавливаются коды, соответствующие нулевой и максимальной допустимым длинам искомого пути).

При исходном нулевом состоянии триггеров 22 моделей ветвей появление сигнала на входе модели ветви приводит к установке соответствующего из них в единичное состояние. Однако для поступ­ ления указанного сигнала на вход модели конечного узла данной ветви необходимо наличие единичного состояния триггеров 2 2 мо­ делей всех ветвей, входящих в данный узел, так как при невыполне­ нии этого условия вход модели узла шунтируется цепью из прямого сопротивления диода 24, малого сопротивления проводящего плеча триггера 22 и шины «земля». Следовательно, сигнал на вход каждой модели узла передается только из модели ветви, принадлежащей пути максимальной длины в этот узел. При нулевом и максимальном допустимых значениях искомого пути триггеры 2 2 всех моделей ветвей в конце первого цикла работы моделирующего устройства будут находиться в единичном состоянии, а в запоминающем счет­ чике будет записано число импульсов, соответствующее максималь­ ной длине пути в мультисети. Последующие циклы выделения вет­ вей искомого пути соответствуют приведенному ранее описанию.

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

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

148

Схема регистра сдвига с электронным коммутатором выхода заданной разрядной ячейки приведена на рис. 90. Установочный код, вводимый в запоминающее устройство (ЗУ), содержит п разря­ дов при 2п >■ С, где С — число разрядов регистра сдвига.

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

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

5.6. ЗАДАЧ А КОММИВОЯЖЕРА И ЕЕ ЦИФРОВОЙ АНАЛОГ

Задачу коммивояжера можно решить методом одновремен­ ного исследования всех возможных путей, по которым может пройти коммивояжер (см. § 1.4). Этот метод предусматривает разбиение исходного города на начальный и конечный (см. рис. 3). Суть метода легко представить, рассмотрев такой наглядный пример.

Пусть из начального города ко всем другим городам выходят коммивояжеры. Когда коммивояжер приходит в і-й город, он раз­ решает выйти из этого города коммивояжерам во все другие города, за исключением конечного города. Эти коммивояжеры имеют же­ тоны, которые указывают, что они посетили t-й город. Когда какойлибо коммивояжер, имеющий жетон посещения города, придет в /-й город, он разрешает выход коммивояжеров из города во все дру­ гие. При этом последние получают жетоны, свидетельствующие о том, что их предшественник, выйдя из начального города, побывал в городах і и /. Если какой-нибудь коммивояжер имеет жетон с указанием того, что п — 2 города пройдено, то он разрешает выход коммивояжера из п — 1 города в конечный. Таким образом, пер­ вый коммивояжер, который появится в конечном городе, пройдет кратчайший путь. Порядок отметок на жетоне будет соответствовать последовательности прохождения городов коммивояжером по крат­ чайшему пути. При этом если все пути одинаковы, то число коммиво­ яжеров, прошедших т городов из всех п, определяется как число перестановок из п элементов по т, т. е.

Р п = п ( п — 1) . . . (п — т + 1 ) .

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

РІ = 9 X 8 = 72,

три города:

Рд = 9 x 8 x 7 = 504,

четыре города:

^ = 9 х 8 х 7 х 6 = 3024,

пять городов:

Рд = 9 x 8 x 7 x 6 x 5 = 1 5 120,

шесть городов:

Рд = 9 х 8 х 7 х 6 х 5 х 4 = 60 480,

семь городов:

Рд = 9 x 8 x 7 x 6 x 5 x 4 x 3 = 181 440

восемь городов:

Р |= 181440 X 2 = 362 880,

девять городов:

Рд = 362 880.

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

148

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

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

Цифровой аналог [4] состоит из моделей ветвей М В и моделей городов МГ, соединенных в соответствии с топологией задачи (рис. 91). В построении модели, так же как и в рассмотренном выше методе определения пути комми­ вояжера, предусматривается раз­ биение исходного города на на­ чальный и конечный таким об­ разом, чтобы модель начального города связывала только выхо­ дящие ветви, а модель конечного города — только входящие (см. рис. 3).

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

посылают сигналы. Они представляются /г-разрядным двоичным кодом, где п — число городов задачи коммивояжера. Импульс в первом разряде кода свидетельствует о начале сигнала (является строб-импульсом), а импульс в і-м разряде — о прохождении сигна­ ла через і-й узел.

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

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

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

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

149

последовательности прохождения городов в минимальном пути ком­

последний город, называемый на этом шаге «конечным».

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

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

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

£лз = Tltmахі/,

где п — количество городов; tmax ц — максимальная продолжитель­ ность ветви.

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

2 mntmax,

где т — номер города; п — число городов; ітах — максимальная величина длительности ветви, то совпадения сигналов окажутся

невозможными, так как

т

2 2 ' < 2 т+1. /=і

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

150

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

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

Рис. 92

Моделью ветви МВ является регулируемая линия задержки ( ЛЗ), например магнитострикционная, величина которой пропор­ циональна длине ветви.

Объем линии задержки выбирается равным

^max ' Л /,

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

триггер 7\ в единичное состояние через схему совпадения Их. При этом открывается схема И2 и на счетчик Сгі поступают импульсы от тактового генератора ГИ. Со входа модели ветви импульсы сиг­ нала поступают на схему совпадения И 3 и в распределитель им­ пульсов, который задерживает импульсы на т тактов. Когда счетчик

■ 151

С<і4 отсчитывает m импульсов, на его выходе появляется сигнал, который подается на второй вход схемы совпадения # 3. Если в этот момент в сигнале имеется признак, то схема И3 выдает импульс, перебрасывающий триггер Т2 в единичное состояние. Импульсом с единичного выхода триггера Т2 регистр сбрасывается в нулевое состояние. При отсутствии в сигнале импульса в этот момент триг­ гер Тг остается в нулевом состоянии и сигнал, пройдя через распре­ делитель, поступает в линию задержки ветви (ЛЗВ). Объем ЛЗВ должен быть

^max = и/,

где / — максимальное число, моделирующее длительность ветви.

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

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

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

Сигнал, пройдя через линию задержки ветви, первым импульсом устанавливает триггеры 7\ и Тг в единичное состояние. При этом открывается схема совпадения Иг и на счетчик Сч4 поступают им­ пульсы от генератора ГМ, а также подается с единичного выхода Т2 разрешающий потенциал на схему совпадения И3.

Импульсы сигнала поступают на схему несоответствия. На вход схемы несоответствия поступают импульсы от тактового генерато­ ра ГМ. На выходе этой схемы импульс появляется в том случае, если в каком-либо разряде сигнала нет импульса, т. е. если сигнал не прошел все города. Если сигнал прошел все п городов, то триггер Г2 остается в единичном состоянии. После поступления на вход счетчика п-то импульса на его выходе появится сигнал, который по­

152