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

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

входами соответствующих триггеров .

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

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

Изобретение относится к вычислительной технике и может быть примен но для решения задали коммивояжера, а также ряда задач, сводящихся к ней И 7естна электрическая модельгр фа, в которой каждой дуге графа соответствуют последовательно соедине ные сопротивление и диод (модель дyги)J соединение элементов модели графа, т.е. моделей дуг, производится в соответствии с топологией графа; в узлах размещены переключающие схемы, количество которых в каЗщом узле равно числу пар вершин, соединенных между собой хотя бы одной дугой 1 . Недостатком известного устройства является высокая трудоемкость решения задачи коммивояжера, определяемая необходимостью полного переброса возможных состояний переключающих схем с целью выбора из этого множества состояний состояния, адекватного решению задачи коммивояжера. Эта труд 2 емкость существенно повышается для симметричной задачи коммивоя.жера. Наиболее близким по технической сущности к предложенному является устройство для решения задачи коммквояжера, содержащее модель графа задачи коммивояжёра, состоящую из моде лей ветвей, соединенных медду собой в соответствии с топологией графа задачи коммивояжера, и из моделей вершин графа згщачи коммивояжера, |ПОдключенных к соответствующим моделям ветвей 23 . Недостатком известного устройства является низкое быстродействие устройства при решении задачи коммивояжера. Цель изобретения - повышение быстродействия. Поставленная цель достигается тем, что в устройство для решения задачи коммивояжера, содержгацее блок моде- ,. ли графа задачи коммивояжера, состоящую из моделей ветвей, соединенныхсогласно топологии графа через начальные и конечные узлы, инцидентные соответствующим расщепленным весядинам графа, дополнительно введены первый, второй и третий блоки ключей, аналого-цифровой преобразова- . тель, первый, второй и третий блоки памяти, блок эыбора экстремального числа, блок индикации, блок управления, состоящий из сдвоенных кнопочных переключателей, первого и второго генератора импульсов, первого и второго элементов ИЛИ, первого и второго ключей, элемента И, триггеров, коммутатора, согласующих диодов. причем первые контакты сдвоенных кнопочных переключателей через согласующий резистор соединены с первым источником постоянного напряжения, вторые контакты сдвоенных переключателей объединены и.соединены с выходом первого генератора импульсов, третьи контакты с/}военных кнопочньох переключателей соединены с первыми входами соответствующих триггеров и через первую группу согласующих диодов подключен к входу первого ключа. четвертые контакты сдвоенных кнопочных переключателей соединены со вторыми входами соответствующих триггеров и через согласующие диоды - с первым выходом сдвигового регистра, выходы триггеров подключены к входам коммутатора и первый элемент ИЛИ - к управляющему входу первого элемента И, информационный вход кото рого подключен к выходу второго генератора импульсов, выход первого элемента И подключен к входу сдвига сдвигового регистра, второй и третий выходы которого соединены с входами второго элемента ИЛИ, вход второго ключа подключен к выходу второго ис точника постоянного напряжения, выходы второго элемента И подключены первой группе информационных выходо первого блока памяти, входы управления адресом записи которого соединены с группой выходов сдвигового регистра, выход второго ключа соединен с управляющими входами моделей ветвей, информационные выходы которой соединены соответственно с инфор ,мационными входами первого и второго блока ключей, управляющие входы кото рых соединены соответственно с выходами триггеров и группой выходов сдвигового регистра, выходы коммутатора подключены к управляющим третье го блока ключей, информационные входы которого соединены с выходами блока выбора экстремального числа, управляющий вход которого подключен к выходу второго элемента И, выходы первого и второго, блока ключей подключены к входам аналого-цифрового преобразователя, выходы которого сое динены с информационными входами первого блока памяти, четвертый выход сдвигового регистра подключен к входу разрешения записи первого блока памяти, выходы которого соединены с информационньши входами блока выбора экстремального числа, выходы третьего блока ключей подключены к информационным входам второго- блока памяти,, вход разрешения записи которого соединен с выходом второго элемента ИЛИ, выходы триггеров подключены к информационным входам третьего блока памяти, вход разрешения записи которого подключен к второму выходу сдвигового регистра, выходы второго и третьего блоков памяти соединены соответственно с первой и второй группой входов блока индикации, управляющий вход которого соединен с выходом первого ключа, выхода второго блока памяти соединены с первыми входами соответствующих триггеров. Кроме того, блок модели графа вы полнен в виде измерительных резисто ров, первые выводы которых подключе вы к информационным входам первых ключей в соответствующих моделях ветвей, выходы которых подключены к входам управляемых источников напряжения в соответствуюцих.моделях ветвей, выходы которых соединены с информационными входами вторых ключей в соответствующих моделях ветвей, первые и вторые выводы измерительных резисторов подключены к информационHfJM выходам блока модели графа/ соответствующие пары начальных и конечных узлов соединены между собой через последовательно соединенные ключ и переменный резистор. На фиг. 1 изображена блок-схема устройства; на фиг. 2 - модель графа задачи, коммивояжера на четыре узла; на фиг. 3 - модель ветви; на фиг. 4 - блок выбора экстремального числа; на фиг. 5 - схема соединений узлов сравнения и элементТ)в ИЛИ блока выбора экстремального числа (схема соединений представлена для четырех четырехразрядных чисел); на фиг. б блок управления во взаимодействии с блоком ключей, двумя блоками памяти и блоком индикации; на фиг.7ячейка блока индикации; на фиг. 8 граф задачи- коммивояжера на четыре узла. Предлагаемое устройство (фиг. l) состоит из модели 1 графа задачи коммивояжера, блоков ключей 2-4, блока 5 выбора экстремального числа, аналого-цифрового преобразователя 6, блоков памяти 7-9, блока управления 10, .блока индикации 11. Модель 1 графа задачи коммивояжера (фиг. 2) состоит из моделей 12 ветвей, начсшьных узлов 13, конечных узлов 14 (, 2, ...,п, измерительного резистора 15 и переменного резистора 16 и ключей 17. Каждая модель ветви содержит ключи 18 и ISj, управляемый источник напряжения 1У (фиг. 3. Блок 4 ключей состоит из элементов И 20 и 21J (i 2,3,...,N, 1,2,..., N-1, где N - максимальная размерность устройства). Блок выбора экстремального числа 5 содержит (фиг. N-1 узлов 22 анализа ,2,..., , каждый из которых состоит из 5 т-1 (т - число двоичных разрядов) сравниваемых чисел с учетом знаковых разрядов, полусумматорой 23, элемента 24 НЕ, элемента 25 И, m элементов 26 ИЛИ, П1 поразрядных узлов 27 сравнения; каждый поразрядный узел 27 сравнения содержит элегмент 28 И, элемент 29 ИЛИ, элемент 30 НЕ. Блок индикации 11 состоит из N-N клеток которые составляют ряды i и столбцы j матрицы, причем при клетка 31 является пустой. Каждая заполненная клетка 31,, состоит (фиг. 7) из элемента 32 H,D -триггера 33 и светодиода 34. В блоке индикации 11 в каждом столбце первые входы непус клеток 31 соединены между собой и подключены к одному из входов пер вой группы И входов блока индикации 11 (фиг. б) , в каждом ряду вторые входы непустых клеток 31 соедин ны между собой и подключены к одному из входов второй группы П входов бл ка индикации 11 (фиг. 61, третьи входы непустых клеток 31 соединены между собой и подключены к входу m блока индикации. Блок управления 10 (фиг. 6 ( усл но показан для устройства с размеркостью N 4 ) состоит из сдвоенных кнопочных переключателей 35 ;D -триг геров 36; ; комму-татора 37, сдвигово го регистра 38, элемента ИЛИ 39; элемента ИЛИ 40, элемента И 41, клю ча 42, генераторов (прямоугол-ьных) импульсов типа меандр 43 и 44; элемента И 45, источников постоянного напряжения 46 и 47, согласующих диодов 48, согласующего резистора 49 г , , Устройство работает следующим образом. Допустим, что максимальная размер ность устройства равна 4, т.е.М 4, и задача решается для графа задачи коммивояжера также с размерностью . В ИСХОДНО14 положении все ключи 17 (Сг/г. 2 разомкнуты, все модели 1 ветвей также разомкнуты (при помощи своих ключей 18, а на их источниках постоянного напряжения 19 выставляют над1ряжения Е- ,пропорциональные межузловым расстояниям решаемой задачи коммивояжера. При помощи ключа 42 блока управления 10 (фиг.. 6) подается управляющий сигнал на ключи 18 моделей ветвей 12, что обеспе-; чивает их включение и в конечном, счете - сборку модели 1 графа задачи коммивояжера. Поскольку модель 1 графа задачи коммивояжера во включен ном состоянии представляет собой некоторую линейную разветвленную электрическую цепь, то в ней на осно вании закона Кирхгофа произойдет такое распределение токов и напряжений, что одни модели ветвей 12 будут выпо5 нять функцию активных источников энергии, а другие модели 12 ветвей - функцию пассивных источников энергии: L1; Е, + Г Ij ; где U; напряжение с соответствующим знаком (±} на некотором узле 14 относитель но соответствующего узла 13 (фиг. 2 Е-- первоначальное выставленное напряжение на 1 -м источнике 19 напряжения (фиг. 3) ; г; - внутреннее сопротивление i -и модели ветви 12 с учетом сопротивления 15 (фиг. 2); i;; - ток в i -и ветви (знак второго слагаемого в приведенной формуле зависит от направления тока по ветви). Легко доказать, что минимальному гамильтонову контуру в- модели 1 графа задачи коммивояжера в установившемся режиме соответствует максимальное положительное приращение напряжения; с; i; - woDi . Решение задачи коммивояжера на предложенном устройстве сводится к отысканию гамильтонова контура с максимальным суммарным положительныг/ приращением напряжения контура: г:, jli . Для этого кратковременно нажимают любую кнопку переклю,чателя 35 (фиг. 6)например, кнопку переключателя 35, выбирая тем самым в качестве стартового узла в будущем гамильтоновом контуре узла 132 в модели 1 графа (фиг. 2), или, что то же самое, узел 2 - в графе задачи коммивояжера (фиг. 8). После нажатия кнопки переключателя 35, через ее первый и четвертый контакты подается логическая 1 от первого источника напряжения, которая записывается на . выходе триггера 36 за счет подачи меандра на его С-вход от генератора 44 импульсов (фиг. 6). Эта 1 появляется на одном из выходов второй группы г выходов блока 10 управления и соответственно на одном из входов второй группы 7 входов блока ключей 2, отчего сработает его соответствующий ключ (реле) и подключит узел 13 к первому (отрицательному ) входу ;j( аналого-цифрового преобразователя 6, а также отключит (разорвет) через соответствующие КЛЮЧИ 18 (фиг. З) те модели ветвей 12, которые подсоединены к узлу появляется на одном из выэта же ходов первой группы N выходов бло-ка 10 управления и соответственно на одном из входов группы N входов блока памяти 9 ((фиг. 1,6); эта же 1 появляется на второй вертикальной шине комкутатора 37, откуда она ререходит -на его горизонтальные шины, соединенные через диодаа с второй вертикальной шиной, и дальше через coofветствующие выходаа четвертой группы е выходов 4яока 10 управления - на вторые е входы соответствующих элементов 20 И и 21j и с индексом i, j 1, 3,, 4, подготавливая будущее срабатывание одного из них в результате ожидаемого появления на нем до- . полнительной 1 от блока 5 выбора экстремального числа; эта же 1 появляется на одном из входов элемента 39 ИЛИ, затем - на .его выходе и на первом входе элемента И 45, отчего импульсы от генератора 43 импульсов начнут поступать на вход сдвигоого регистра 38 и заставят его работать в режиме переключателя. Перый импульс от генератора импульсов 43 переводит 1 с шестого выхода сдвигового регистра 38 на первый выход его группы выходов, поэтому она появляется и на первом выходе группы 6 выходов блока 10 управления эта 1 поступит соответственно на первый вход второй группы g входов блока ключей 3 и на первый вход второй группы входов блока памяти 7, в результате чего соответствующий ключ (реле) блока ключей 3 подключит к второму (положительному) входу аналого-цифрового преобразователя 6 начальный полюс Н модели. 12 ветви, расположенной между узлами IS и 14 подавая тем самым на аналого-цифровой преобразователь 6 напряжение с соответствующим знаком (+) с соответствующего резистора 15 (фиг. 2), которое преобразуется в аналого-цифровом преобразователе 6 в некоторое число 02 в двоичном коде, которое за пишется в первом регистре блока памяти 7. Это число может быть либо положительным, либо отрицательным. После прихода второго импульса на вход регистра сдвига 38 от генератора импульсов 43 появятся на втором выходе группы и втором выходе группы f выходов регистра сдвига 38, а следовательно, и блока 10 управления. Одна из этих 1 заставит срабо тать второй ключ блока ключей 2 и подключить к аналого-цифровому преоб разователю б резистор 15 (фиг. 2), ра положенное между узлами 12у и 14, а вторая 1 заставит второй регистр блока памяти 7 записать второе число А2а, которое окажется на выходе аналого-цифрового преобразователя 6. После прихода третьего импульса на вход регистра сдвига 38 уровней в третьем регистре блока памяти 7 будет |записано число Ог. / равное в двоичном коде напряжению на резисторе 15 расположенного между узлами 13„ и 14 фиг. 2). Четвертый импульс на входе сдвигового регистра 38 вызовет н .первом выходе сдвигового регистра 38 и одновременно на входе г узла блока памяти 9, а через элемент 40 ИЛИ - и на входе Ц блока 8 памяти (фиг. 1 и б , в результате на всех выходах группы н выход:ов блока памяти 8 уста новится О, а на втором выходе груп пы п выходов блока памяти 9 и соответственно на втором входе второй группы п входов блока индикации 11 установится 1, а это приведет к тому, что все непустые клетки 31 второго ряда блока 11 (фиг. б и 7) будут подготовлены к срабатыванию, т.е. к зажиганию некоторого светодиода 34. Таким образом, после трек 1 на выходе регистра сдвига 38 в блоке памяти 7 окажется записанным массив из трех чисел а 2, 24 из которых надо выбрать экстремальное число. Массив чисел может быть либо положительный, либо отрицательным, либо смешанным; в первом и третьем случае надо из массива выбрать максимальное положительное.число, а во втором случае - минимальное по модулю. Эту функцию выполняет блок 5 выбора экстремального числа (фиг. 4 и 5), на входы W которого сигналы с выходов регистров блока памяти 7, подаются через элементы И блока памяти 7 (т.е. через общепринятую схему снятия информации ) после подачи на эти схемы пятой 1 с шестого и выхода блока управления 10 пятая 1 на втором U) выходе сдвигового регистра 38, а следовательно, и на шестом ш. выходе блока управления 10 появляется после подачи на вход сдвигового регистра 38 пятого импульса от генератора импульсов 4. При эт4эм в случае отрицательного массива чисел логическая со знаковых разрядов, поступая на элемент И 41 блока управления 10, вызывает 1 на первом с выходе (фиг. 1 и б) блока управления 10, которая поступает на вторые входы полусумматоров 23 узлов анализа 22 блока 5 выбора экстремального числа (фиг. 4), что вызывает инверсию кодов чисел на входах узлов 27 сравнения, в результате чего минимальное по модулю число массива чисел становится после полусумматоров 23 максимальным числом. При сравнении чисел их двоичные коды поступают на входы W блока 5 выбора экетремсшьного числа; старшие разряды чисел поступают на () узлы сравнения 27 (фиг. 4), а знаковые разряды чисел поступают на tn узлы сравнения 27. В узлах сравнения 27 с инвертированным единичным значением знаковых разрядов кодов сравниваемых чисел устанавливается 1 на выходе элементов 29 ИЛИ. В узлах сравнения 27 с инвертированным нулевым значением знаковых разрядов кодов сравниваемых чисел устанавливается О на выходе элементов 29 ИЛИ, так как на их первых входах имеется О с выхода элементов НЕ 24 и О -на их |вторых входах с выхода элементов 30 His, ибо на входе последних существует при наличии инвертированной 1 на входе узла сравнения 27 хотя бы в одном узле анализа 22. Нулевой сигнал с выхода элементов ИЛИ 29 запрещает все элементы И 28, расположенные в узлах -27. , 27п,.2 , .. . , 27| сравнения, и элементы и 25 соответствующих узлов 22; анализа, исключая их участие в формировании выходного сигнала на соотве.тствуюищх выходах b блока 5 выбора экстремального числа (фиг. 4). при отсутствии чисел с единичным значением данного разряда единичное значение выхода элемента ИЛИ 29 во всех узлах анализа 22 устанавливается по цепи: элемент 28 И, элемент 26 ИЛИ, элемент 3 НЕ, второй вход элемента 29 ИЛИ и обеспечивает анализ содержимого еледующего разряда чисел. После установления сигналов на вы ходах элементов 28 И, соединенных со старшими каналами, работа логических элементов в других каналах аналогична. Единичное значение на выходе эле мента 25 И, а следовательно, и на вы ходе Ь блока 5 выбора экстремального числа установится только в том узле анализа 22, который ни в одном узле сравнения 27 не содержит элемент 29 ИЛИ с нулевым значением на выходе, т.е. в узле анализа 22 с максимальны числом на его входах лд . При наличии на выходах м блока 7 памяти только отрицательных чисел, на входы узлов сравнения 27 поступают их инверсные коды, в результате наименьшее по модулю из них станет наибольшим, которое и будет выделено соответствующим узлом анализа 22. Единичный сигнал с выхода Ь блока 5 выбора экстремального числа поступает на соответствующий вход первой группы 6 входов ключей блока 4 (фиг. 1 и 6), поэтому сработает. один из ключей элементов 20 И, 21j и - пусть это будет элемент И 22 Это означает, что из трех чисел pj./ а 23/ 0114 которые поступили на входы м блока 5 выбора экстремального чис ла через блок памяти 7 от аналого-ци рового преобразователя б, максимальным положительным числом оказалось число а2, соответствующее модели вет ви 12, расположенной меяаду узлами 13 и 14ц (фиг. 2). Следовательно для дальнейшего анализа на предмет выбора в нем экстремального числа избран узел 13д или, что то же самое,, узел графа задачи комгдивояжера (фиг. 8) , так же как раньше (т.е. на первом шаге) анализировался узел 13 (или узел 2 графа задачи коммивояжера, фиг. 8). Шестой импульс на входе сдвигового регистра 38 вызывает 1 на его третьем выходе и соответственно на втором входе элемента 40 ИЛИ на его выходе, на входе блока памяти 8, отчего на четвертом выходе группы н выходов блока памяти 8 (фиг. 1 и.6) также появится 1. Она же появится одновременно на D -входе триггера 36 и на входе /Н четвертого столбца блока индикации 11 (фиг. 1 и б), в результате чего клетка 312 4 загорит-. ся, т.е. в ней зажжетсясветодиод 34 Таким образом, будет закончено форми рование первого звена будущего гамильгонова контура, т.е. осуществлен переход от узла 2 к узлу 4 графа задачи коммивояжера (фиг. &) . Седьмой импульс на входе регистра сдвига 38 уровней вызовет 1 на его четвертом выходе, откуда она подается на С-входы триггеров ЗЬ , в результате чего на выходах триггеров установится О, так как на их D-входах присутствует О, а на выходе триггера 36ij установится 1, так как на его Л-вход подается 1 с четвертого выхода группы Н выходов блока памяти 8 (фиг. 6). Восьмой импульс на заходе регистра сдвига 38 вызовет 1 на его пятом выходе, которая перепишется на его шестой выход через- его второй вход. Поскольку на первом входе элемента 45 И присутствует 1 с выхода триггера 364 , то от генератора импульсов 43 будут продолжать подаваться импульсы на регистр сдвига 38, который начнет второй цикл переключения логической 1 для обследования узла 13 и выбора в нем экстремального числа, затем работа устройства повторяется. Как только устройство перейдет к анализу последнего узла 13, , то к этому моменту все инцидентные ему модели 12 ветвей будут разорваны и на выходе 6 блока 5 выбора экстремального числа будет нулевой сигнал, который через блок памяти 8 подается на D -входы триггеров в результате на выходах триггеров окажутся нулевые сигналы, которые через элемент 39 ИЛИ запрут элемент 45 И, отключив тем самым регистр сдвига 38, работа устройства прекратится. С блока индикации 11 по зажженным клеткам 31 определяют топологию выделенного гамильтонова контура. Затем кнопкой 35j выбирают следующий стартовый узел, (гася при этом через ключ 46 (фиг.б) на блоке индикации 11 все зажженные клетки З, для которого описанным образом отыскивается свой гамильтонов контур.С помощью кнопок переключателя 35 назначают ч качестве стартовых узлов 1все узлы 13 в модели 1 графа конкретной задачи коммивояжера, для каждого стартового узла устройство отыскивает гамильтонов контур, так что формируется П гамильтоновых контуров (я - размерность решаемой задачи коммивояжера), из которых отбирают минимальный контур по минимальной сумме межузловых расстояний. Затем на модели 1 графа задачи коммивояжера (фиг. 2) с помощью резисторов 16, управляемых синхронно, регулируют напряжение на каждой паре узлов и 14 при включенных ключах 17 так, чтобы суммарное напряжение на парах указанных узлов (которое можно суммиовать, например, с помощью операционного усилителя, а контролировать с помощью цифрового вольтметра) было равно длине найденного на предыдущей итерации минимального гамильтонова контура. После этого повторяют еще одну итерацию формирования п гамильтоновых контуров, среди которых также отыскивеиот минимальный гамильтонов контур. Если вновь найденный минимальный контур равен первому минимальному гамильтоД

.

(г) (гп

Ж

Ж

Ж

(ш)

(Ф) (Ф) .

(Р) (Р)

м ж

(с) (ci

(т) (т)

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

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

ЭДН

г