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

Шуе./

J1716548

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

Известно устройство для решения задачи о коммивояжере по авт. св. СССР-К 231903, содержащее модели дуг и источники изменения длин дуг. Моделирование задач большого размера с jg помощью этого устройства ограничено максимально допустимой величиной напряжения между начальньм и конечным узлами устройства, необходимость ремый делитель напряжения, суммирующи операционный усилитель и аналоговый ключ, причем в каждой модели дуги, соединяющей i-й узел графа с j-м уз лом графа, один из входов суммирующего операционного усилителя.через регулируемый делитель напряжения под ключен к выходу источника напряжени а инверсный выход суммирующего уси лителя через аналоговый ключ соедин с входами суммирующих операционных усилителей моделей дуг, входящих в j-й узел.графа, и с входами суммирую

гулирования источников изменения длин щих операционных усилителей моделей

дуг, выходящих из 1-го узла графа, введены по n-З дополнительных модел дуг для всех дуг, кроме дуг, входящи в первый и выходящих из первого узла графа, причем инверсный выход суммирующего операционного усилителя k-й модели дуги, соединяющей i-й узел графа с j-м узлом графа, через анало говый ключ соединен с тремя входами суммирующих операционных усилителей k-x моделей дуг графа, выходящих из 1-го узла или входящих в j-й узел, с двумя входами суммирующих операционных усилителей k-x модулей дуг графа входящих в i-й узел или выходящих из j-ro узла, с одним входом суммирующи операционных усилителей остальных kмоделей дуг графа, с двумя входами суммирующих операционных усилителей (k-1)-x моделей дуг графа, не входя- 35 щих в i-й узел и выходящих из 1-го или из j-ro узла или входящих в j-й узел, с одним входом суммирующих опе рационных усилителей остальных (k-l) моделей дуг графа, не входящих в i-й узел, с двумя входами суммирующих операционных усилителей (k+1)-x моде лей дуг графа, не выходящих из j-ro узла и входящих в i-й или в j-й узел или выходящих из j-ro узла, с одним входом Суммирующих операционных усилителей остальных (k+1)-x моделей ду графа, не выходящих из j-ro узла, с одним входом суммирующих операционны

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

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

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

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

0

5

0

дуг, выходящих из 1-го узла графа, введены по n-З дополнительных моделей дуг для всех дуг, кроме дуг, входящих в первый и выходящих из первого узла графа, причем инверсный выход суммирующего операционного усилителя k-й модели дуги, соединяющей i-й узел графа с j-м узлом графа, через аналоговый ключ соединен с тремя входами суммирующих операционных усилителей k-x моделей дуг графа, выходящих из 1-го узла или входящих в j-й узел, с двумя входами суммирующих операционных усилителей k-x модулей дуг графа, входящих в i-й узел или выходящих из j-ro узла, с одним входом суммирующих операционных усилителей остальных kx моделей дуг графа, с двумя входами суммирующих операционных усилителей (k-1)-x моделей дуг графа, не входя- 5 щих в i-й узел и выходящих из 1-го или из j-ro узла или входящих в j-й узел, с одним входом суммирующих операционных усилителей остальных (k-l)-x моделей дуг графа, не входящих в i-й узел, с двумя входами суммирующих операционных усилителей (k+1)-x моделей дуг графа, не выходящих из j-ro узла и входящих в i-й или в j-й узел или выходящих из j-ro узла, с одним входом Суммирующих операционных усилителей остальных (k+1)-x моделей дуг графа, не выходящих из j-ro узла, с одним входом суммирующих операционных

усилителей 1,2,...,(fc-2),(k+2)

n-1, n-х моделей дуг, входящих в 1-й или j-й узлы графа и выходящих из 1-го или j-ro узлов графа.

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

5

0

5

10

15

20

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

На фиг.1 представлена модель d-jv-й дуги графа, которая, как и в прототипе, содержит источник 1 напряжения, суммирующий операционный усилитель 2, делитель 3 напряжения и аналоговый ключ 4$

Инвертирующий выход операционного усилителя 2 через аналоговый ключ 4 соединен с входами соответствующих операционных усилителей. Напряжение снимаемое с регулируемого делителя 3 напряжения, пропорционально длине дуги d.;{ .

На фиг. 2 показан фрагмент графа, содержащий дугу d; и дуги, модели которых не имеют непосредственных

связей с моделью дуги d;: .

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

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

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

35

40

45

-JQ

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

5

0

5

5

0

5

0

тур, удовлетворяющий условиям задачи о коммивояжере

2

U

Ч

по п-му

контуру

где U. , О,1,

Sdi, (D

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

п тп

напряжение, снимаемое со среднего вывода ре-1- гулируемого делителя напряжения дуги| число узлов графа , индекс разрешенного контура, т.е. контура, удовлетворяющего условиям задачи о коммивояжере.

Устойчивое состояние устройства характеризуется тем, что на выходах п операционных усилителей дуг, образующих оптимальный контур$ образуются Q напряжения +UwaKC, определяемые амплитудной характеристикой усилителя, и на выходах остальных операционных усилителей дуг образуются напряжения -UAAAKC причем для значений выходных напряжений в устойчивом состоянии выполняется условие

z|+UMQKC p I -UMQKC I

где z - отношение числа дуг, входящих в разрешенный контур, к числу дуг, не входящих в разрешенный контур. Дуги, операционные усилители которых в устойчивом состоянии имеют на выходах напряжение .,;, определяют решение задачи о коммивояжере.

Анализ работы устройства аналоги-v чен приведенному в прототипе.

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

55 ь о

р м у л а

изобретения

Устройство для решения экстремальных комбинаторных задач, содержащее источник напряжения и модели дуг графа каждая из которых содержит регулируемый делитель напряжения, суммирующий операционный усилитель и аналоговый ключ, причем в каждой модели дуги, соединяющий i-й узел графа с j-м узлом графа(i 1,2,..., N; j 1, 2,..., М, где N - количество узлов в графе4, М - индекс разрешенного контура в пути коммивояжера), один из входов суммирующего операционного усилителя -через регулируемый делитель напряжения подключен к входу источника напряжения, а инверсный выход суммирующего операционного усилителя через аналоговый ключ соединен с входами суммирующих операционных усилителей моделей дуг, входящих в j-й узел графа, и с входами суммирующих операционных усилителей моделей дуг, выходящих из 1-го узла графа, о т л и - чающее с я тем, что, с целью расширения функциональных возможностей устройства за счет решения задачи коммивояжера, в него введены дополнительные модели дуг, соединенные в соответствии с деревом возможных путей коммивояжера, причем инверсный выход суммирующего операционного усилителя k-й модели дуги, соединяющей i-й узел графа с j-м узлом графа (k 1, 2,..., N), соединен через аналоговый ключ с тремя входами суммирующих операционных усилителей k-x моделей дуг, соответствующих дугам, выходящим из 1-го или входящим в j-й узел графа, с дву-,

мя входами суммирующих операционных усилителей k-x моделей дуг,соответствующих дугам, входящим в i-й узел или выходящим из j -го узла графа, с одним входом суммирующих операционных усилителей

остальных k-x моделей ду г, с двумя входами суммирующих операционных усилителей (k-1)-x моделей дуг, соответствующих дугам, не входящим в i-й и выходящим из 1-го или из j-ro или входящим в

Узел графа, с одним входом суммирующих операционных усилителей остальных (k-l)-x моделей дуг, соответствующих дугам, не входящим в 1-й узел, с двумя входами суммирующих операционных усилителей (k+1)-x моделей дуг, соответствующих дугам, не выходящим из i-ro узла и входящим в i-й или в j-й или выходящим из 1-го узла графа, с одним входом суммирующих операционных усилителей остальных (k+1)-x моделей дуг, соответствующих дугам, не выходящим из j-ro узла, с одним входом суммирующих операционных усилителей 1, 2,..., (k-2), (k+2),

Q ..., N-1, N-x моделей дуг, соответствующих дугам, входящим в i-й или j-й узлы графа и выходящим из 1-го или 1-го узлбв графа.

0

5

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

-CVJ

/л

у.