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

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

Иллюстрации

Показать все

Реферат

 

" +++ OIQ3klga - . т нтно т,:,,и.

О П И С"А"Н И Е

23! 903

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

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

Республик

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Зависимое от авт. свидетельства М

Кл. 42m, 7/48

Заявлено 05Х1.1967 (1т1е е1164426/18-24) с присоединением заявки М

Приоритет

Комитет по валам изсоретений и аткрм1ий

МПК G 060

Ъ ДК 681.333(088.8) при Совете Министров

СССР

Опубликовано 28.Х1.1968. Бюллетень Хо 36

Дата опубликования описаштя 7Л .1969

Автор изобретения

Заявители

Г. К. Шарашидзе

Институт кибернетики АН Украинской ССР и Вычислительный центр

АН Грузинской ССР

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯ)КЕРА

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

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

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

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

На чертеже дана схема устройства для решения задачи,коммивояи ера.

Исходный узел расщеплен на начало 1 конец 1" пути, сосдиненныс источштком тока I.

Остальные (n — 1) узлы (2, 8... 22) дублнрованы (22 — 1) раз н в них помещены источники е2, ез... е„изменения длин ветвей.

Все узлы, кроме одноименных, соединены между собой через модели соответствующих ветвей, построенные, например,,в виде последовательно соединенных источников напряже10 ния Е,, и диодов Д (где i, j=1, 2, 3... n). Т. с. схема данного устройства реализует расширснный граф, который удовлетворя T исходной матрице расстояний Д = (d;i), i, j=1,2,... и, причем принято: d; = о при i = j.

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

Задача определения пути комм1гвояжера сводится к задаче определения кратчайшего

20 пути между узлами I и !" на расширенном графе.

При этом возможны следующие два случая:

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

25 поскольку между начальным 1 и конечным 1" узлами содержится 22.ветве11, а, следовательно, путь проходит через п узлы, на кратчайшем пути окажется несколько узлов с одним и тсмже номером, т. е. данный п ть нс является п 30 тем коммивояжера. Тогда на следу1ощем этапе решения увеличиваем на одну и ту же величину длины ветвей либо входящих, либо выходящих из одного из таких узлов, до тех пор пока станет невозможным дальнейшее увеличение длин этих ветвей без исключения данного узла из кратчайших путей. Повторяем этот процесс для всех несколько раз выходящих на кратчайшие пути узлов до тех пор, пока не придем к случаю, описанному ниже.

II. Все узлы заданного графа выходят на кратчайшие пути на расширенном графе.

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

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

Следует отметить, что увеличение на одну и ту же величину длин ветвей, входящих либо выходящих из кратных узлов, iHc изменяет исходной задачи, так как все пути коммивояжера изменяются при этом на одну и ту же величину и, следовательно, оптимальный путь коммивояжера останется по-прежнему оптимальным. Процесс же отыскания оптимально10 пути коммивояжера по .п, 1 сходится, так как, во-первых, искомый путь коммивояжера всегда ограничен: снизу — кратчайшим путем сети, представленной расширенным графом, не являющимся путем коммивояжера, и сверху — длиннейшим путем указанной сети, И, 10 во-вторых, искусственно вводимое увеличение длин ветвей вызывает сближение длины крагчайшего пути полученной сети, не являющегося путем коммивояжера, с длиной пути коммивояжера. Так, если длина кратчайшего пу15 ти, в который 1-тый узел входит k раз, равна

l,ð, а длина оптимального пути коммивояжера равна 1.,|, и l ð(l.,ð, то увеличение длин ветвей, выходящих из этого узла на величи20 пу А,, приводит к увеличению указанных путей соответственно до величин (/„р+k Л1) и (А„р+Л;), т. е. указанное выше нера,венство становится менее жестким, кратчайший путь с каждьв| новым шагом становится ближе к оптималь ному пути коммивояжера.

Предмет изобретения

Устройство для решения задачи коммивоя30 жера, содержащее модели ветвей, соеди няющие узлы пути коммивояжера и исходный узел, расщепленный на начальный и конеч11ы11, отличающееся тем, что, с целью упрощения задачи определения оптимального пути, 35 оно содержит источники изменения длин вет,вей, причем все узлы, кроме исходного, дублированы (n — 1) раз, и дублированные узлы каждого предыдущего ряда соединены всеми

Возмо>1ы(ыми соединениями с $3ëÿìH последу40 ющего ряда через модели, ветвей, исключая одноименные узлы, а узлы первого и последнего рядов соединены соответственно с начальным и конечным узлами через соответствующие модели ветвей, и во все (n — 1) ра;

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

231903

Составитель Л. Б. Дмитриева

Техрсд Т. П. Курилко Корректор А. П. Татаринцева

Редактор П, Шлайн

Типография, пр. Сапунова, 2

Заказ 363120 Тираж 530 Подписное

ЦИИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

Москва, Центр, пр. Серова, д, 4