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

 

Союз Советсини

Соцмалистичесини

Респубиии

О П И С А Н И Е (i)932505

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (6I ) Дополнительное к авт. свил-ву (22) Заивлено 11 ..07.80 (2! ) 2955030/18-24 с присоединением заявки,% (51) М. К и.

G 06 G 7/122

РВударатиеа11 квмитет СССР па делам иааеретени11 и аткрмти11 (23) Приоритет (53) УДК 681.333 (088. 8) Опубликовано 30.05.82. Бюллетень № 20

Дата опубликования описания 30 ° 05. 82. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ

О КОИМИВОЯЖЕРЕ

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

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

Недостатками такой модели являются черезвычайная сложность ее реализации и необходимость проведения (n-2) повторных решений для получения маршрута коммивояжера.

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

НЕдостатками известного устройS ства являются требование точной установки равенства значений токов в уз- лах модели, большой объем аппаратуры (при числе узлов п число источников напряжений равно, а исп(в- 1

10 точников тока — n) возможность образования неполных циклов, т. е. таких решений задачи, при которых путь коммивояжера не будет проходить

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

Црль изобретения — повышение точиости решения задачи.

32505 4 элементов определяет в некотором масштабе длину моделируемой ветви.

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

Допустим также, что в любой момент

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

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

Тогда напряжение пробой в любом 1 -м полном контуре определится как 1 К = " 3OHC+ l ) Г где К вЂ” суммарное количество газоразрядных приборов, включенных

2S в ветвях 1 --го полного контура

Очевидно, что при плавном изменении g Е„ первым пробьется контур, отвечающий условию К=п 1п,. что соответствует решению задачи коммивояжера.

Действительно, учитывая, что

K=E а,.=Е $" =а п, (g}

ЗО

3 9

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

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

его выходом.

На чертеже представлена ахема предгагаемого устройства.

Устройство содержит модели узлов, 1-4 транспортной сети, причем 5-8выходы моделей узлов, 9-12 — входы моделей узлов, разделительные диоды 13, регулируемые источники 14 напряжений, ограничительные резисторы 15, модели 16 (длины) ветвей в виде последовательно включенных элементов с падающим участком вольтамперной характеристики, зашунтированных цепочками из последовательно включенных конденсатора и резистора.

Работа схемы протекает следующим образом.

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

Для индикации маршрута движения в каждую ветвь может быть включен индикатор тока.

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

t 1ц1 «1) где 1, m<1 — соответственно длина

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

Z.Å„=0„пип включается контур, являющийся pemeкием задачи коммивояжера согласно формулы 2 1 .

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

Учитывая, что суммарная ЗДС в полном контуре Е =пЕ, где Š— ЭДС

1 регулируемого источника в одном узле, а в неполном контуре g E= (и -g) Е где 1 > и"2, где / — целое число, условие образования только полного контура запишется в виде 9325 пЕ; (n g)E„

8 к-1 8+6-1 (A) где

"заис

О„

Неравенство (5) удовлетворяется при

S> — к- — 6+5, (5) и-g

7 10 что определяет требования к характеристикам нелинейных элементов, используемых для решения задачи коммивояжера в сети заданного объема и длин ветвей.

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

Формула изобретения

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

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

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

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

Ф 230527, кл. G 06 G 7/122, 1967.

2. Моделирование задач исследования операций. Под ред. Витенберга.

М., "Энергия" 1978, с. 143 (прототип).

932505

Составитель И.Лебедев

Редактор М,Ткач Техред 3. Фанта Корректор М.Коста

Заказ 3786 70 Тираж 732 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

I/3035, Иосква, Ж-35, Раушская наб., д. 4/5

Филиал ППП Патент, г, Ужгород, ул. Проектная, 4