Устройство для решения задачи коммивояжера

23 903 Союз Советскиз Социалистических Республик. свг Кл, 4 Заявлено 05."т 1.1967 (Уе 1164426/18-2с присоединением заявки М Комитет по аеламобретений и аткрвн ийри Совете Министров МПК 6 риоритет Опубликовано 28.Х Дата опубликовани 68. Бюллетень Ле описания 7 Л.1969 681.333 (088.8 АвторизобретениЗаявители Г. К. Шарашидзе Украинской ССР и ВычиАН Грузинской ССР тельный цент ститут кибернетики УСТРОЙСТ РЕШЕНИЯ ЗАДАЧИ И ВОЯЖЕРА Известны устроиства для решения задачи коммивояжера, содержащие модели ветвей, соединяющие узлы пути коммивояжера и исходный узел, расщепленный на начальный и конечный,Предлагаемое устройство отличается от известных тем, что содержит источники изменения длин ветвей. При этом все узлы, кроме исходного, дублированы (гг - 1) раз, и дублированные узлы каждого предыдущего ряда соединены, всеми, возможными соединениями с узлами последующего ряда через модели вегвей, исключая одноименные узлы. Узлы первого и последнего рядов соединены соответственно с начальным и конечным узлами через соответствующие модели ветвей, и во все (п - 1) раз дублированные узлы также помещены источники изменения длин ветвей, регулируемые в процессе поиска оптимального решения,Такое выполнение устройства позволяет упростить решение задачи,В задаче коммивояжера задается граф, состоящий из и узлов и ветвей, соединяющих эти узлы. На таком графе нужно определить контур гминибгальной длины, проходящий через все узлы заданного графа и посещающий каж дый узел не более одного раза.На чертеже дана схема устройства для решения задачи,кохгхвивоякера. Р 1 сходггый узел расщеплен ца началоконец 1" пути, соединенныс источником тока.Остальные (гг - 1) узлы (г, д п) дублцрованы (гг - 1) раз и в них помещены источники е 2, ез еизменения длин ветвей.Все узлы, кроме одноименных, соединенымежду собой через модели соответствующих ветвей, построенные, цапримерв виде последовательно соединенных источников напряже ция Ег и диодов Д (где г,= 1, 2, 3 п). Т. с,схема данного устройства реализует расширснцый граф, который удовлетворяет исходной матрице расстояний Д = (гуг), г, = 1, 2,п, причем принято: гуг = -с при г=.15 Схема х стройства содержит также ицдцка.ционное устройство г, топологически повторяющее модель .И расширенного графа.Задача определения пути коммивояжерасводится к задаче определения кратчайшего 20 пути между узламиица расширенномграфе.При этом возможны следующие два случая: 1. Не все узлы заданного графа выходят цакратчайшие пути на расширенном графе. Но 25 поскольку между начальным 1 и конечным "узлами содержится п ветвей, а, следовательно, путь проходит через п узлы, на кратчайшем пути окажется несколько узлов с одам и темже номером, т. е. данный ить нс является пу тем коммивояжера. Тогда на следугощегм эта.пе решения увеличиваем на одну и ту же величину длины ветвей либо входящих, либо выходящих из одного из таких узлов, до тех пор пока станет невозможным дальнейшее увеличение длин этих ветвей без исключения данного узла из кратчайших путей. Повторяем этот процесс для всех несколько раз выходя. щих на кратчайшие пути узлов до тех пор, пока не придем к случаю, описанному ниже.11. Все узлы заданного графа выходят на кратчайшие пути на расширенном графе,В этом случае возможны следующие три ситуации. Среди кра гчайших путей:а) имеются непересекающиеся пути коммивояжера, т, е. все кратчайшие пути есть пути коммивояжера, либо кратчай 1 ций путь есть путь коммивояжера, что соответствует решению задачи;б) имеется множество пересекающихся путей, но увеличение длин ветвей либо входящих, либо выходящих из любого узла, который выходит на кратчайшие пути более одного раза, приводит к исключению этих узлов из кратчайших путей. Тогда,все ветви, составляющие кратчайшие пути, входят и в пути коммивояжера, и любой кратчайший путь, проходящий через все узлы заданного графа, есть оптимальный путь коммивояжера)в) имеется множество пересекающихся путей, но увеличение длин ветвей либо входящих, либо выходящих из некоторых узлов, которые,выходят на кратчайшие пути более одного раза, не,приводит к исключению узлов из кратчайших путей. Тогда увеличиваем длины этих ветвей, пока не придем к случаям 2, а или 2,6.Увеличение длин ветвей либо входящих, либо выходящих из некоторого дублированного узла в устройстве производится одновременным увеличением всех напряжения Ег источников, включенных,в одноименные дублированные узлы.Следует отметить, что увеличение на одну и ту же величину длин ветвей, входящих либо выходящих из кратных узлов, не изменяет исходной задачи, так как все пути коммивояжера изменяются при этом на одну и ту же величину и, следовательно, оптимальный путь коммивояжера останется по-прежнему оптимальным, Процесс же отыскания оптимального пути коммивояжера по п, 1 сходится, так 5 как, во-первых, искомый путь коммивояжеравсегда ограничен: снизу - кратчайшим путем сети, представленной расширенным графом, не являющимся путем коммивояжера, и сверху - длиннейшим путем указанной сети, И, 10 во-вторых, искусственно вводимое увеличениедлин ветвей вызывает сближение длины крагчайшего пути полученной сети, не являющегося путем коммивоякера, с длиной пути коммивояжера. Так, если длина кратчайшего пу ти, в который г-тый узел входит 7 г раз, равна1,р, а длина оптимального пути коммивояжера равна 1.,г, и 7 р ( Ер, то увеличение длин ветвей, выходящих из этого узла на величи,пу Ьг, приводит к увеличению указанных путей соответственно до величин (1 р +Й Лг) и (У.р+Лг), т. е. указанное выше неравенство становится менее жестким, кратчайший путь с какдыгя новым шагом становится ближе к оптимальному пути коммивояжера. Предмет изобретенияУстройство для решения задачи коммивоя.ЗО жера, содержащее модели ветвей, соединяющие узлы пути коммивояжера и исходныйузел, расщепленный на начальный и конечный, отличающееся тем, что, с целью упрощения задачи определения оптимального пути,35 оно содержит источники изменения длин вет,вей, причем все узлы, кроме исходного, дублированы (тг - 1) раз, и дублированные узлыкаждого предыдущего ряда соединены всемивозможными содиеи с узми посду 40 ющего ряда через модели, ветвей, исключаяодноименные узлы, а узлы первого и последнего рядов соединены соответственно с начальным и конечным узлами через соответствующие модели ветвей, и во все (гг - 1) раз45 дублированные узлы помещены источштки изменения длин ветвей, регулируемые в процессе поиска оптимального решения,231903 Составитель Л. Б. ДмитриеваТехрсд Т. П. Курилко Корректор А. П. Татаринцева Редактор П, Шлайн Типография, пр, Сапунова, 2 Заказ 36320 Тираж 530 ПодписноеЦИИИПИ Комитета по делам изобретений и открытий при Совете Министров СССРМосква, Центр, пр. Серова, д, 4