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

Союз Советск ниСоциалистическиеРеспублик О П И С А Н И Е ц 932505ИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(51) М. Кл. 6 06 С 7/22 РВударстюю квмитет СССР пп делам иаееретениВ и аткрмти 1(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯО КОКИВОЯЖЕРЕ ЧИ зобретени относится к вычисли- и может быть испольния задачи о коммивоельнои тех вано дляер с рассоточ Известна электрическая модель задачи о коммивояжере, содержащая цифровые модели ветвей и цифровые модели городов, соединенные согласно топологии реальной транспортной сети, причем исходньш город разбивается на два (начальный и конечный города), что соответствует расщеплению исходного узла электрической модели на два узла 11.Недостатками такой модели являются чрезвычайная сложность ее реализации и необходимость проведения (и"2) повторных решений для получения маршрута коммивояжера.Наиболее близким к предлагаемому является устройство для решения задачи о коммивояжере, представляюющее собой электрическую сеть щелпенными узлами, выполненную гласно топологии реальной транспортной сети, в каждую ветвь которойвключена последовательно электрическая модель длины ветви2.Недостатками известного устрой-ства являются требование точной установки равенства значений токов в уз-лах модели, большой объем аппаратуры при числе узлов п число источников напряжений равно , а иск и10точников тока - и), возможностьобразования неполных циклов, т. е.таких решений задачи, при которыхпуть коммивояжера не будет проходить счерез все узлы. Интуитивно-эвристический метод отключения ветвей, образующих неполные циклы, не даетвозможности получения точного результата решения, так как полный циклпри таком подходе образуется уже вискаженной сети, не соответствующейисходной задаче.ЦЕпь изобретения - повышениености решения задачи.32505 фэлементов опр еделя ет в некотороммасштабе длину моделируемой ветви.Для доказательства единственностирешения задачи о коммивояжере примем, что длина ветви моделируетсяцепью последовательно включенныхгазоразрядных приборов, количествокоторых пропорционально длине ветви,Допустим также, что в любой момент 1 о времени напряжения регулируемых источников 14 в каждом узле сети равны Е. Тогда суммарное напряжение,приложенное к любому полному контуру, проходящему через все и узлов, 15 будет равно, Е , и это напряжеУние будет деиствовать на суммарноеколичество газоразрядных приборовсоответствующих моделей ветвей.Тогда напряжение пробой в любом м -мполном контуре определится как1 к 110 ис (11 Ггде К - суммарное количество газоразрядных приборов, включенных 25 в ветвях 1 -го полного контураОчевидно, что при плавном измененииЕ первым пробьется контур, отвечающий условию К=п 1 п,. что соответствует решению задачи коммивояжера.Действительно, учитывая, чтоК=Е В, =Е 1" =аП, 12) 3 9Поставленная цель достигается тем, что в устройство для решения за дачи о коммивояжере, содержащее модели узлов и модели ветвей, причем каждый выход каждой модели узла соединен через модели ветвей со входами всех других моделей узлов, а каждая модель ветви состоит иэ последовательно включенных модели длины вет ви и разделительного диода, в каждую модель узла между его входом и выходом дополнительно включены последовательно соединенные ограничительный резистор и регулируемый источник напряжения,Кроме того, каждая модель длины ветви выполнена в виде цепочки последовательно включенных элементов с падающим участком вольт-амперной характеристики, например, газоразряд ных ламп, вход каждого из которых через последовательно включенные конденсатор и резистор соединен с его выходом.На чертеже представлена ахема предгагаемого устройства.Устройство содержит модели узлов ,1-4 транспортной сети, причем 5-8- выходы моделей узлов, 9-12 - входы моделей узлов, разделительные диоды 13, регулируемые источники 14 напряжений, ограничительные резисторы 15, модели 16 (длины) ветвей в виде последовательно включенных элементов с падающим участком вольтамперной характеристики, зашунтированных цепочками из последовательно включенных конденсатора и резистора.Работа схемы протекает следующим образом.При одновременном плавном изменении величины напряжений всех регулируемых источников 14 напряжения определяется момент, когда срабатывает одна из возможных цепей с моделями 16 длины ветвей, Путь протекания тока опередит решение задачи коммивояжера в исходной транспортной сети.Для индикации маршрута движения в каждую ветвь может быть включен индикатор тока.В качестве элемента с падающим участком вольт-амперной .характеристики, используемых в электрической модели длины ветви, могут применяться диоды в обратном включении, тиристоры, динисторы, газоразрядвые приборы и др., причем количество таких И 1)И 1где 1 , щ 1 - соответственно длина11-й ветви и количест во газоразрядных приборов, ее моделирующих,на основании выражения 11) можно сделать вывод о том, что при достижении равенства40 ЕЕ=Ок пиивключается контур, являющийся решением задачи коммивояжера согласноформулы 21.Покажем условия невозникновенияв схеме неполных контуров, не являющихся решением задачи о коммивояжере, для чего рассмотрим полныйконтур с количеством газоразрядныхприборов К и неполный контур с количеством гаэоразрядных приборов .ФУчитывая, что суммарная ЗДС в полном контуре Е=пЕ, где Е - ЭДС1регулируемого источника в одном 55 узле, а в неполном контуре Е=(п-)Егде 1 п"2, где- целое число,условие образования только полногоконтура запишется в виде8) - к- - 5+5, 5)о-уу 710 что определяет требования к характеристикам нелинейных элементов, используемых для решения задачи коммивояжера в сети заданного объема и длин ветвей. ИТаким образом, предлагаемое устройство повышает точность решения и позволяет практически мгновенно получить истинный результат решения. Формула изобретения 1. Устройство для решения задачи о коммивояжере, содержащее моде- р ли узлов и модели ветвей, причем каждый выход каждой модели узла соединен через модели ветвей с входами всех других моделей узлов, а каждая 1 05 6.модель ветви состоит из последовательно включенных модели длины ветвии разделительного диода, о т л ич а ю щ е е с я тем, что, с цельюповышения точности решения задачи, вкаждую модель узла мекду его входоми выходом дополнительно включеныпоследовательно соединенные ограничительный резистор и регулируемый источник напряжения.2. Устройство по п, 1 о т л и -ч а ю щ е е с я тем, что каждая модель длины ветви выполнена в видецепочки последовательно включенныхэлементов с паданхцим участком вольтамперной характеристики, например,газоразрядных ламп, вход каждого изкоторых через последовательно включенные ограничительный резистор инакопительный конденсатор, соединен .с его выходом.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРФ 230527, кл, С 06 С 7/122, 1967.2. Моделирование задач исследования операций. Под ред. Витенберга.М., "Энергия" 1978, с. 143 (прототип).932505 732арственного изобретений ва, Ж, Р 1 одписн та СССР аказ 3786 70 Тираж ВНИИПИ Госу по делам 13035, Мосот 4/ город, ул. Проектная,илиал ПП атент Составитель И,Лебедев Редактор М,Ткач Техред 3, Фанта Корректор М.Ко