Устройство для решения экстремальных комбинаторных задач

 

Союз Советских

Социалистических

Республик

О П И С А Н И Е () 750502

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (6! ) Дополнительное к ивт. сеид-ву— (22) Заявлено 20.03.78 (21) 259 2268/18-24 с с присоединением заявки.%(23) Приоритет— (51) M. Кл.

6 06 G 7/122

Государственный комитет

Опубликовано 23.07.80. Бюллетень №27 (53) УДК 681,333 (088.8) по делам изобретений и открытий

Дата опубликования описания 28.07.80 (72) Авторы изобретения

Ю. М. Бастриков, Л, И. Гутенмахер и В, С,.Янина

Одесский ордена Труцового Красного Знамени политехнический институт (71) Заявитель (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЭКСТРЕМАЛЬНЫХ

КОМ БИНАТОР1-{ЫХ ЗАДАЧ

Изобретение относится к области вычислительной техники и может быть использовано для решения задачи о назначении, задачи о коммивояжере и др.

Известно моделирующее устройство для решения задачи о коммивояжере, осно5 ванное на цифроаналоговом методе одновременного исследования всех возможных гамильтоновых путей. и использующее счетчиковые структуры )1j.

l0

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

Наиболее близким к предлагаемому

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

2 (П-1) раз (о- число узлов), и дублированные узлы каждого ряда соединены всеми возможными соединениями с узлами послецующего ряца через модели дуг, исключая одноименные узлы, а узлы первого и последнего рядов соединены соответстВенно с начальным и конечным узлами через соответствующие модели цуг, и во все (n-1) раз дублированные узлы помещены источники изменения длин дуг, регулируемые в процессе поиска оптимального решения (2).

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

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

Цель изобретения — расширение класса решаемых задач путем увеличения мерности и повышения тоности решения.

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

На фиг. 1 показана дуга ol; графа, соединяющая 1-д> вершину графа с j -ой, и выделены все дуги графа, Модели которых подключаются к дуге Д; ; на фиг. 2 представлена модель одной из дуг графа, Устройство содержит источник 1 напряжения, суммирующий операционный усилитель 2, регулируемый делитель 3 напряжения и аналоговый ключ 4.

02 ф

Уст ройс f во функционирует, ис ходя из следующей постановки задачи о коммивояжере.

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

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

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

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

gg.,=, (Q,. -7 — XU - .ЕО; - Е (;

КОЙтмРУ KOstYPY

Инвертирующий выход операционного усилителя 2 через аналоговый ключ 4 соединен со входами операционных усилителей всех дуг, входящих в тот узел в который входит данная дуга d;>, и со 4S входами операционных усилителей всех дуг, выходящих из того узла 1, из которого .выходит дуга Ы;, соответственно вход операционного усилителя дуги с ; через аналоговые ключи соединен с выходами операционных усилителей всех дуг, входящих в тот узел ; в которвый входит дуга d j и с выходами операционных усилителей всех дуг, выходящих из того узла, из которого выходит myra cilia>. и

Напряжение, снимаемое с регулируемого делителя 3 напряжения. пропорционально длине дуги б . где 0" Ц" - напряжения соответственiji lj но на выходе и входе усилителя $.". в момент вре)i мени, предшествующий началу лавинообразного процесса; Я вЂ” напряжение, снимаемое со среднего вывода регулируемого делителя напряжения дуги (Я, и - число узлов графа;

К вЂ” индекс разрешенного кон« тура, т, е. контура, удовлетворяющего условиям задачи о назначении.

Устойчивое состояние устройства характеризуется тем, что на выходах и операционных усилителей дуг, образуюкогда на выкоде операционного усилителя, моделируемого данную дугу, образуется напряжение — lJ - Открытым — когда на выходе операционного усилителя образуется напряжение +U Как в триггере не возможно состояние с двумя.открытыми или двумя закрытыми плечами, TBK и в предлагаемом устройстве не возможны состояния с числом входящих узел и выходящих из узла дуг > 1. Такое свойство устройства равнозначно условиям задачи о назначении, а в частном случае устойчивое состояние может также удовлетворить условие цикличности и тем самым условию задачи о коммивояжере.

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

Формула изобретения

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

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

М 227716, кл. G 06 G 7/122, 1967.

2. Авторское свидетельство СССР

M 231903, кл. G 06 G 7/122, 1967 (прототип) .

5 750502 б щих оптимальный контур, образуются напряжения 1 О,, определяемые амплитудой. характеристикой операционного усилителя, и на выходах остальных операционных усилителей дуг образуются напряжения-0, причем для значений выходных напряжений в устойчивом состоянии выполняется условие 1+ц,„о1„ -о где Z — отношение числа дуг, входящих в разрешенный контур, к числу дуг, не входящих в разрешенный контур.

Дуги, операционные усилители которых в устойчивом состоянии имеют на выхода к напряжения + U„„определяют

15 решение задачи о назначении.

При этом возможны две ситуации:

1. Полученный контур является гамильтоновым, т. е. решение удовлетворяет условиям задачи о назначении и задачи о коммивояжере.

2. Полученный контур является нега.мильтоновым, т. е. решение удовлетворяет только условию задачи о назначении.

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

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

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

55 узел дуг, кроме одной, и всех выходящих из узла дуг, кроме одной. Закрытым усI л овно называем такое сост оян ие ду ги, 750502

I

4у

Заказ 4468/19 Тираж 751 Подписное

UHHHIIH Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент, r. Ужгород, ул. Проектная, 4

Составитель А. Линков

Редактор B. Зарванская Текред Л. Теслюк Корректор Г. Решетняк