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

(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ

1

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

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

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

Наиболее близким к предлагаемому является устройство для решения задачи о коммивояжере, представляюкидее собой электрическую сеть с расщепленными узлаш, выполненную соО КОММИВОЯЖЕРЕ

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

Недостатками известного устройства являются требование точной установки равенства значений токов в уз- лах модели, большой объем аппаратуры (при числе узлов п число источников напряжений равно , а исtoточников тока - п), возможность образования неполных циклов, т.е. таких решений задачи, при которых путь коммивояжера не будет проходить через все узлы. Интуитивно-эвристи15ческий метод отключения ветвей, об- разукицих неполные циклы, не дает возможности получения точного результата решения, так как полный цикл при таком подходе образуется уже в

Я искаженной сети, не соответствующей исходной задаче.

изобретения - повышение точности решения задачи.

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

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

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

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

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

будет равно , Е, и это напряжение будет деЬствовать на суммарное количество газоразрядных приборов срответствуюищх моделей ветвей. Тогда напряжение пробой в любом -i -м полном контуре определится как . R UsaHcMKH)Ur, Н) где К - суммарное количество газоразрядных приборов, включенных в ветвях J -го полного контура Очевидно, что при плавном изменении S Е первым пробьется контур, отвечающий условию ,. что соответствует решению задачи коммивояжера. Действительно, учитьюая, что К 5:т;: 5: l-ij) 1 Ujl 3 - соответственно длина ij-й ветви и количество газоразрядных приборов, ее моделирующих, на основании выражения . |1) можно сделать вывод о том, что при достижении равенства включается контур, являющийся решением задачи коммивояжера согласно формулы 21. Покажем условия невозникновения в схеме неполных контуров, не являющихся решением задачи о коммивояжере, для чего рассмотрим полньй контур с количеством газоразрядных приборов К и неполный контур с количеством газоразрядных приборов S. Учитывая, что суммарная ЭДС в полном контуре , где Е - ЭДС регулируемого источника в одном узле, а в неполном контуре )Е где l Jfjn-Z, где - целое число, условие образования только полного контура запишется в виде )E-i - Неравенство (5) удовлетворяется 8., (S ЧТО определяет требования к характ ристикам нелинейных элементов, используемых для решения задачи коммивояжера в сети заданного объема и длин ветвей. Таким образом, предлагаемое уст ройство повышает точность решения и позволяет практииески мгновенно получить истинный результат реше1ш Формула изобретения 1, Устройство для ранения задачи о коммивояжере, содержащее моде ли узлов и модели ветвей, причем каждый выход каждой модели узла со нен через модели ветвей с входами всех других моделей узлов, а кажда модель ветви состоит из последовательно включенных модели длины ветви и разделительного диода, отличающееся тем, что, с целью повышения точности решения задачи, в каждую модель узла между его входом и выходом дополнительно включены последовательно соединенные ограничительный резистор и регулируе№1й источник напряжения. 2. Устройство по п. 1, отличающееся тем, что каждая йодель длины ветви выполнена в виде цепочки последовательно включенных элементов с падагацим участком вольтамперной характеристики, например, газоразрядных ламп, вход каждого из которых через последовательно включенные ограничительный резистор и накопительный конденсатор, соединен . с его выходом. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 230527, кл. G 06 G 7/122, 1967. 2.Моделирование задач исследования операций. Под ред. Витенбёрга. М., Энергия, 1978, с. 143 (прототип).