Аналоговая модель решения задачи о коммивояжере Советский патент 1982 года по МПК G06G7/122 

(5) АНАЛОГОВАЯ МОДЕЛЬ РЕШЕНИЯ ЗАДАЧИ О КОММИВОЯЖЕРЕ

I

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

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

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

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

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

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

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

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

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

20 ограничительного резистора соединен с первым выводом шунтирующего резистора и.первым выводом газоразрядного прибора, второй вывод которол % 393 го соединен с входом источника напряжения и первой обкладкой шунтирующего конденсатора, вторая обкладка которого подключена ко второму выводу шунтирующего резистораг выход источника напряжения каждой модели узла соединен с входами всех моделей выходящих ветвей графа. На фиг. 1 приведена схема исходной сети; на фиг. 2 - принципиальная электрическая схема устройства. Устройство содержит газоразрядные приборы 1с напряжением зажигания ( и напряжением горения и, - ис очники напряжения моделей ветвей 2, величины напряжений которых связаны с длинами ветвей исходной сети соотношением . А - 15j aEij, где 1ij - длина ветвей; I - номер узла начала ветви; j - номер узла конца ветви; а - коэффициент пропорциональ ностй; . А . - величина, имеющая размерность длины. Причем А П , ; диоды 3, регулиуремые источники напряжения k моделей узлов, величина .напряиАния Е определяется соотношением C(f 4- и-ч) а E-iiVk- Ccf-vvi-TH)Eijgn1; rCcT-l) г„е f.i| П - количество узлов исходной сети; cfSEjj - сумма напряжений источников ЭДС длиннейшего контура; aStijViV сумма напряжений длиннейшего полного контура; у - разность между количеством узлов в полном контуре и количеством узлов в длинней шем контуре, шунтирующие ко денсаторы 5 шунтирующие резисторы 6 и ограничительные резисторы 7. Величины и, и и j определяются тип используемого газоразрядного прибора Работа электрической модели основана на явлении, присущем электричес КИМ элементам с неустойчивым участко отрицательного сопротивления вольтамперной характеристики. Напряжение зажигания цепи последовательно включенных газоразрядных приборов, определяется соотношением где U-, - напряжение зажигания; П - количество последовательно включенных газоразрядных приборов; Ug, - напряжение стабилизации. Приведенное соотношение может быть реализовано если газоразрядные приборы в диодном.включении шунтированы конденсаторами различных по величине емкостей через сопротивления R. В результате неравномерного распределения напряжения источника между конденсаторами, первым зажигается газоразрядный прибор, шунтированный конденсатором наименьшей емкости. При этом напряжение на нем уменьшается до и, а разность . перераспределяется между конденсаторами незажженных газоразрядных приборов. Вторым зажигается газоразрядный прибор, шунтированный конденсатором с наименьшей емкостью из числа конденсаторов, шунтирующих незажженные газоразрядные приборы. Напряжение на двух зажженных газоразрядных приборах изменяется до значения и т.д. В результате при зажигании п-1 газоразрядных приборов в последовательности цепи из П приборов, напряжение на группе зажженных приборов составит (n-l)U/j, и для зажигания последнего необходимо дополнительное напряжение равное Ug.. Процесс протекает лавинообразно и воспринимается как одновременное зажигание всех газоразрядных приборов. Свойство (3) обеспечивает в схеме протекание тока по/контуру, соответствующему циклу максимальной длины в преобразованной исходной сети. Рассмотрим неблагоприятное условие контур, в котором сумма напряжений источников напряжения максимальна, не проходит через все узлы (длиннейший цикл преобразованной исходной сети не является полным). При этом 01 SEljQfhK«а EijQV (J,) где ClSEijg ik- сумма напряжений источников напряжения длиннейшего полного контура; .-iJQ - сумма напряжений источ ников напряжения длиннейшего контура. Полагаем 0. Результирующее напряжение, приложенное к газоразрядным приборам в длиннейшем полном контуре и длиннейшем контуре, соответственно равно asEiii k -VHt,, viaYB%i Cvi-9-)Ey (5; где n-Z .- целое число, Суммарное напряжение, необходимое для зажигания газоразрядных приборов в длиннейшем полном контуре и длин-, нейшем контуре, соответственно равно U,)U М (H--3-)U2 (6) Условие, при котором произойдет зажигание газоразрядных приборов в длиннейшем полном контуре при этом имеет вид . Ч St,.,e,W), . ()U2. U - -Cw-r-i)Ua , введя обозначение (Г rf- , iigv y q,(H-r)y о + Vi-i СГ 4у -Зр-:(в) IРешая полученное неравенство относительно О , получит )c,jgK-(vi-r-Oa V Из полученного выражения следует что всегда, при надлежащем выборе Е существует положительное (Г, при котором удовлетворяется неравенство ( Отметим, что неравенство (8) при ус ловии {) не удовлетворяется при (. При (f7l, (что характерно для га зоразрядных приборов) значение Е„ необходимоедля образования тока в длиннейшем полном контуре, получим, реш11в неравенство (8) относительно Е При этом имеем (cf 4H-i)q Ei jg-k-: (cT-t-h yi tie) r ((Г-1) Следовательно с учетом условий Wt (8), (9), (10) при любой-разнице в суммах напряжений источников ЭДС, включенных в ветви длиннейшего контура и длиннейшего полного контура, при существует такое значение Еу, при котором выполняется условие образования длиннейшего полного контура. Определение Д1 1ннейшего полного контура в преобразованной сети соответствует определению пути коммивояжера в исходной сети. Таким образом в данном устройстве исключается возможность образования неполных контуров, чем и достигается решение задачи о коммивояжере. Кроме того, поскольку все суммы напряжений источников напряжения полных контуров приложены к одной и той же цепи последовательно соединенных газоразрядных прибрров, т.е. действуют на общую меру сравнения, существенно снижаются требования к точности задания порога зажигания цепи газоразрядных приборов. Для построения аналоговой модели с общей мерой задачи о коммивояжере в соответствии с топологией заданной сети составляется подобная по топологии электрическая цепь где в ветвях, эквивалентных ветвям исходной сети, последовательно включены источники напряжения и диоды в напряжении, совпадающем с направлением ветвей исходной сети и по величине напряжения пропорциональные длинам ветвей преобразованной исходной сети, а между группами исходящих и входящих ветвей . каждого узла включены регулируемый Ясто.чник напряжения, ограничительный резистор и газоразрядный прибор, шунтированный конденсатором, и резистором в направлении от группы входящих в узел ветвей, к группе исходящих ветвей; Если при включении питания образуется ток в контуре, проходящем через все узлы, то этот контур, соответствует пути коммивояжера на- исходной сети. В случае образования неполных контуров, отличается питание и увеличивается значение напряжений, подключаемых между группами исходящих и входящих ветвей узлов, на источнике питания. После этого вновь подключаются все источники напряже- ния. Процедура повторяется до образования .полного контура, являющегося решением задачи.

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

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

в

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

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

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

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

2.Авторское свидетельство СССР N 231903, кл. G 06 G 7/122, 1968 (прототип).