Устройство для решения экстремальных комбинаторных задач Советский патент 1980 года по МПК G06G7/122 

Изобретение относится к области вычислительной техники и может быть использовано для решения задачи о назначении, задачи о коммивояжере и др. Известно моделирующее устройство для решения задачи о коммивояжере, осн ванное на цифроаналоговом методе одновременного исследования всех возможны гамильтоновых путей и использующее счетчиковые структуры j, Недостатком устройства является сложность получения решения и сложност самого устройства при большой размерности решаемых задач. Наиболее близким к предлагаемому по технической сущности является устро ство для решения задачи коммивояжера, содержащее источник напряжения, регулируемые делители напряжения, инвертирующие сумматоры и аналоговые ключи, моцели цуг, соединяющие узлы пути ком мивояжера и исходный узел, расщепленный на начальный и конечный, причем все узлы, кроме исходного, дублированы (п-1) раз (п- число узлов), и дублированные узлы каждого ряда соединены всеми возможными соединениями с узлами последующего ряда через модели дуг, исключая одноименные узлы, а узлы первого и последнего рядов соединены соот- ветстбенно с начальным и конечным узлами через соответствующие модели дуг, и во все (п-1) раз дублированные узлы помещены источники изменения длин дуг, регулируемые в процессе поиска оптимального решения 2, Многократное дублирование узлов и дуг в устройстве ограничивает возможность моделирования задач большого размера из-за быстрого роста аппаратурных затрат с увеличением числа узлов, кроме того, моделирование задач большого размера ограничено максимально допустимой величиной напряжения между начальным и конечным узлами устройства, а многократное дублирование источников изменения длин дуг, регулируемых в процессе поиска оптимального решения, влечет за 75 собой значительный рост затрат времени на поиск оптимального решения, причем, применение в моделях цуг диодов снижает точность решения задачи из-за неидеальности характеристик диодов, Цель изобретения - расширение класса решаемых задач путем увеличения мерности и повышения тоности решения. Указанная цель достигается тем, что в устройстве для решения экстремальных, комбинированных задач, содержащем источник напряжения и модели дуг графа, каждая из которых содержит регулируемый делитель напряжения, суммирующий операционный усилитель и аналоговый ключ, в каждой модели дуги, соединяющей ю вершину графа с j -ей вершиной графа, один из входов суммирующего операционного усилителя через регу лируемый делитель напряжения подключен к выходу источника напряжения, а инверсный выход суммирующего операционного усилителя через аналоговый ключ соединей с входами соответствующих суммирующих операционные усилителей моделей дуг, входящих в J - ю вершину графа, и с соответствующими входами суммирую щих операционных усилителей моделей дуг, выходящих из I -ей вершины графа. На фиг. 1 показана дуга dl, графа, соединяющая вершину графа с j -ой, и выделены все дуги графа, Кюдели которых подключаются к дуге ; на фиг. представлена мойель одной из дуг графа, Устройство содержит источник 1 напряжения, суммирующий операционный усилитель 2, регулируемый делитель 3 напряжения и аналоговый ключ 4. Инвертирующий выход операционного усилителя 2 через аналоговый ключ 4 соединен со входами операционных усилителей всех дуг, входящих в тот узел j , в который входит данная дуга dlij , и со входами операционных усилителей всех цуг, выходящих из того узла , из кото рого.выходит дуга ; соответственно вход операционного усилителя дуги Ы;; через аналоговые ключи соединен с выходами операционных усилителей всех дуг входящих в тот узел ; в которвый входи дуга и с выходами операционных уси лителей всех дуг, выходящих из того узла , из которого выходит дуга сЛ ij. Напряжение, снимаемое с регулируемо го делителя 3 напряжения, пропорциональ но длине дуги . 2 Устройство функционирует, исходя из ледующей постановки задачи о коммивояжере. Необходимо на полном графе баз пе- . тель, заданном узлами и матрицей расстояний между ними, отыркать гамильтоновый цикл (цикл, проходящий через все злы граф по одному разу) минимальной длины, т. е. исходный граф следует дополнить до полного симметрического. В устройстве после одновременного замыкания аналоговых ключей образуются положительные обратные связи, что обуславливает возникновение лаэинооб- разного процесса опрокидывания в одно из возможных устойчивых состояний. Каждое из устойчивых состояний устройства соответствуетконтуру обхода всех узлов Ърафа, при условии про- хождения через каждый узел только один раз, т. е. удовлетворяет условиям задачи о назначении. Направление развития лавинообразного процесса опрокидывания определяется суммой напряжений, существующих на входах операционных усилителей в момент времени, предшествующий началу лавинообразного процесса, и соответствует оптимальному контуру обхода узлов графа, что следует из выражения (1), определяющего суммарное напряжение на входах суммирующих операционных усилителей дуг, образующих возможный контур обхода узлов графа, т. е. контур, удовлетворяющий условиям задачи о назначении:iu.. a(u..-iU;..--s d.. ( J n J nJ пок-oMv KOMTVPv контуру I где UlpUii - напряжения соответственно на выходе и входе усилителя - в момент времени, предшествующий началу лавинообразного процесса; . - напряжение, снимаемое со среднего вывода регулируемого делителя напряжения дуги сэ(у ; П - число узлов графа; К - индекс разрешенного контура, т. е. контура, удовлетворяющего условиям задачи о назначении. Устойчивое состояние устройства характеризуется тем, что на выходах тл операционных усилителей дуг, образующик оптимальный контур, образуются напряжения , определяемые амп литудой- карактаристикой операционного усилителя, и на выходах остальных операционных усилителей дуг образуются напряжения-VJj Q, , причем для значений выходных напряжений в устойчивом состоянии выполняется условие ., где Z - отношение числа дуг, входящи в разрешенный контур, к числу дуг, не входящих в разрешенный контур. , операционные усилители кото рых в устойчивом состоянии имеют на выходах напряжения - Upncn определяют решение задачи о назначении. При этом возможны две ситуации: 1.Полученный контур является гамил тоновым, т. е. решение удовлетворяет условиям задачи о назначении и задачи о коммивояжере. 2.Полученный контур является нега- мильтоновым, т. е. решение удовлетворяет только условию задачи о назначении. Во второй ситуации для решения зада чи о коммивояжере можно вюспользовагь ся одним из известных способов отыскания оптимального гамильтонова контура на основе имеющегося решения задачи о назначении. Причем под негамильтоновым контуро будем понимать контур, не удовлетворяю щий условию циклической перестановки, характеризующей рассматриваемый контур. Если под гамильтоновым контуром понимается такой путь, когда коммивояжер, побывав в каждом городе, возвращается обратно в исходный , то не- гамильтоновым контуром называется ана логовый путь, но разбитый на несколько подциклов. При анализе работы устройства удобно рассматривать его как симметричное устройство со многими устойчивыми состояниями и провести аналогию с обычным симметричным триггером, имеющим два устойчивых состояния. Если в триггере обратные связи обуславливают два возможных устойчивых состояния, причем открытое состояние осшого плеча триггера автоматически влечет за собой закрытое состояние другого плеча, то в предлагаемом устройстве обратные связи обеспечивают закрытие всех входящих в узел дуг, кроме одной, и всех выходящих из узла дуг, кроме одной. Закрытым условно называем такое состояние дуги. 026 когда на выходе операционного усилителя, моделируемого данную дугу, образуется напряжение -Upr,o,. Открытым - когда на выходе операционного усилителя образуется напряжение . Как в триг гере не возможно состояние с двумя -открытыми или двумя закрытыми плечами, так и в предлагаемом устройстве не возможны состояния с числом входящих узел и выходящих из узла дуг 1. Такое свойство устройства равнозначно условиям задачи о назначении, а в частном случае устойчивое состояние может также удовлетворить условие цикличности и тем самым условию задачи о коммивояжере. Благодаря введению новых связей повысилась точность решения, снизились аппаратурные затраты и появилась -возможность расширить класс решаемых задач за счет увеличения размерности решаемых задач по сравнению с возможностями известных решений. Формула изобретения Устройство для решения экстремальных комбинаторных задач, содержащее источник напряжения и модули дуг графа , каждая из которых содержит регулируемый делитель напряжения, суммирующий операционный усилитель и аналоговый ключ, отличающееся тем, что, с целью расширения класса решаемых задач путем увеличения мерности и повышения точности решения, в каждой модели дуги, соединяющей -ю вершину графа с j -ой вершиной графа, один из входов суммирующего операционного усилителя через регулируемый делитель напряжения подключен к выходу источника напряжения, а инверсный выход суммирующего операционного усилителя через аналоговый ключ соединен с входами соответствующих суммирующих операционных усилителей моделей дуг, входящих в j -ю вершину графа, и с соответству- тощими входами суммирующих операционных усилителей моделей дуг, выходящих из -ой вершины графа. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР 227716, кл. G 06 G 7/122, 1967. 2,Авторское свидетельство СССР 2319ОЗ, кл. G Об G 7/122, 1967 прототип).