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

ОП ИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СфветскикСециалистическикРеслублик(51)М. Кл. 6 06 О 7/122 с присоединением заявки М(23) Раудереиккай квинтет ИФР ю Аааай нзокретевнв н вткрытяй(088.8) Дата опубликования описания 23 . 05 .82(72) Авторизобретения Л.ф. федотов Киевский автомобильно-дорожный институт им. 60-л Великой Октябрьской социалистической революции(54) АНАЛОГОВАЯ МОДЕЛЬ РЕЦ 1 ЕНИЯ ЗАДАЧИ О КОММИВОЯЖЕРЕ Изобретение относится к аналоговому моделированию и предназначено для . решения задачи о коммивояжере.Известна модель сетевого графика для решения задачи коммивояжера, содержащая регулируемые линии задержки генераторы импульсов, триггеры, схемы совпадения, формирователи импульсов, цикличные счетчики, схемы разделения, регистры 1 11.Однако известное устройство сложно по конструкции. Наиболее близким к данному техническому решению является устройство для решения задач коммивояжера, содержащее модели ветвей, состоящих из источника. напряжения и диода, и модели узлов, состоящих из источника напряжения21.Недостатком известного устройства является то, что все узлы, кроме исходного, дублированы (и) раз. Это приводит к большому количеству используемых элементов для решения :задачи.Цель изобретения - упрощениеустройства.Поставленная цель достигается тем, .что в аналоговой модели, содер" жащей модели ветвей по числу ветвей графа, соединенные согласно топологии графа, причем каждая модель состоит из последовательно включенных диода и источника напряжения и модели узлов, состоящие из источника напряжения, вкаждую модель узла введены газоразрядный прибор, шунтирующий конденсатор, шунтирующий. резисифтор и ограничительныи резистор, причем, первый вывод ограничитель" ного резистора каждой модели узла подключен к выходам всех моделей, входящих ветвей графа, второй вывод ограничительного резистора соединен с первым выводом шунтирующего резистора и. первым выводом газоразрядного прибора, второй вывод котороФ(е) 1Решая полученное неравенство от-. 55 носительно О, получиту 10 М)аЪЕ" 1,-Ь-Г)О ЗЕ+ТЕф,ЖИз полученного выражения следует, что всегда, при надлежащем выборе Е, существует положительное 3, при ко-" тором удовлетворяется неравенство (8).45 Отметим, что неравенство (8) при условии (4) не удовлетворяется при .1=1.При К) 1, (что характерно для газоразрядных приборов) значение Е 1 необходимоедля образования тока в ,длиннейшем полном контуре, получим, решив неравенство (8) относительно .При этом имеем тированный конденсатором, и резисто- ром в направлении от группы входящих в узел ветвей, к группе исходящих ветвей; Если при включении питания образуется ток в контуре, проходящем . через все узлы, то этот контур, соответствует пути коммивояжера на исходной сети. В случае образования неполных контуров, отличается питание и , увеличивается значение напряжений, подключаемых между группами исходящих и входящих ветвей узлов, на источнике питания. После этого вновь подключаются все источники напряже" ния. Процедура повторяется до образования,полного контура, явпяющегося решением задачи.(ди) 6 2 ЕЕр ОЗАРЯЙ - сумма напряжений источ=ников напряжения длиннейшего контура.Полагаем Е О.Результирующее напряжение, прило женное к газоразрядным приборам в длиннейшем полном контуре и длинней- . шем контуре, соответственно равно С 3 ЕЕфрй ФИЕИО 211 щ+И-фЕ (6) 0 где 1 п," целое число,Суммарное напряжение, необходимоедля зажигания газоразрядных приборовв длиннейшем полном контуре и длин-, 15нейшем контуре, соответственно равно0 +Ь)О ыОЪ(и1 О (6)"Э 2 условие, при котором произойдет зажигание гаэоразрядных приборов в длиннейшем полном контуре при этом имеет вид и( .ЙБ ., ( (-, ИФи-"-1)ФИ. мД-)Оо) Следовательно с учетом условий (4), (8), (9), (10) при любой- разнице в суммах напряжений источников ЭДС, включенных в ветви длиннейшего контура и длиннейшего полного контура, при д 7 1 существует такое значение 2Е , при котором выполняется условиеразования длиннейшего полного контура. Определение длиннейшего полного контура в преобразованной сети соответствует определению пути коммивояжера в исходной сети.Таким образом в данном устройстве исключается воэможность образования неполных контуров, чем и достигается решение задачи о коммивояжере. Кроме того, поскольку все суммы напряжений источников напряжения полных контуров приложены к одной и той же цепи последовательно соединенных газоразрядных приборов, т.е. действуют на общую меру сравнения, существенно снижаются требования к точности задания порога зажигания цепи газораэрядных приборов. Для построения аналоговой моделис общей мерой задачи о коммивояжерев соответствии с топологиеи заданнойсети составляется подобная по топологии электрическая цепь где в ветвях,эквивалентных ветвям исходной сети,последовательно включены источникинапряжения и диоды в напряжении, совпадающем с направлением ветвей исходной сети и по величине напряженияпропорциональные длинам ветвей преобразованной исходной сети, а междугруппами исходящих и входящих ветвейкаждого узла включены регулируемыйИсточник напряжения, ограничительныйрезистор и газоразрядный прибор, шун 930323Устройство позволяет решать ряд задач исследования операций, например, задачи и назначениях, задач составления расписаний, задачи об определении оптимального развозочного маршрута.формула изобретенияАналоговая модель решения задачи о коммивояжере, содержащая модели ветвей по числу ветвей графа, соеди" ненные согласно топологии графа, при" чем каждая модель состоит иэ последовательно включенных диода и источника напряжения и модели узлов, состоящие из источника напряжения, о тл и ч а ю щ а я с я тем,что,с целью упрощения, в каждую модель узла введены газоразрядный прибор, шунтирующий конденсатор, шунтирующий резистор и ограничительный резистор,причем, первый вывод ограничительного резистора каждой модели узла под"ключен к выходам всех моделей входящих ветвей графа, второй вывод огра- В ничительного резистора соединен с первым выводом шунтирующего резистораи первым выводом газоразрядногоприбора, второй вывод которого соединен с входом источника напряжения ипервой обкладкой шунтирующего конденсатора, вторая обкладка которогоподключена ко второму выводу шунтирующего резистора, выход источниканапряжения каждой модели узла соеди- И . нен с входами всех моделей выходящихветвей графа.Источники инФормации,принятые во внимание при экспертизе1. Авторское свидетельство СССР 2 ф Н 227716, кл. 606 0 7/122, 1968.2. Авторское свидетельство СССРЮ 231903, кл. С 06 С 71122, 1968930323 Фма 2 Составитель Л. ТерехоедакторА. Шандор Техред Д, Бабинец орректор И. Иус ПодписноеСР з 3474/66 Тираж 732 ВНИИПИ Государственного комитета С по делам изобретений и открытий 113035, Москва, Ж, Рауаская наб.