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

(5 П 0 06 0 7 48 ОПИСАНИЕ ИЗОБРЕТЕНИ К АВ НОМУ СВИДЕТЕЛЬСТ 8668/18-24.83 . 84. Бюл. донов, А бов В, И. М 20М. Щетинин,ябцев и Ю.С,Ва л УДАРСТВЕННЫИ КОМИТЕТ СССРДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56 ) 1. Бычкова Л.С. Решение задачи коммивояжера на специализированных аналоговых устройствах.-Кн.Приборс э строение, средства автоматизации и системы. управления. М., фНаука", 1967, с. 156-163.2. Авторское свидетельство СССР Р 227716, кл. 0 06 0 7/48, 25.09.68. (прототип).(54)(57) 1. УСТРОЙСТВО РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА, содержащее блок модели графа, состоящую из моделей ветвей, соединенных между собой в соответствии с топологией графа, через начальные и конечные узлы, инцидент-. ные соответствующим расщепленным вершинам графа, о т л и ч а ю щ е ес я тем, что, с целью повышения.быстродействия, в устройство дополнительно введены первый, второй и третий блоки ключей, аналого-цифровой преобразователь, первый, второй и третий блоки памяти, блок выбора экстремального числа, блок индикации, блок управления, состоящий из сдвоенных кнопочных переключателей, первого и второго генераторов импульсов, первого и второго элементов ИЛИ, первого и второго ,ключей элемента И, триггеров, коммутатора согласующих диодов, причем первые контакты сдвоенных кнопочных переключателей через согласующий резистор соединены с выходом первого источника постоянного напряжения, вторые контакты сдвоенных кнопочных переключателей объединены и соединены с выходом первого гене- ратора импульсов, третьи контакты сдвоенных кнопочных переключателей соединены с первыми входами .соответствующих триггеров и через первую группу согласующих диодов подключены к входу первого ключа, четвертые кон. такты кнопочных переключателей соединены с вторыми входами соответствующих триггеров и через согласующие диоды - с первым выходом сдвигового регистра, выходы триггеров подключены к входам коммутатора и через первый элемент ИЛИ - к управляющему входу первого элемента И, информационный вход которого подключен к выхо ду второго генератора импульсов, выход первого элемента И подключен к входу сдвига сдвигового регистра, второй и третий выходы которого соединены с входами второго элемента ИЛИ вход второго ключа подключен к выходу второго источника постоянного % напряжения, входы второго элемента И подключены к первой группе информационных выходов первого блока памяти, входы управления адресом записи которого соединены с группойвыходов сдвигового регистра, выход второго ключа соединен с управляющими входами моделей ветвей, информационные выходы которых соединены соответственно с информационными входами первого и второго блока ключей, управляющие входы которых соединены соответственно с выходами триггеров и группой выходов сдвигового регистра, выходы коммутатора подключены к управляющим входам третьего блока ключей, информационные входы которого соединены с выходами блока выбора экстремального числа, управяющий вход которого подключен к выходу второго элемента И, выходы первого и второго блока ключей подключены к входам аналого-цифрового преобразователя, выходы которого соединены с информационными входами пер1095201 40 ие Составитель А. КолчинНедолуженко Техред А.Ач К ор О.Ти едак тор дписное илиал ППП "Патент", г.ужгород, ул.Проектна з 3600/32 Тираж 699 ВНИИПИ Государственного к по делам изобретений и 113035, Москва, Ж, Раушмитета СССР крытий ая наб., д1095201 вого блока памяти, четвертый выходсдвигового регистра подключен к вхо.ду разрешения записи первого блокагамяти, выходы которого соединены синформационными входами блока выбора экстремального числа, выходы третьего блока ключей подключены к информационным входам второго блока памяти, вход разрешения записи которогосоединен с выходом второго элементаИЛИ, выходы триггеров подключенык информационным входам третьегоблока памяти, вход разрешения записи которого подключен к второму выходу сдвигового регистра, выходы второго и третьего блоков памяти соединены соответственно с первой и второй группой входов блока индикации,управляющий вход которого соединен свыходом первого ключа, выходы второго блока памяти соединены с первыми Изобретение относится к вычислительной технике и может быть примене. но для решения задачи коммивояжера, а также ряда задач, сводящихся к ней.,Из-,естна электрическая модельгра фа, в которой каждой дуге графа соответствуют последовательно соединенные сопротивление и диод модель дуги; соединение элементов модели графа, т.е. моделей дуг, производится в соответствии с топологией графа; в узлах размещены переключакщие схемы, количество которых в хайдом узле равно числу пар вершин, соединенных между собой хотя бы одной дугой Я .Недостатком известного устройства является высокая трудоемкость реше- д ния задачи коммивояжера, определяемая необходимостью полного переброса возможных состояний переключакщих схем с целью выбора из этого множества состояний состояния, адекватного решению задачи коммивояжера. Эта тру 4 Ъемкость существенно повышается для симметричной задачи коммивояжера.1Наиболее близким по технической сущности к предложенному является устройство для решения задачи коммивояжера, содержащее модель графа задачи коммивояжера, состоящую из моде лей ветвей, соединенных между собой в соответствии с топологией графа задачи коммивояжера, и из моделей вершин графа задачи коммивояжера, подключенных к соответствующим моделям ветвей 2 . входами соответствующих тригге-ров,2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок модели графа выполнен в виде измерительных резисторов, первые выводы которых подключены к информационным входам первых ключей в соответствующих моделях ветвей, выходы которых подключены к входам управляемых источников напряжения в соответствующих моделях вет- . вей, выходы которых соединены с информационными входами вторых ключей в соответствующих моделях ветвей, первые и вторые выводы измерительных резисторов подключены к информационным выходам блока модели графа, соответствующие пары начальных и конечных узлов соединены между собой через последовательно соединенные ключ и переменный резистор. Недостатком известного устройства является низкое быстродействие устройства при решении задачи коммивояжера. Цель изобретения - повышение быстродействия.Поставленная цель достигается тем, что в устройство для решения задачи коммивояжера, содержащее блок модели графа задачи коммивояжера, состоящую из моделей ветвей, соединенных согласно топологии графа через начальные и конечные узлы, инцидентные соответствующим расщепленным верши-нам графа, дополнительно введеныпервый, второй и третий блоки клю" чей, аналого-цифровой преобразова-. тель, первый, второй и третий блокипамяти, блок выбора экстремальногочисла, блок индикации, блок управления состоящий из сдвоенных кнопочных переключателей, первого и второго генератора импульсов, первого ивторого элементов ИЛИ, первого и второго ключей, элемента И, триггеров,коммутатора, согласующих диодов,причем первые контакты сдвоенныхкнопочных переключателей через согласующий резистор соединены с первымисточником постоянного напряжения,вторые контакты сдвоенных переключателей объединены и,соединены с выходом первого генератора импульсов,третьи контакты счвоенных кнопочныхпереключателей соединены с первымивходами соответствующих триггеров ичерез первую группу согласующих диодов подключен к входу первого ключа,Кроме того, блок модели графа выполнен в виде измерительных резисто- ров, первые выводы которых подключеб 5 четвертые контакты сдвоенных кнопоч- ных переключателей соединены со вторыми входами соответствующих триггеров и через согласующие диоды - с первым выходом сдвигового регистра, выходы триггеров подключены к входамкоммутатора и че. з первый элемент ИЛИ - к управляющему входу первого элемента И, информационный вход кото.рого подключен к выходу второго генератораимпульсов, выход первого 1 О;элемента И подключен к входу сдвигасдвигового регистра, второй и третийвыходы которого соединены с входамивторого элемента ИЛИ, вход второгоключа подключен к выходу второго источника постоянного напряжения, выходы второго элемента И подключены кпервой группе информационных выходовпервого блока памяти, входы управления адресом записи которого соединены с группой выходов сдвигового регистра, выход второго ключа соединен с управляющими входами моделейветвей, информационные выходы которой соединены соответственно с инфор мационными входами первого и второгоблока ключей, управляющие входы которых соединены соответственно с выходами триггеров и группой выходовсдвигового регистра, выходы коммутатора подключены к управляющим третьего блока ключей, информационные входы которого соединены с выходамиблока выбора экстремального .числа,управляющий вход которого подключенк выходу второго элемента И, выходыпервого и второго. блока ключей подключены к входам аналого-цифровогопреобразователя, выходы которого соединены с информационными входамипервого блока памяти, четвертый выход сдвигового регистра подключен квходу разрешения записи первого блока памяти, выходы которого соединены с информационными входами блокавыбора экстремального числа, выходы 45третьего блока ключей подключены кинформационным входам второго блокапамяти,. вход разрешения записи которого соединен с выходом второго элемента ИЛИ, выходы триггеров подклю Очены к информационным входам третьего блока памяти, вход разрешениязаписи которого подключен к второмувыходу сдвигового регистра, выходывторого и третьего блоков памятисоединены соответственно с первойи второй группой входов блока индикации, управляющий вход которогосоединен с выходом первого ключа,выходы второго блока памяти соединены с первыми входами соответствующихтриггеров,ны к информационным входам первыхключей в соответствующих моделях ветвей, выходы которых подключены квходам управляемых источников напряжения в соответствующих. моделях ветвей, выходы которых соединены с информационными входами вторых ключей в соответствующих моделях ветвей, первые и вторые выводы измерительныхрезисторов подключены к информационным выходам блока модели графа, соответствующие пары начальных и конечных узлов соединены между собой через последовательно соединенные ключи переменный резистор.На фиг. 1 изображена блок-схема устройства; на фиг. 2 - модель графа задачи. коммивояжера на четыре узла; на фиг. 3 - модель ветви; на фиг. 4 - блок выбора экстремального числа; на фиг, 5 - схема соединений узлов сравнения и элементЬв ИЛИ блока выбора экстремального числа (схема соединений представлена для четырех четырехразрядных чисел; на фиг. 6 блок управления во взаимодействии с блоком ключей, двумя блоками памяти.и блоком индикации; на фиг.7 ячейка блока индикации; на фиг. 8граф задачи. коммивояжера на четыреузла.Предлагаемое устройство фиг. 1)состоит из модели 1 графа задачи коммивояжера, блоков ключей 2-4, блока 5 выбора экстремального числа,аналого-цифрового преобразователя 6,блоков памяти 7-9, блока управления 10, .блока индикации 11.Модель 1 графа задачи коммивояжера фиг. 2) состоит из моделей 12ветвей, начальных узлов 13, конечныхузлов 14=1, 2, , П), измерительного резистора 15 и переменногорезистора 16 и ключей 17. Каждая модель ветви содержит ключи 18и 18,управляемый источник напряжения 19(Фиг. 3), Блок 4 ключей состоит изэлементов И 20; и 21 ( =2,3, Д,=1,2 М -1, где И - максимальнаяразмерность устройства). Блок выбораэкстремального числа 5 содержитфиг. 4 0 = 8-1 узлов 22 анализаК=1, 2 Ю, каждый из которых состоит из 5 = вт - число двоичныхразрядов) сравниваемых чисел с учетом знаковых разрядов, полусумматорой 23, элемента 24 НЕ, элемента 25 И,В элементов 26 ИЛИ, в 1 поразрядныхузлов 27 сравнения; каждый поразрядный узел 27 сравнения содержит эле. -мент 28 И, элемент 29 ИЛИ, элемент30 НЕ,Блок индикации 11 состоит из Н 8клеток 31 которые составляют рядый столбцы 1 матрицы, причем приклетка 31 является пустой. Каждаязаполненная клетка 31," состоит (Фиг. 7)из элемента 32 И,1) -триггера 33 исветодиода 34. В блоке индикации 11в каждом столбце первые входы непус-ых клеток 31 соединены между собойи подключены к одному из входов первой группы и входов блока индикации 11 фиг. 6), в каждом ряду вторые входы непустых клеток 31 соединены между собой и подключены к одномуиз входов второй группы П входов блока индикации 11 фиг. 6), третьивходы непустых клеток 31 соединенымежду собой и подключены к входу упблока индикации.Блок управления 10 фиг. б ) ( условно показан для устройства с размерностью й =4 ) состоит из сдвоенныхкнопочных переключателей 35; 1) -триггеров 36,; коммутатора 37, сдвигового регистра 38, элемента ИЛИ 39;элемента ИЛИ 40, элемента И 41, ключа 42, генераторов (прямоугольных)импульсов типа "меандр" 43 и 44;элемента И 45, источников постоянного напряжения 46 и 47, согласующихдиодов 48, согласующего резистора 49.25Устройство работает следующимобразом.Допустим, что максимальная размерность устройства равна 4, т.е. М =4, и задача решается для графа задачи коммивояжера также с размерностью й =4. В исходном положении все ключи 17 (;,г. 2) разомкнуты, все модели 12 ветвей также разомкнуты ( при помощи своих ключей 18), а на их источни ках постоянного напряжения 19 выставляют напряжения Е,пропорциональные межузловым расстояниям решаемой задачи коммивояжера. При помощи ключа 42 бЛока управления 10 (фиг, б) 4 О подается управляющий сигнал на ключи 18 моделей ветвей 12, что обеспе; чивает их включение и в конечном счете - сборку модели 1 графа зада- чи коммивояжера. Поскольку модель 1 графа задачи коммивояжера во включен-О ном состоянии представляет собой некоторую линейную разветвленную электрическую цепь, то в ней на основании закона Кирхгофа произойдет такое распределение токов и напряжений, что одни модели ветвей 12 будут выполнять Функцию активных источни- . ков энергии, а другие модели 12 ветвей - функцию пассивных источниКов энергии: 9=Е+ р;, где 0;- напряжение с соответствующим знаком (+) на некотором узле 14, относительно соответствующего узла 13 (фиг. 2) Е - первоначальное выставленное напряжение на 1 -и источнике 19 напряже 1ния (Фиг. 3); г - внутреннее сопротивление-й модели ветви 12 с учетом сопротивления 15 (фиг. 2);- ток в-й ветви (знак второго 1слагаемого в приведенной Формуле за висит от направления тока по ветви) .Легко доказать, что минимальному гамнльтонову контуру в модели 1 графа задачи коммивояжера в установившемся режиме соответствует максимальное положительное приращение напряжения;тах. Решение задачи коммивояжера на предложенном устройстве сводится к отысканию гамильтонова контура с максимальным суммарным положительным приращением напряжения контура: с.г, = та. Для этого кратковременно нажимают любую кнопку переклю; чателя 35 (фиг, 6) например, кнопку переключателя 35, выбирая тем самым в качестве стартового узла в будущем гамильтоновом контуре узла 13 в модели 1 графа (фиг, 2), или, что то же самое, узел 2 - в графе задачи коммивояжера (фиг. 8), После нажатия кнопки переключателя 35, через ее первый и четвертый контакты подается логическая ф 1" от первого источника напряжения, которая записывается на выходе триггера 36 за счет подачи меандра на его С-вход от генератора 44 импульсов (фиг. 6). Эта ф 1" появляется на одном из выходов второй группы 2 выходов блока 10 управления и соответственно на одном из входов второй группы 1 входов блока ключей 2, отчего сработает его соответствующий ключ (реле) и подключит узел 13 к первому (отрицательгному ) входуаналого-циФрового преобразователя б, а также отключит ( разорвет) через соответствующиелючи 18 ( фиг. 3) те модели ветвей 12,оторые подсоединены к узлу 141 эта же ф 1" появляется на одном из выходов первой группы Й выходов блока 10 управления и соответственно на одном из входов группы и входов . блока памяти 9 фиг. 1,6); эта же "11 появляется на второй вертикальной шине коммутатора 37, откуда она дереходит на его горизонтальные шины, соединенные через диоды с второй вертикальной шиной, и дальше через соответствующие выходы четвертой группы 6 выходов фтока 10 управления - на вторые е входы соответствующих элементов 20, И и 21 И с индексом=1,3.,4, подготавливая будущее срабатывание одного из них в результате ожидаемого появления на нем дополнительной ф 1" от блока 5 выбора экстремального числа; эта же ф 1" появляется на одном из входов элемента 39 ИЛИ, затем - на его выходе и на первом входе элемента И 45, отчего импульсы от генератора 43 импульсов начнут поступать на вход сдвигового регистра 38 и заставят его работать в режиме переключателя . Первый импульс от генератора импульсов 43 переводит "1" с шестого выхода10 сдвигового регистра 38 на первый выход его группы выходов, поэтому она появляется и на первом выходе группывыходов блока 10 управления; эта ф 1" поступит соответственно на первый вход второй группывходов блока ключей 3 и на первый вход второй группы У входов блока памяти 7, в результате чего соответствующий ключ (реле) блока ключей 3 подключит к второму (положительному ) входу аналого-циФрового преобразователя б начальный полюс Н модели. 12 ветви, расположенной между узлами 13 и 14, подавая тем самым на аналого"цифровой преобразователь б напряжение с 15 соответствующим знаком (+) с соответствующего резистора 15 (фиг. 2), которое преобразуется в аналого-цифровом преобразователе б в некоторое число О в двоичном коде, которое запишется в первом регистре блока памяти 7. Это число может быть либо положительным, либо отрицательным. После прихода второго импульса на вход регистра сдвига 38 от генератора импульсов 43 появятся ."1" на втором выходе группыи втором выходе группы Р выходов регистра сдвига 38, а следовательно, и блока 10 управления. Одна из этих ф 1" заставит сработать второй ключ блока ключей 2 и подключить к аналого-цифровому преобразователю б резистор 15 (фиг. 2), рас- . положенное между узлами 13 и 14, а вторая "1 ф заставит второй регистр блока памяти 7 записать второе числокоторое окажется на выходе аналого-цифрового преобразователя б. После прихода третьего импульса на вход регистра сдвига 38 уровней в третьем регистре блока памяти 7 будет 40 записано число 02, равное в двоичном коде напряжению на резисторе 15,. расположенного между узлами 13и 144 (фиг. 2). Четвертый импульс на входе сдвигового регистра 38 вызовет "1" на 45 ,первом выходе сдвигового регистра 38 и одновременно на входеузла блока памяти 9, а через элемент 40 ИЛИ - и на входе Ц блока 8 памяти (фиг. 1 и б)в результате на всех выходах 50 группы Н выходов блока памяти 8 установится ф 0", а на втором выходе группы и выходов блока памяти 9 и соответственно на втором входе второй группы и входов блока индикации 11 55установится "1", а это приведет к тому, что все непустые клетки 31 второго ряда блока 11 ( фиг. б и 7) будут подготовлены к срабатыванию, т.е. к зажиганию некоторого свето диода 34. Таким образом, после трех ф 1" на выходе регистра сдвига 38 в блоке памяти 7 окажется записанным массив из трех чисел а о, пгеиэ которых надо выбрать экстремальное 65 число. Массив чисел может быть либоположительный, либо отрицательным,либо смешанным; в первом и третьемслучае надо из массива выбрать максимальное положительное .число, а вовтором случае - минимальное по модулю. Эту функцию выполняет блок 5выбора экстремального числа (фиг. 4и 5), на входы м которого сигналыс выходов регистров блока памяти 7,подаются через элементы И блока памяти 7 ( т.е. через общепринятую схему снятия информации ) после подачина эти схемы пятой ф 1" с шестого 9выхода блока управления 10 пятая "1на втором Ш выходе сдвигового регистра 38, а следовательно, и на шестом ц. выходе блока управления 10 появляется после подачи на вход сдвигового регистра 38 пятого импульсаот генератора импульсов 4. При этрмв случае отрицательного массива чи.сел логическая 1" со знаковых разрядов, поступая на элемент И 41 блокауправления 10, вызывает "1 ф на первом с выходе (Фиг. 1 и б) блока управления 10, которая поступает навторые входы полусумматоров 23 узлованализа 22 блока 5 выбора экстремаль.ного числа (фиг. 4), что вызываетинверсию кодов чисел на входах узлов27 сравнения, в результате чего минимальное по модулю число массивачисел становится после полусумматоров 23 максимальным числом. При сравнении чисел их двоичные коды поступают на входы М блока 5 выбора экстремального числа; старшие разрядычисел поступают на 1 уп) узлы сравнения 27 ( фиг. 4), а знаковые разряды чисел поступают на л узлы сравнения 27. В узлах сравнения 27 с инвертированным единичным значением знаковых разрядов кодов сравниваемых чисел устанавливается "1" на выходеэлементов 29 ИЛИ. В узлах сравнения27 я, с инвертированным нулевым значением знаковых разрядов кодов сравниваемых чисел устанавливается "0" навыходе элементов 29 ИЛИ, так какнаих первых входах имеется "О с выхода элементов НЕ 24 и "0" -на ихвторых входах с выхода элементов 30НЕ, ибо на входе последних существует"1" при наличии инвертированной "1"на входе узла сравнения 27 хотя бы водном узле анализа 22, Нулевой сигнал с выхода элементов ИЛИ 29 запрещает все элементы И 28, расположенные в узлах "27,., 27.,27 сравнения, и элементы й 25 соответствующих узлов 22; анализа, исключая их участие в формировании выходного сигнала на соответствующих выходах 1 блока 5 выбора экстремального числа (фиг, 41. При отсутствии чисел с единичным значением данногоразряда единичное значение выхода элемента ИЛИ 29 во всех узлах анализа 22 устанавливается по цепи: элемент 28 И, элемент 26 ИЛИ, элемент 30 НЕ, второй вход элемента 29 ИЛИ и обеспечивает анализ содержимого сле дующего разряда чисел.После установления сигналов на выходах элементов 28 И, соединенных со старшими каналами, работа логических элементов в других каналах аналогич на. Единичное значение на выходе элемента 25 И, а следовательно, и на выходе ь блока 5 выбора экстремального числа установится только в том узлеанализа 22;, который ни в одном узле 15 сравнения 27 не содержит элемент 29 ИЛИ с нулевым значением на выходе, т.е. в узле анализа 22 с максимальным числом на его входах М . При наличии на выходах р блока 7 памяти только отрицательных чисел, на входы узлов сравнения 27 поступают их инверсные коды, в результате наименьшее по модулю из них станет наибольшим, которое и будет выделено соответствующим узлом анализа 22.Единичный сигнал с выходаблока 5 выбора экстремального числа поступает на соответствующий вход первой группы о входов ключей блока 4 :(фиг. 1 и ь), поэтому сработает один из ключей элементов 2 О И, 21 И - пусть это будет элемент И 22, Это означает, что из трех чисел , О 04, которые поступили на входы2 Зм блока 5 выбора экстремального числа через блок памяти 7 от аналого-циф. рового преобразователя б, максимальным положительным числом оказалось число 024, соответствующее модели ветви 12, расположенной между узлами 1340 и 14 4 (фиг. 2). Следовательно для дальйейшего анализа на предмет выбора в нем экстремального числа избран. узел 134 или, что то же самое, узел 4 графа задачи коммивояжера (фиг. 8), 45 так же как раньше (т.е, на первом шаге) анализировался узел 132 (или узел 2 графа задачи коммивояжера, фиг. 8) .50Шестой импульс на входе сдвигового регистра 38 вызывает "1" на еготретьем выходе и соответственно навтором входе элемента 40 ИЛИ на еговыходе, на входе блока памяти 8,отчего на четвертом выходе группы Нвыходов блока памяти 8 (фиг, 1 и.б)также появится "1". Она ке появитсяодновременно на 3 -входе триггера 36и на входе Ю четвертого столбца блока индикации 11 ( фиг. 1 и ь), в результате чего клетка 31 4 "загорит-.1ся", т.е. в ней зажжется светодиод 34,Таким образом, будет закончено формирование первого звена будущего гамильтонова контура, т.е. осуществ лен переход от узла 2 к узлу 4 графа задачи коммивояжера (Фиг, Ь) .Седьмой импульс на входе регистра сдвига 38 уровней вызовет "1" на его четвертом выходе, откуда она подается на С-входы триггеров Зь в результате чего на выходах триггеров Зь -36 установится "0", так как на их Э-входах присутствует "0", а на выходе триггера Зь установится "1", так как на его 2 -вход подается "1" с четвертого выхода группы Н выходов блока памяти 8 (фиг. 6.Восьмой импульс на входе регистра сдвига 38 вызовет "1" на его пятом выходе, которая перепишется на его шестой выход через его второй вход.Поскольку на первом входе элемента 45 И присутствует "1" с выхода триггера Зь, то от генератора импульсов 43 будут продолжать подаваться импульсы на регистр сдвига 38, который начнет второй цикл переключения логической "1" для обследования узла 134 и выбора в нем экстремального числа, затем работа устройства повторяется. Как только устройство перейдеТ к анализу последнего узла 13, то к этому моменту все инцидентные ему модели 12 ветвей будут разорваны и на выходе 1 блока 5 выбора экстремального числа будет нулевой сигнал, который через блок памяти 8 подается на 2 -входы триггеров Зб; в результате на выходах триггеров Зь окажутся нулевые сигналы, которые через элемент 39 ИЛИ запрут элемент 45 И, отключив тем самым регистр сдвига 38, работа устройства прекратится, С блока индика- ции 11 по зажженным клеткам 31 определяют топологию выделенного гамильтонова контура. Затем кнопкой 35;выбирают следующий стартовый узел, (гася при этом через ключ 4 ь(фиг.б) на блоке индикации 11 все зажженные клетки 31 для которого описанным образом отыскивается свой гамильтонов контур.С помощью кнопок переключателя 35 назначают в качестве стартовых узлов все узлы 13 в модели 1 графа конкретной задачи коммивояжера, для каждого стартового узла устройствоотыскивает гамильтонов контур, так что Формируется П гамильтоновых контуров(п - размерность решаемой задачи коммивояжера), из которых отбирают минимальный контур по минимальной сумме межузловых расстояний. Затем на модели 1 графа задачи коммивояжера (фиг. 2) с помощью резисторов 16, управляемых синхронно, регулируют напряжение на каждой паре узлов 13 и 14 при включенных ключах 17 так, чтобй суммарное напряжение на парах указанных узлов (которое можно суммировать, например, с помощью операционного усилителя, а контролироватьс помощью цифрового вольтметра) былоравно длине найденного на предыдущей итерации минимального гамильтонова контура. После этогоповторяют еще одну итерацию формирования и гамильтоновых контуров,среди которых также отыскивают минимальный гамильтонов контур. Есливновь найденный минимальный контурравен первому минимальному гамильто нову контуру, то решение оканчиваютесли второй гамильтонов контур оказался меньше первого контура, товыполняют следующую итерацию формирования д гамильтоновых контуров. Устройство для решения задачи коммивояжера благодаря наличию новых блоков и связей между ними позволяет уменьшить время получения решения задачи коммивояжера.