Аналоговая модель решения задачи о коммивояжере

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

Софивлиетиивеиик

Реелублии ((()930323 (61) Дополнительное к авт. свид-ву (22) Заявлено 23. 05. 80 (21) 2931528/18-24 (51 )h%. Кл.

6 06 G 7/122 с присоединением заявки J4(23) 9вулареткеиаВ кеиятат

CCCP в Звал юокретевя1 н вткрытяя

Приоритет

Опубли",овано 23. 05.82 Бюллетень М 19 (53) УДК681.333 . (088. 8) Дата опубликования описания 23 . 05 .82 (72) Автор изобретения

Л.Ф. Федотов (71) Заявитель

Киевский автомобильно-дорожный институт им. 60-летия

Великой Октябрьской социалистической революции (54) АНАЛОГОВАЯ МОДЕЛЬ РЕШЕНИЯ ЗАДАЧИ

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

Изобретение относится к аналоговому моделированию и предназначено для . решения задачи о коммивояжере.

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

Однако известное устройство сложно по конструкции.

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

Недостатком известного устройства является то, что все узлы, кроме исходного, дублированы (n- 1) раз.

Это приводит к большому количеству используемых элементов для решения

:задачи.

Цель изобретения — упрощение устройства.

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

930323

A - lij aEij, где l i j - длина ветвей;

- номер узла начала ветви;

j - номер узла конца ветви; а - коэффициент пропорциональ-, gs ности;

А, — величина, имеющая размер- . ность длины.

Причем А 7 lij „; диоды 3, регуWlÆ(. лиуремые источники напряжения 4 моделей узлов, величина,напряжения Е> определяется соотношением

М+ - ) a 3Å1 К- (д+М-у-1)Е ц A ъ

I у(А ) где

U 02

n - количество узлов исходной. сети; а3Я ф(- сумма напряжений источников

ЭДС длиннейшего контура; 635jjpg- сумма напряжений длиннейшего полного контура;

45 у - разность между количеством узлов в полном контуре и количеством узлов в длиннейшем контуре, шунтирующие конденсаторы g, шунтирующие резисторы 6 и ограничительные резисторы 7

Величины 0 и U определяются типом используемого газораэрядного прибора.

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

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

На фиг. 1 приведена схема исходной сети; на фиг. 2 - принципиаль- 10 ная электрическая схема устройства.

Устройство содержит гаэоразрядные приборы 1 с напряжением зажигания

U и напряжением горения U, - ис,точники напряжения моделей ветвей 2, is величины напряжений которых связаны с длинами ветвей исходной сети соотношением

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

0ех 0 +(и 1)0а (3) где 0 - напряжение зажигания; и - количество последовательно включенных газоразрядных приборов;

U< - напряжение. стабилизации.

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

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

При этом напряжение на нем уменьша-: ется до 0, а разность 0 - U< пере-: распределяется между конденсаторами незажженных газораэрядных приборов.

Вторым зажигается газораэрядный прибор, шунтированный конденсатором с наименьшей емкостью из числа конденсаторов, шунтирующих неэажженные газоразрядные приборы. Напряжение на двух зажженных газоразрядных приборах изменяется до значения 20 и т.д. В результате при зажиганйи и-1 газораэрядных приборов в последовательности цепи иэ n,ïðèáoðoâ, напряжение на .группе зажженных приборов составит (n- 1)0, и для зажигания послед" него необходимо дополнительное напряжение равное 0 . Процесс протекает лавинообразно и воспринимается как одновременное зажигание всех гаэоразрядных приборов.

Свойство (3) обеспечивает в схеме протекание тока по контуру, соответствующему циклу максимальной длины в преобразованной исходной сети.

Рассмотрим неблагоприятное условие - контур, в котором сумма напряжений источников напряжения максимальна, не.проходит через все узлы (длиннейший цикл преобразованной исходной сети не является полным). При этом . a ÜÅ ôè k<îЕЬу М. где el 3б15фй сумма напряжений источников напряжения длиннейшего полного контура;

930323

{ ЕЕЯЯФ{ ИЕ„ Иа ЬЯ *+(И фя (ц 10 где 1(< п-2,- целое число, Суммарное напряжение, необходимое для зажигания газоразрядных приборов в длиннейшем полном контуре и длин-. 15 нейшем контуре, соответственно равно

U +(и-1)u ы U> (- -a)u (6) ф 2.

25

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

0 .каждого узла включены регулируемый

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

CIK E . 1{ + И 1.".

35 (И

Из полученного выражения следует, что всегда, при надлежащем выборе Е„, существует положительное d, при котором удовлетворяется неравенство (8).

Отметим, что неравенство (8) при условии (4) не удовлетворяется при

8=1.

При К) 1, (что характерно для газоразрядных приборов) значение Е

М необходимое для образования тока в .длиннейшем полном контуре, получим, решив неравенство (8) относительно E„.

При этом имеем

7 (д - ) 07Fjjgi - сумма напряжений источников напряжения длиннейшего контура.

Полагаем Е О.

Результирующее напряжение, приложенное к газоразрядным приборам в длиннейшем полном контуре и длинней-шем контуре, соответственно равно условие, при котором произойдет зажигание гаэоразрядных приборов в длиннейшем полном контуре при этом имеет вид .f -ТН

О +(И-a) U Ц +(Wy- ) {1

Ъ или, введя обозначение д= -, U2

{имеем

Cs)

Решая полученное неравенство от-. носительно {, получит

1 (и-{)а%1=„" 1,,- (и- ЖО ЗЕ : +ТЕ а ЪЕ,„ - R $qq)gy y++3 gg (д +и-s)o 2е j а-. (д +и-у- )аи„" я

Ц7

Следовательно с учетом условий (4), (8), (9), (10) при любой- разнице s суммах напряжений источников

ЭДС, включенных в ветви длиннейшего контура и длиннейшего полного контура, при К7 1 существует такое значение

Х

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

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

930323

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

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

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

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

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

26 Н 227716, кл. G 06 G 7/122, 1968.

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

Р 231903, кл. G 06 G 7/122, 1968 (прототип).

930323

S, Составитель Л. Терехов

Редактор А. Шандор Техред Д, Бабинец

Корректор И. Иуска филиал ППП "Патент",. r. Ужгород, ул. Проектная, 4

Заказ 3474/66 Тираж 732 Подписное

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

113035, Москва, Ж-35, Рауаская наб., д. 4/5