УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА Советский патент 1968 года по МПК G06G7/122 

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

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

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

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

Исходный узел расщеплен иа начало / и конец / пути, соединенные источником тока /. Остальные (п-1) узлы (1 З...п) дублированы (п-1) раз и в них помещены источники (2, бз... е„ изменения дл-ин ветвей.

Все узлы, кроме одноименных, соединены 1между собой через модели соответствующих ветвей, иостроенные, например, ,в виде последовательно соеднненных источников напряжения EIJ н диодов Д (где г, . 2, З...п). Т. с. схема данного устройства реализует расишрсниый граф, который удовлетворяет «сходной матрице расстояний Д (с//;), , ,2,... п, причем принято: dij со прн / /.

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

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

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

I. Пе все узлы задаиного графа выходят на кратчайшие пути на расширенном графе. Ио поскольку между начальным / н конечнь / узлами содержится п .ветвей, а, следовательио, путь проходит через п узлы, на кратчайшем пути окажется несколько узлов с одним и темже номером, т. е. да1П1ый путь .не является иутем коммивояжера. Тогда на следующем этале решения увеличиваем «а одну и ту же величину длины ветвей либо входящих, либо выходящих из одного из такИХ узлов, до тех пор нока етанет невозможным дальнейшее увеличение дли« этнх ветвей без исключения данного узла из кратчайших нутей. Повторяем этот нроцесс для всех несколвко раз .выходяHJ,HX на кратчайшие лути узлов до тех пор, нока не придем к случаю, оп-исанному ниже.

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

В этом случае возможны следующие три ситуации. Среди кратчайших путей:

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

б)имеется множество пересекающихся путей, по увеличение длин ветвей либо входящих, либо выходящих «3 любого узла, который выходит на кратчайшие пути более одного раза, прИВодит к исключению этих узлов из кратчайших путей. Тогда все еетви, составляющие кратчайш-ие пути, входят и в лути коммивояжера, и любой кратчайший путь, проходящий через все узлы заданного графа, есть оптимальный путь комимивояжера;

в)имеется мно кество лересекающихся путей, но увеличение длиН ветвей либо входящих, либо выходяЩИХ из некоторых узлов, которые выходят на кратчайшие пути более одного раза, не лриводит к исключению узлов из кратчайших путей. Тогда увеличиваем длины этих ветвей, нока не придем к случаям 2, а или 2, б.

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

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

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

/кр, а длина оптимального нути коммивояжера равна LKP , то увеличение длин ветвей, выходящих из этого узла на величину Д, лриводит к увеличению указанных нутей соответственно до величин () и (кр+(), т. е. указанное выше неравенство становится именее жестким, кратчайший луть с каждым новым шагом становится ближе к оптимальному лутн коммивояжера.

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

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

оно содержит источники изменения длин ветвей, причем все узлы, кроме исходного, дублированы (п-1) раз, и дублированные узлы каждого предыдущего ряда соединены всеми ВОЗМОЖ.НЫМИ соедннениями с узлами последующего ряда через модели ветвей, исключая одноименные узлы, а узлы первого и последнего рядов соединены соответственно с начальным и конечным узлами через соответствующие модели ветвей, и во все (п-1) раз

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