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

)4 6 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОПИСАНИЕ ИЗОБРЕТЕНИЯд," ВСг СОЮЗ МУ СВИДЕТЕЛЬСТВУ г бЕ. Зацерковнь(56) Авторское свидетельство СССР У 230527, кл. 6 06 Р 15/20, 1967.Авторское свидетельство СССР В 227716, кл. С 06 Р 15/20, 1967. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА(57) Изобретение относится к вычислительной технике и может быть использовано для определения кратчайшего пути коммивояжера, проходящего через все вершины графа. Целью иэоб ретения является повьппение быстродействия устройства. Из передающей части модели начального узла графа посылается сигнал, в первом разряде которого содержится импульс, указывающий на приход сигнала в узел, единица в К-м разряде М-й группы которого определяет номер ветви, по которой сигнал прошелв М-ю вершину графа. Сигнал задерживается в моден лях ветвей на время, кратное 2 , где Н - номер ветви. При поступлении сигнала в М-ю модель по К-й входящей ветви в его соответствующий разряд записывается единица, после чего сигнал выдается на выход модели. В приемной части модели анализируется наличие единичных сигналов в каж". дой из групп, что свидетельствует о прохождении сигналом всех вершин графа. 3 э.п. ф-лы, 6 ил.1 137424Изобретение относится к вычислительной технике и может быть использовано для определения кратчайшего пути коммивояжера, проходящего через все вершины графа.Целью изобретения является повышение быстродействия устройства.На фиг. 1 изображена функциональная схема устройства; на фиг. 2 пример топологии графа, соответствующий функциональной схеме, представленной на фиг. 1; на фиг. 3 - пример функциональной схемы промежуточного узла; на фиг. 4 - пример функциональной схемы приемной части модели на чального узла; на фиг. 5 - функциональная схема блока анализа; на фиг. 6 " временные диаграммы работы тактового генератора, 20Устройство содержит передающую часть 1 модели начального узла, приемную часть 2 модели начального узла, модели 3 промежуточных узлов и модели 4 ветвей. 25Модель 3 промежуточного узла содержит триггеры 5, элементы И 6, триггер 7, элементы И 8 и 9, кольцевой регистр 10 сдвига, элемент ИЛИ 11, элементы ИЛИ 12, повторитель 13 им пульсов регистра 14 сдвига, схему 15 анализа, элементы ИЛИ 16, элементы И 17 и элемент ИЛИ 18.Приемная часть 2 модели начального узла содержит триггеры 19, элемент ИЛИ 20,. триггер 21, элемент И 22, счетчик 23, элемент ИЛИ 24, элементы И 25, элемент ИЛИ 26, элемент И-НЕ 27, элементы И 28 и 29, элементы ИЛИ 30, регистр 31 сдвига, элементы 40 И 32, триггеры 33, элемент ИЛИ 34, триггер 35, элемент И 36, блок 37 анализа.В блок 37 анализа входят регистры 38, элементы И 39, сумматор 40, элемент И 41, регистр 42, схемы 43 сравнения, элементы И 44, триггеры 45, элементы И 46, счетчик 47, элемент И 48, счетчик 49, блок 50 индикации.Устройство работает следующим образом.50Из передающей части 1 модели из начального узла по всем исходящим ветвям посылается сигнал, в первом разряде которого содержится импульс, используемый в качестве маркера, указывающего на приход сигнала в узел, единица в К-м разряде М-й группы которого, где М=1Р - номер вер 0гшины в графе, К=1. Р (Р) - номер ветви, входящей в М-ю вершину графа, Р - количество вершин в графе, определяет номер ветви, по которой сигнал пришел в М-ю вершину графа,Посылаемый сигнал задерживается в моделях 4 ветви. Величина задержки в ветви выбирается равной 2", где Н=К. М - номер ветви. Этим достигается исключение возможности одновременного прихода двух сигналов в одну и ту же модель 3 узла. При поступлении сигнала в какую-либо модель 3 в него вводится признак ветви, по которой он пришел в данный узел графа, т.е. записывается единица в разряд сигнала, местоположение которого определяет номер ветви, после чего сигнал посылается дальше по всем ветвям, исходящим из данного узла.Если сигнал, пришедший в узел, содержит импульс, соответствующий одной из инцидентных ветвей данного узла, то, следовательно, он пришел.в узел повторно и поэтому уничтожается.Сигнал, пришедший в конечный узел и содержащий импульсы, соответствующие ветвям, инцидентных всем узлам сетевого графика, запоминается. Если во время работы устройства поступает еще один сигнал с признаками ветвей, инцидентных всем узлам, и в результа- . те анализа будет установлено, что длительность пути, пройденного этим сигналом, меньше, чем длительность пути, пройденного ранее запомненным, сигналом, то запоминается новыйтсигнал, а предыдущий стирается. По окончании анализа в модели конечного узла отображается путь и его длительность. Время работы устройства, равное К+1, выбирается для обеспечения анализа всех возможных путей, соответствующих полным циклам графа, и выбора кратчайшего из них.Модель 3 работает следующим образом.С приходом сигнала по какой-либо из ветвей начальный импульс устанавливает триггер 7 и один из триггеров 5, соответствующий данной ветви, в единичное состояние. При этом открывается элемент И 8 и на регистр 10 поступают тактовые импульсы от генератора ГИ, одновременно через элемент ИЛИ 12 сигнал поступает в регистр 14. При этом через элемент К+1 и элемент ИЛИ 12 импульс регистра 10,137424 соответствующий ветви, по которойпришел сигнал, запишется в регистр14 по импульсам от генератора СГИ.Если сигнал приходит в данныйузел не первый раз, то в двух разрядах регистра 14, соответствующихдвум входящим ветвям, по которым пришел сигнал, будут записаны единицы.Импульсы, соответствующие единицамв этих разрезах, через элементыИЛИ .16, И 17 и через элемент ИЛИ 18поступают на вход элемента И 9. Импульс с (Н+1)-го выхода регистра 10переводит в нулевое состояние триггеры 5 и 7 и поступает на первыйвход элемента И 9. При этом на еговыходе появляется импульс, которыйустанавливает регистр 14 в нулевоесостояние.20Если сигнал приходит в данныйузел первый раз, то импульс на выходе элемента И 9 не будет сформирован и содержимое регистра 14 будетвыдаваться через повторитель 13 вовсе исходящие ветви.Приемная часть 2 модели начального узла работает следующим образом.Сигнал, поступающий по какой-либоиз ветвей, через элементы ИЛИ 20 и24 импульса СГИ записывается в регистр 31,Единичный сигнал с выхода триггера 19, соответствующего ветви, по которой пришел сигнал, открывает определенный элемент И 25. Импульс, пос 35тупающий с выхода счетчика 23 на второй вход элемента И 25, записывается через элемент ИЛИ 24 в регистр 31,в разряд, соответствующий ветви, покоторой поступил сигнал. Сдвиг им-,пульсов СГИ относительно импульсовГИ необходим для учета времени, необходимого для установления кода всчетчике 23, и времени срабатывания45элементов И 25 и ИЛИ 24, а также дляобеспечения правильности записи сигнала в регистр 31.(Н+1)-й импульс с выхода счетчика23 подается на второй вход элементаИ 27. Если сигнал прошел все узлы се Оти, то на входах всех элементов ИЛИ,соответствующих узлам сети, появляются импульсы, вызывающие импульс навыходе элемента И 29. Этот импульсподается на первый вход элемента И-НЕ 5527 и через элемент И 28 подается напервые входы элементов И 32 и второйвход элемента ИЛИ 26. На выходах элеоаментов И 32, вторые входы которыхсоединены с разрядами регистра 31, вкоторых записаны единицы, т.е,с разрядами, соответствующими ветвямсети, по которым передавался сигнал,появляются импульсы, переводящие соответствующие триггеры 32 в единичноесостояние.Сигналы с выходов триггеров 33поступают в устройство 37 анализа,определяющее длительность пути, ина вход элемента ИЛИ 34, выходной.сигнал которого переводит триггер 35в единичное состояние. Сигнал с прямого выхода триггера 35 подается навторой вход элемента И 36. При этомимпульсы ГИ запускают счетчик 49.Выходной сигнал с элемента ИЛИ 26переводит триггеры 19, 21 и 33 в нулевое состояние, подтягивая схему канализу нового сигнала.Если за время, необходимое дляпрохождения всех сигналов, не придетновый сигнал, прошедший все узлы, тоимпульс с выхода переполнения счетчика 49 поступает в блок 37 анализа,разрешая индикацию пути коммивояжера в устройстве 50 индикации, ипереводит триггер 35 в нулевое состояние.Если сигнал, записанный в регистр31, прошел не все узлы сети, то навыходе элемента И 29 не появится импульс. В этом случае на выходе элемента И-НЕ 27 после поступления наего второй вход импульса со счетчика 23 появляется импульс, которыйчерез элемент ИЛИ 26 переводит триггеры 19, 21 и 33 в нулевое состояние,прекращая процесс анализа. Если завремя анализа поступает несколькосигналов, прошедших все узды сети. тоустройство 37 анализа выбирает путьминимальной длины.Устройство анализа работает следующим образом.Перед началом решения задачи вкаждый из регистров 38 заносится число, равное длине соответствующей ветви, а в регистр 42 - число, превышающее сумму длительностей всех ветвейсети. При поступлении в приемнуючасть начального узла сигнала, прошедшего все узлы, с прямых выходовтриггеров 33 сигналы поступают напервые входы тех из элементов И 39и на вторые входы тех элементов И 44,которые соответствуют ветвям, прой1374240 6 Формула изобретения 35 40 45 денным сигналом. Элементы И 39, накоторые подается сигнал спрямых выходов триггеров 33, открываются, ичисла, записанные в регистрах 38,через открытые элементы И 39 подаются на сумматор 40, определяющий длину пройденного пути. С выхода сумма, тора 40 число, соответствующее длине пройденного пути, поступает напервый вход схемы 43 сравнения, навторой вход которой подается число,записанное в регистр 42.Если число на первом входе схемы 43 сравнения меньше числа на еговтором входе, то с выхода схемы 43,подается единичный сигнал на первыевходы всех элементов. И 44, на второйвход элемента И 41, на второй входсчетчика 47 и на инверсные входытриггеров 45. Тем самым триггеры 45подготавливаются к записи новой информации, а в счетчик 47 записывается единица.Число, хранящееся в сумматоре 40,через открытый элемент И 41 записывается в регистр 42 Импульсы с выходов элементов 44, на обоих входах.которых имеются единичные сигналы,переводят в единичное состояние тетриггеры 45, которые соответствуютветвям, пройденным сигналом, обеспечивая фиксацию ветвей пути, проходящего через все узлы,Если при поступлении в приемную часть модели начального узла сигнала, прошедшего все узлы, окажется, что длина его пути больше числа, хранящегося в регистре 42, то на втором выходе схемы 43 будет нулевой сигнал, который запрещает запись длительности пути, пройденного разряд ным сигналом, в регистр 42 и изменение состояния триггеров 45. Если при поступлении в приемную часть модели начального узла сигнала, прошедшего все,узлы, окажется, что его длительность равна числу, хранящемуся в регистре 45, то на первом выходе схемы 43 будет единичный сигнал, который увеличивает значение счетчика 47 на единицу.После определения всех путей, проходящим через все узлы, состояние триггеров 45 соответствует составу кратчайшего пути, проходящего через все узлы. 1. Устройство для решения задачи коммивояжера, содержащее модель начального узла графа, Рмоделей промежуточных узлов графа, где Р - количество вершин графа и Р(Р) моделей ветвей соединенные в соответствии с топологией графа, причем модель начального узла графа содержит передающий и приемный модуль, тактовый вход устройства подключен к тактовому входу приемного модуля модели начального узла графа и тактовым входам всех моделей промежуточных узлов графа, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, Т-тая модель ветви (Т=1Р(Рсодержит элемент задержки, величина которой пропорцио"тнальна 22. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что передающий модуль начального узла графа содержит генератор одиночного импульса, вход пуска которого является входом пуска устройства, а выход является информационным выходом модели начального узла.3. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что М-я модель промежуточного узла графа (М=1 Р) содержит блок сопряжения, регистр сдвига и схему сравнения, причем тактовый вход модели промежуточного узла графа подключен к тактовому входу блока сопряжения и входу признака сдвига регистра сдвига, последовательный информационный выход которого является информационным выходом модели промежуточного узла графа, К-й информационный вход которой (К=1, , Р) подключен к К-му информационному входу блока сопряжения, информационный выход которого подключен к информационному входу регистра сдвига, К-й разряд М-й группы парал-" лельного информационного выхода которого подключен к К-му входы схемы сравнения, выход признака конца слова блока сопряжения подключен к входу опроса схемы сравнения, выход признака "Больше" которой подключен к входу установки в "0" регистра сдвига.4. Устройство по п.1, о т л ич а ю щ е е с я тем, что приемный модуль модели начального узла содержит блок сопряжения, регистр7 13742 сдвига, две схемы сравнения М Групп иэ К ключей, блок задания топологии, сумматор, регистр и блок памяти, причем К-й информационный вход блока5 сопряжения является К-м информационным входом приемного модуля модели ,начального узла графа, информационный выход блока сопряжения подключен к информационному входу регистра 10 сдвига, вход признака сдвига которого является тактовым входом приемного модуля модели начального узла графа и соединен с тактовым входом блока сопряжения, выход признака конца 15 слова которого подключен к входу опроса первой схемы сравнения, выход признака наличия единиц во всех группах информационных входов которой подключен к управляющим входам всех 20 ключей всех групп, К-й разряд М-й группы информационного выхода регист 408ра сдвига подключен к К-му информационному входу И-й группы первой схемы сравнения и информационному входу К-го ключа М-й группы, выход которого подключен к Н-му разряду информационного выхода блока памяти (Н=К-М) и к К-му входу опроса М-й группы блока задания топологии, Н-й информационный выход кото:рого является выходом веса пути в М-ю вершину графа по К-й входящей ветви и подключен к входу Н-го слагаемого сумматора, выход которого подключен к первому информационному входу второй схемы сравнения и информационному входу регистра, выход которого подключен к второму информационному входу второй схемы сравнения, вы-. ход признака "Меньше" которой подклЬ- чен к входам признаков записи регист ра и блока памяти.1374240 150Фиг,ХСоставитель А. Мишин Редактор Е. Копча Техред Л.Серцвкоаа КорректоР А. Тяско Заказ 604/46 Тираж 704 Подписное ВНИИПИ Государственного комитета СССР