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

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

Иллюстрации

Показать все

Реферат

 

1. УСТРОЙСТВО РЕШЕНИЯ ЗАДАНИ КОММИВОЯЖЕРА, содержащее блок модели графа,состоящую из моделей ветвей , соединенных между собой в соответствии с топологией графа,через Начальные и конечные узлы, инцидентные соответствующим расщепленным вершинам графа. отличающеес я тем, что, с целью повышения быстродействия , в устройство дополнительно введены первый, второй и Третий блоки ключей, аналого-цифровой преобразователь, первый, второй и третий блоки памяти, блок выбора экстремального числа, блок индикации , блок управления, состоящий из сдвоенных кнопочных переключателей , первого и второго генераторов импульсов, первого и второго элементов ИЛИ, первого и второго .ключей элемента И, триггеров, коммутатора согласующих диодов, Ъричем первые контакты сдвоенных кнопочных переключателей через согласующий резистор соединены с выходом первого источника постоянного напряжения , вторые контакты сдвоенных кнопочных переключателей объединены и соединены с выходом первого генератора импульсов, третьи контакты сдвоенных кнопочных переключателей соединены с первыми входами .соответствующих триггеров и через первую группу согласующих диодов подключены к входу первого ключа, четвертые контакты кнопочных переключателей соединены с вторыми входами соответствующих триггеров и через согласующие диоды - с первым выходом сдвигового регистра, выходы триггеров подключены к входам коммутатора и через первый элемент ИЛИ - к управляющему входу первого элемента И, информационный вход которого подключен к выхо ду второго генератора импульсов, выход первого элемента И подключен к Q входу сдвига сдвигового регистра, S9 второй и третий выходы которого сое (Л динены с входами второго элемента ИЛИ вход второго ключа подключен к выходу второго источника постоянного напряжения, входы второго элемента И подключены к первой группе информационных выходов первого блока памяти, входы управления адресом записи которого соединены с группой выходов сдвигового регистра, выход второго ключа соединен с управляющими входами моделей ветвей, информационные выходы которых соединены соответственно с информационными входами первого и второго блока ключей , управляющие входы которых соединены соответственно с выходами триггеров и группой выходов сдвигового регистра, выходы коммутатора подключены к управляющим входам третьего блока ключей, информационные входы которого соединены с выходами блока выбора экстремального числа, управляющий вход которого подключен к выходу второго элемента И, выходы первого и второго блока ключей подключены к входам аналого-цифрового преобразователя , выходы которого соединены с информационными входами пер

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU„„

3(51) G 06 G 7 48

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21 ) 3558668/18-24 (22) 28. 02. 83 (46 ) 30. 05. 84. Бюл. М 20 (72 ) A. Г. Додонов, A. M.Ùåòèíèí, В.В.Белобабов, В. И. Рябцев и Ю.С.Васильев (53) 681.333(088.8) (56 ) 1. Бычкова Л.С. Решение задачи коммивояжера на специализированных аналоговых устройствах.-Кн.Приборс э строение, средства автоматизации и системы. управления. M., "Наука", 1967, с. 156-163.

2. Авторское свидетельство СССР

Р 227716, кл. G 06 G 7/48, 25.09.68. (прототип). (54)(57) 1. УСТРОЙСТВО РЕШЕНИЯ ЗАДАНН КОММИВОЯЖЕРА, содержащее блок модели графа, состоящую из моделей ветвей, соединенных между собой в соответствии с топологией графа, через начальные и конечные узлы, инцидент-. ные соответствующим расщепленным вершинам графа, о т л и ч а ю щ е ес я тем, что, с целью повышения.быстродействия, в устройство дополнительно введены первый, второй и третий блоки ключей, аналого-цифровой преобразователь, первый, второй и третий блоки памяти, блок выбора экстремального числа, блок индикации, блок управления, состоящий из сдвоенных кнопочных переключателей, первого и второго генераторов импульсов, первого и второго элементов ИЛИ, первого и второго .ключей элемента И, триггеров, коммутатора согласующих диодов, причем первые контакты сдвоенных кнопочных переключателей через согласующий резистор соединены с выходом первого источника постоянного напряжения, вторые контакты сдвоенных кнопочных переключателей объединены и соединены с выходом первого гене- ратора импульсов, третьи контакты сдвоенных кнопочных переключателей соединены с первыми входами .соответствующих триггеров и через первую группу согласующих диодов подключены к входу первого ключа, четвертые контакты кнопочных переключателей соединены с вторыми входами соответствующих триггеров и через согласующие диоды — с первым выходом сдвигового регистра, выходы триггеров подключены к входам коммутатора и через первый элемент ИЛИ вЂ” к управляющему входу первого элемента И, информационный вход которого подключен к выхо ду второго генератора импульсов, выход первого элемента И подключен к входу сдвига сдвигового регистра, второй и третий выходы которого соединены с входами второго элемента

ИЛИ вход второго ключа подключен к выходу второго источника постоянного напряжения, входы второго элемента

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

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

Изобретение относится к вычислительной технике и может быть применено для решения задачи коммивояжера, а также ряда задач, сводящихся к ней., Из-,åñòíà электрическая модель гра- 5 фа, в которой каждой дуге графа соответствуют последовательно соединенные сопротивление и диод (модель дуги); соединение элементов модели графа, т.е. моделей дуг, производится в соответствии с топологией графа; в узлах размещены переключакщие схемы, количество которых в хайдом узле равно числу пар вершин, соединенных между собой хотя бы одной дугой P1) .

Недостатком известного устройства является высокая трудоемкость реше- о ния задачи коммивояжера, определяемая необходимостью полного переброса возможных состояний переключакщих схем с целью выбора из этого множества состояний состояния, адекватного решению задачи коммивояжера. Эта тру4Ъемкость существенно повышается для симметричной задачи коммивоя- 25 жера.

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

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

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

Цель изобретения — повышение быстродействия.

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

Кроме того, блок модели графа выполнен в виде измерительных резисто ров, первые выводы которых подключеб5 четвертые контакты сдвоенных кнопоч- ных переключателей соединены со вторыми входами соответствующих триггеров и через согласующие диоды — с первым выходом сдвигового регистра, выходы триггеров подключены к входам коммутатора и че . з первый элемент

ИЛИ вЂ” к управляющему входу первого элемента И, информационный вход которого подключен к выходу второго генератора:импульсов, выход первого 10

|элемента И подключен к входу сдвига сдвигового регистра, второй и третий выходы которого соединены с входами второго элемента ИЛИ, вход второго ключа подключен к выходу второго ис- 15 точника постоянного напряжения, выходы второго элемента И подключены к первой группе информационных выходов первого блока памяти, входы управления адресом записи которого соедине- о ны с группой выходов сдвигового регистра, выход второго ключа соединен с управляющими входами моделей ветвей, информационные выходы которой соединены соответственно с инфор-у5 мационными входами первого и второго блока ключей, управляющие входы которых соединены соответственно с выходами триггеров и группой выходов сдвигового регистра, выходы коммутатора подключены к управляющим третьего блока ключей, информационные входы которого соединены с выходами блока выбора экстремального .числа, управляющий вход которого подключен к выходу второго элемента И, выходы первого и второго. блока ключей подключены к входам аналого-цифрового преобразователя, выходы которого сое динены с информационными входами первого блока памяти, четвертый выход сдвигового регистра подключен к входу разрешения записи первого блока памяти, выходы которого соединены с информационными входами блока выбора экстремального числа, выходы 45 третьего блока ключей подключены к информационным входам второго блока памяти,. вход разрешения записи которого соединен с выходом второго элемента ИЛИ, выходы триггеров подклю- 5О чены к информационным входам третьего блока памяти, вход разрешения записи которого подключен к второму выходу сдвигового регистра, выходы второго и третьего блоков памяти соединены соответственно с первой и второй группой входов блока индикации, управляющий вход которого соединен с выходом первого ключа, выходы второго блока памяти соединены с первыми входами соответствующих триггеров. ны к информационным входам первых ключей в соответствующих моделях ветвей, выходы которых подключены к входам управляемых источников напряжения в соответствующих. моделях ветвей, выходы которых соединены с информационными входами вторых ключей в соответствующих моделях ветвей, первые и вторые выводы измерительных резисторов подключены к информационным выходам блока модели графа, соответствующие пары начальных и конечных узлов соединены между собой через последовательно соединенные ключ и переменный резистор.

На фиг. 1 изображена блок-схема устройства; на фиг. 2 — модель графа задачи. коммивояжера на четыре узла; на фиг. 3 — модель ветви; на фиг. 4 — блок выбора экстремального числа; на фиг. 5 — схема соединений узлов сравнения и элементЬв ИЛИ блока выбора экстремального числа (схема соединений представлена для четырех четырехразрядных чисел); на фиг. 6 блок управления во взаимодействии с блоком ключей, двумя блоками памяти.и блоком индикации; на фиг.7ячейка блока индикации; на фиг. 8 граф задачи. коммивояжера на четыре

v зла.

Предлагаемое устройство (фиг. 1) состоит из модели 1 графа задачи коммивояжера, блоков ключей 2-4, блока 5 выбора экстремального числа, аналого-цифрового преобразователя 6, блоков памяти 7-9, блока управления 10, .блока индикации 11.

Модель 1 графа задачи коммивояжера (фиг. 2) состоит из моделей 12 ветвей, начальных узлов 13, конечных узлов 14 („ =1, 2, ..., л), измерительного резистора 15 и переменного резистора 16 и ключей 17. Каждая модель ветви содержит ключи 18 и 182, управляемый источник напряжения 19 (фиг. 3). Блок 4 ключей состоит из элементов И 20; и 21> (< =2,3,... Д, =1,2,..., М -1, где И вЂ” максимальная размерность устройства). Блок выбора экстремального числа 5 содержит (фиг. 4) 0 = К -1 узлов 22 анализа (К=1,2,..., Д, каждый из которых состоит из 5 = в-1 (m — число двоичных разрядов) сравниваемых чисел с учетом знаковых разрядов, полусумматорой 23, элемента 24 НЕ, элемента 25 И, щ элементов 26 ИЛИ, tyl поразрядных узлов 27 сравнения; каждый поразрядный узел 27 сравнения содержит эле.— мент 28 И, элемент 29 ИЛИ, элемент

30 НЕ.

Блок индикации 11 состоит из N N клеток 31 которые составляют ряды и столбцы j матрицы, причем при клетка 31 является пустой. Каждая заполненная клетка 31," состоит (фиг. 7) 1095201 из элемента 32 И, ) -триггера 33 и светодиода 34. В блоке индикации 11 в каждом столбце первые входы непус-ых клеток 31 соединены между собой и подключены к одному из входов первой группы М входов блока индикации 11 фиг. 6), в каждом ряду вторые входы непустых клеток 31 соединены между собой и подключены к одному из входов второй группы П входов блока индикации 11 (фиг. 6), третьи входы непустых . клеток 31 соединены между собой и подключены к входу rr„ блока индикации.

Блок управления 10 (фиг. 6 ) (услов. но показан для устройства с размер- 15 ностью и =4 ) состоит из сдвоенных кнопочных переключателей 35„; 1) -триггеров 36,; коммутатора 37, сдвигового регистра 38, элемента HJIH 39; элемента ИЛИ 40, элемента И 41, клю- 20 ча 42, генераторов (прямоугольных) импульсов типа "меандр" 43 и 44; элемента И 45, источников постоянного напряжения 46 и 47, согласующих диодов 48, согласующего резистора 49.25

Устройство работает следующим образом.

Допустим, что максимальная размер1 ность устройства равна 4, т. е. М =4, и задача решается для графа задачи коммивояжера также с размерностью й=4. В исходном положении все ключи

17 (<;;r. 2) разомкнуты, все модели 12 ветвей также разомкнуты (при помощи своих ключей 18), а на их источни- 35 ках постоянного напряжения 19 выставляют напряжения Е „, пропорциональные межузловым расстояниям решаемой задачи коммивояжера. При помощи ключа 42 блока управления 10 (фиг. 6) 4g подается управляющий сигнал на ключи 18 моделей ветвей 12, что обеспе; чивает их включение и в конечном счете — сборку модели 1 графа задачи коммивояжера. Поскольку модель 1 графа задачи коммивояжера во включен-» ном состоянии представляет собой некоторую линейную разветвленную электрическую цепь, то в ней на основании закона Кирхгофа произойдет такое распределение токов и напряжений, что одни модели ветвей 12 будут выпопнять функцию активных источни- . ков энергии, а другие модели 12 ветвей — функцию пассивных источниКов энергии: Ц =E„ + p„ q<, где 0;напряжение с соответствующим знаком (+) на некотором узле 14, относительно соответствующего узла 13„ (фиг. 2)

Š— первоначальное выставленное напряжение на 1 -и источнике 19 напряже- 60

1 ния (фиг. 3); г„— внутреннее сопротивление -й модели ветви 12 с учетом сопротивления 15 (фиг. 2); — ток в -й ветви (знак второго

1 слагаемого в приведенной формуле за- 65 висит от направления тока по ветви).

Легко доказать, что минимальному гамнльтонову контуру в.модели 1 графа задачи коммивояжера в установившемся режиме соответствует максимальное положительное приращение напряжения;

-e vnox . Решение задачи коммивояжера на предложенном устройстве сводится к отысканию гамильтонова контура с максимальным суммарным положительным приращением напряжения контура- 2г„, „= таю. Для этого кратковременно нажимают любую кнопку переклю; чателя 35» (фиг. 6) например, кнопку переключателя 35, выбирая тем самым в качестве стартового узла в будущем гамильтоновом контуре узла 13 в модели 1 графа (фиг. 2), или, что то же самое, узел 2 — в графе задачи коммивояжера (фиг. 8). После нажатия кнопки переключателя 35, через ее первый и четвертый контакты подается логическая "1" от первого источника напряжения, которая записывается на выходе триггера 362 за счет подачи меандра на его С-вход от генератора 44 импульсов (фиг. 6). Эта "1" появляется на одном из выходов второй группы g выходов блока 10 управления и соответственно на одном из входов второй группы 1 входов блока ключей 2, отчего сработает его соответствующий ключ (реле) и подключит узел 13 к первому (отрицатель2 ному ) входу аналого-цифрового преобразователя 6, а также отключит разорвет) через соответствующие

1 лючи 18 (фиг. 3) те модели ветвей 12, оторые подсоединены к узлу 14,. эта же "1" появляется на одном из выходов первой группы hi выходов бло-. ка 10 управления и соответственно на одном из входов группы N входов . блока памяти 9 ((фиг. 1,6); эта же

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

6 выходов @тока 10 управления — на вторые е входы соответствующих элементов 20, И и 21 И с индексом > =1,3.,4, подготавливая будущее срабатывание одного из них в результате ожидаемого появления на нем до-полнительной "1" от блока 5 выбора экстремального числа; эта же "1" появляется на одном из входов элемента 39 ИЛИ, затем - íà .его выходе и на первом входе элемента И 45, отчего импульсы от генератора 43 импульсов начнут поступать на вход сдвигового регистра 38 и заставят его работать в режиме переключателя . Первый импульс от генератора импульсов

43 переводит "1" с шестого выхода

1 095 201

10 сдвигового регистра 38 на первый выход его группы выходов, поэтому она появляется и на первом выходе группы (выходов блока 10 управления; эта "1" поступит соответственно на первый вход второй группы входов блока ключей 3 и на первый вход второй группы Ф входов блока памяти 7, в результате чего соответствующий ключ (реле) блока ключей 3 подключит к второму.(положительному1 входу аналого-цифрового преобразователя 6 начальный полюс Н модели. 12 ветви, расположенной между узлами 13г и 14<, подавая тем самым на аналого-цифровой преобразователь 6 напряжение с 15 соответствующим знаком (+) с соответствующего резистора 15 (фиг. 2), которое преобразуется в аналого-цифровом преобразователе 6 в некоторое число аг в двоичном коде, котоРое за-20 пишется в первом регистре блока памяти 7. Это число может быть либо положительным, либо отрицательным.

После прихода второго импульса на вход регистра сдвига 38 от генератора импульсов 43 появятся -"1" на втором выходе группы и втором выходе группы Р выходов регистра сдвига 38, а следовательно, и блока 10 управления. Одна из этих "1" заставит срабо->0 тать второй ключ блока ключей 2 и подключить к аналого-цифровому преобразователю 6 резистор 15 (фиг. 2), расположенное между узлами 13 и 14, а вторая "1" заставит второй регистр блока памяти 7 записать второе число которое окажется на выходе аналого-цифрового преобразователя 6.

После прихода третьего импульса на вход регистра сдвига 38 уровней в третьем регистре блока памяти 7 будет 40 записано число Ог<, равное в двоичном коде напряжению на резисторе 15, . расположенного между узлами 13 и 14 (фиг. 2). Четвертый импульс на входе сдвигового регистра 38 вызовет "1" на 45 ,первом выходе сдвигового регистра 38 и одновременно на входе узла блока памяти 9, а через элемент 40 ИЛИ вЂ” и на входе И, блока 8 памяти (фиг. 1 и 6) в результате на всех выходах 50 группы H выходов блока памяти 8 установится "0", а на втором выходе группы и выходов блока памяти 9 и соответственно на втором входе второй группы и входов блока индикации 11 55 ! установится "1", а это приведет к тому, что все непустые клетки 31 второго ряда блока 11 (фиг. 6 и 7) будут подготовлены к срабатыванию, т.е. к зажиганию некоторого свето- 60 диода 34. Таким образом, после трех

"1" на выходе регистра сдвига 38 в .блоке памяти 7 окажется записанным массив из трех чисел аг,, ozz, аг ° иэ которых надо выбрать экстремальное 65 число. Массив чисел может быть либо положительный, либо отрицательным, либо смешанным; в первом и третьем случае надо из массива выбрать максимальное положительное .число, а во втором случае — минимальное по модулю. Эту функцию выполняет блок 5 выбора экстремального числа (фиг. 4 и 5), на входы м которого сигналы с выходов регистров блока памяти 7, подаются через элементы И блока памяти 7 (т.е. через общепринятую схему снятия информации ) после подачи на эти схемы пятой "1" с шестого ш выхода блока управления 10 пятая "1 на втором 4l выходе сдвигового регистра 38, а следовательно, и на шестом ц. выходе блока управления 10 появляется после подачи на вход сдвигового регистра 38 пятого импульса от генератора импульсов 4. При этрм в случае отрицательного массива чи.сел логическая "1" со знаковых разрядов, поступая на элемент И 41 блока управления 10, вызывает "1" на первом с выходе (фиг. 1 и 6) блока управления 10, которая поступает на вторые входы полусумматоров 23 узлов анализа 22 блока 5 выбора экстремального числа (фиг. 4), что вызывает инверсию кодов чисел на входах узлов

27 сравнения, в результате чего минимальное по модулю число массива чисел становится после полусумматоров 23 максимальным числом. При сравнении чисел их двоичные коды поступают на входы Al блока 5 выбора экстремального числа; старшие разряды чисел поступают íà уп-1) узлы сравнения 27 (фиг. 4), а знаковые разряды чисел поступают на л узлы сравнения 27. В узлах сравнения 27 с инвертированным единичным значением знаковых разрядов кодов сравниваемых чисел устанавливается "1" на выходе элементов 29 ИЛИ. В узлах сравнения

27> с инвертированным нулевым значением знаковых разрядов кодов сравниваемых чисел устанавливается "0" на выходе элементов 29 ИЛИ, так как на их первых входах имеется "0" с выхода элементов HE 24 и "0" - на их вторых входах с выхода элементов 30

НЕ, ибо на входе последних существует

"1" при наличии инвертированной "1" на входе узла сравнения 27 хотя бы в одном узле анализа 22. Нулевой сигнал с выхода элементов ИЛИ 29 запрещает все элементы И 28, расположенные в узлах -27,„ « 27 z, 27 сравнения, и элементы и 25 соответствующих узлов 22; анализа, исключая их участие в формировании выходного сигнала на соответствующих вы ходах Ь блока 5 выбора экстремального числа (фиг. 41. При отсутствии чисел с единичным значением данного

1095201

10 разряда единичное значение выхода элемента ИЛИ 29 во всех узлах анализа 22 устанавливается по цепи: элемент 28 И, элемент 26 ИЛИ, элемент 30

НЕ, второй вход элемента 29 ИЛИ и обеспечивает анализ содержимого следующего разряда чисел.

После установления сигналов на выходах элементов 28 И, соединенных со старшими каналами, работа логических элементов в других каналах аналогич- 10 на. Единичное значение на выходе элемента 25 И, а следовательно, и на выходе ь блока 5 выбора экстремального числа установится только в том узле анализа 22;, который ни в одном узле сравнения 27 не содержит элемент 29

ИЛИ с нулевым значением на выходе, т.е. в узле анализа 22 с максимальным числом на его входах М . При наличии на выходах р блока 7 памяти только отрицательных чисел, на входы узлов сравнения 27 поступают их инверсные коды, в результате наименьшее по модулю из них станет наибольшим, которое и будет выделено соответствующим узлом анализа 22.

Единичный сигнал с выхода блока 5 выбора экстремального числа поступает на соответствующий вход первой группы О входов ключей блока 4

:(фиг. 1 и ь), поэтому сработает один из ключей элементов 20„ И, 21 И вЂ” пусть это будет элемент И 22 .

Это означает, что из трех чисел д, 1

9 Ol >л, которые поступили на входы

23 м блока 5 выбора экстремального чис-35 ла через блок памяти 7 от аналого-цифрового преобразователя 6, максимальным положительным числом оказалось число 0>л, соответствующее модели ветви 12, расположенной между узлами 13 40 и 14 4 (фиг. 2). Следовательно для дальйейшего анализа на предмет выбора в нем экстремального числа избран. узел 134 или, что то же самое, узел 4 графа задачи коммивояжера (фиг. 8), так же как раньше (т.е. на первом шаге) анализировался узел 13< (или узел 2 графа задачи коммивояжера, фиг. 8) .

Шестой импульс на входе сдвигового регистра 38 вызывает "1" на его третьем выходе и соответственно на втором входе элемента 40 ИЛИ на его выходе, на входе блока памяти 8, отчего на четвертом выходе группы Н выходов блока памяти 8 (фиг. 1 и.б) также появится "1". Она >ке появится одновременно на 3 -входе триггера 36 и на входе kl четвертого столбца блока индикации 11 (фиг. 1 и 6), в ре- 60 зультате чего клетка 31> 4 "загорит-.

1 ся", т.е. в ней зажжется светодиод 34.

Таким образом, будет закончено формирование первого звена будущего гамильтонова контура, т.е. осуществ- 65 лен переход от узла 2 к узлу 4 графа задачи коммивояжера (фиг. Ь) .

Седьмой импульс на входе регистра сдвига 38 уровней вызовет "1" на его четвертом выходе, откуда она подается на С-входы триггеров Зь,, в результате чего на выходах триггеров

Зь„ -36 установится "0", так как на их 3-входах присутствует "0", а на выходе триггера Зьл установится "1", так как на его 3 -вход подается "1" с четвертого выхода группы Н выходов блока памяти 8 (фиг. 6).

Восьмой импульс на входе регистра сдвига 38 вызовет "1" на его пятом выходе, которая перепишется на его шестой выход через его второй вход.

Поскольку на первом входе элемента 45 И присутствует "1" с выхода триггера Зь, то от генератора импульсов 43 будут продолжать подаваться импульсы на регистр сдвига 38, который начнет второй цикл переключения логической "1" для обследования узла 134 и выбора в нем экстремального числа, затем работа устройства повторяется. Как только устройство перейдеТ к анализу последнего узла 13Ä, то к этому моменту все инцидентные ему модели 12 ветвей будут разорваны и на выходе 3 блока 5 выбора экстремального числа будет нулевой сигнал, который через блок памяти 8 подается на 2 -входы триггеров 36„ ; в результате на выходах триггеров Зь„. окажутся нулевые сигналы, которые через элемент 39 ИЛИ запрут элемент 45 И, отключив тем самым регистр сдвига 38, работа уст-. ройства прекратится. С блока индика ции 11 по зажженным клеткам 31 определяют топологию выделенного гамильтонова контура. Затем кнопкой 35; выбирают следующий стартовый узел, (гася при этом через ключ 4ь (фиг.6) на блоке индикации 11 все зажженные клетки 31 для которого описанным образом отыскивается свой гамильтонов контур.

С помощью кнопок переключателя 35 назначают в качестве стартовых узлов все узлы 13 в модели 1 графа конкретной задачи коммивояжера, для каждого стартового узла устройство отыскивает гамильтонов контур, так что формируется П гамильтоновых контуров(п — размерность решаемой задачи коммивояжера), из которых отбирают минимальный контур по минимальной сумме межузловых расстояний. Затем на модели 1 графа задачи коммивояжера (фиг. 2) с помощью резисторов 16, управляемых синхронно, регулируют напряжение на каждой паре узлов 13„ и 14„ при включенных ключах 17 так, чтобй суммарное напряжение на парах указанных узлов (которое можно суммировать, например, с помощью операци1095201

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

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

1095201

1I39520 ! рис. 5

1095201 И)

Cej

Составитель A. Колчин

Редактор М. Недолуженко Техред А.Ач Корректор О.Тигор

Заказ 3600/32 Тираж 699 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", г.Ужгород, ул.Проектная, 4