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

Исходя из этого, естественно предложить в качестве модели уз­ ла логическую схему дизъюнкции ИЛИ (рис. 49). Аналогией дли­ тельности ветви могут служить временные соотношения.

Известны [191] модели, в которых используются временные со­ отношения в процессе моделирования. В модели задачи о кратчай­ шем пути в качестве ветвей используется реле времени, которое пос­ ле прихода сигнала через установленное время задержки выдает сигнал. Этот сигнал применяется для запуска других реле, модели­

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

Рис. 50

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

Рассмотрим цифровой аналог задачи о кратчайшем пути, по­ строенный на базе элементов цифровой техники. Такой аналог для решения задачи кратчайшего пути состоит из моделей ветвей и моде­ лей узлов. Модели ветвей и узлов соединяются между собой в соот­ ветствии с топологией сети. На рис. 50 приведен пример сети и ее цифрового аналога.

Для определения длины кратчайшего пути между начальными и

50

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

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

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

пульсов, пропорциональное длине ветви. В таком цифровом анало­ ге основным элементом моделей ветвей является схема отсчета коли­ чества импульсов, пропорционального продолжительности ветви (рис. 52). Схема отсчета состоит из триггера Т, схемы совпадения И и «-разрядного счетчика. Количество разрядов счетчика выбира­ ется в зависимости от необходимой точности получения результатов решения.

91

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

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

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

закрывает схему И.

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

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

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

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

92

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

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

Рис. 54

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

Счетчик Сч2 выполняет функции регенерации информации, за­ писанной в счетчики Счх.

Для индикации ветвей, принадлежащих кратчайшему пути, не­

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

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

93

ва является высокая точность определения кратчайшего пути и уста­ новки исходных данных.

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

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

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

5.2. ЦИФРОВОЙ АНАЛОГ ЗАДАЧ

ОДЛИННЕЙШЕМ ПУТИ

Вобщем случае задача о длиннейшем пути для двуна­

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

Однако задачу о длиннейшем пути для двунаправленного графа можно сформулировать аналогично задаче коммивояжера, т. е. определить в двунаправленном графе длиннейший путь такой, что он содержит каждый узел не более одного раза. При данной поста­ новке задача о длиннейшем пути оказывается аналогичной длин­ нейшему пути Гамильтона для заданного множества ветвей. Реше­ ние этой задачи можно найти методом одновременного просмотра всех путей (см. § 1.4). Используя указанный метод, можно постро­ ить цифровой аналог, подобный цифровому аналогу для решения задачи коммивояжера; подробнее он описан ниже (см. § 5.6). Здесь только укажем, что для определения длиннейшего пути необходимо в конечном узле предусмотреть устройство, позволяющее найти ту ветвь, по которой пришел последний сигнал в конечный узел. При этом максимальное время определения конфигурации длиннейше­ го пути в двунаправленном графе для такого цифрового аналога будет

i n - 2) (л*™» Ѣ 2 4 t j j

tD<

fr

где tmах — число импульсов, пропорциональное максимальной дли­ не одной ветви; іл.„ — число импульсов, пропорциональное длин­ нейшему пути; п — число узлов; /V — частота тактового генератора.

94