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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано для определения кратчайшего пути коммивояжера, проходящего через все вершины графа. Целью изобретения является повьшение быстродействия устройства. Из передающей части модели начального узла графа посылается сигнал, в первом разряде которого содержится импульс, указывающий на приход сигнала в узел, единица в К-м разряде М-й группы которого определяет номер ветви, по которой сигнал прошел в М-ю вершину графа. Сигнал задерживается в моделях ветвей на время, кратное 2 , где Н - номер ветви. При поступлении сигнала в М-ю модель по К-й входящей ветви в его соответствующий разряд записывается единица, после чего сигнал вьщается на выход модели.- В приемной части модели анализируется наличие единичных сигналов в дои из групп, что свидетельствует о прохождении сигналом всех вершин графа. 3 з.п. ф-лы, 6 ил. (Л

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

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

РЕСПУБЛИК

„„SU„„7424 (51) 4 G 06 F 15/20

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

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

ВСгСО@. 8 <<

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4103873/24-24 (22) 04;08.86 (46) 15.02.88. Бюл. К 6 (72) А.А. Бобошко и Г.Е. Зацерковный (53) 681.333(088.8) (56) Авторское свидетельство СССР

У 230527, кл. G 06 F 15/20, 1967.

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

В 227716, кл. G 06 Р 15/20, 1967. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ

КОММИВОЯЖЕРА (57) Изобретение относится к вычислительной технике и может быть использовано для определения кратчайшего пути коммивояжера, проходящего через все вершины графа. Целью изобретения является повьппение быстродействия устройства. Из передающей части модели начального узла графа посылается сигнал, в первом разряде которого содержится импульс, указывающий на приход сигнала в узел, единица в К-м разряде M-й группы которого определяет номер ветви, по которой сигнал прошел в М-ю вершину графа. Сигнал задерживается в моден лях ветвей на время, кратное 2, где

Н вЂ” номер ветви. При поступлении сигнала в М-ю модель по К-й входящей ветви в его соответствующий разряд записывается единица, после чего сигнал выдается на выход модели..

В приемной части модели анализируется наличие единичных сигналов в каж-;дой из групп, что свидетельствует о прохождении сигналом всех вершин графа. 3 э.п. ф-лы, 6 ил.

1 137424

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

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

На фиг. 1 изображена функциональная схема устройства; на фиг. 2 пример топологии графа, соответствующий функциональной схеме, представленной на фиг. 1; на фиг. 3 — пример функциональной схемы промежуточного узла; на фиг. 4 — пример функциональ-15 ной схемы приемной части модели на чального узла; на фиг. 5 — функциональная схема блока анализа; на фиг. 6 " временные диаграммы работы тактового генератора. 20

Устройство содержит передающую часть 1 модели начального узла, приемную часть 2 модели начального узла, модели 3 промежуточных узлов и модели 4 ветвей. 25

Модель 3 промежуточного узла содержит триггеры 5, элементы И 6, триггер 7, элементы И 8 и 9, кольцевой регистр 10 сдвига, элемент ИЛИ 11, элементы ИЛИ 12, повторитель 13 им- 30 пульсов регистра 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 индикации.

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

Из передающей части 1 модели из начального узла по всем исходящим ветвям посылается сигнал, в первом разряде которого содержится импульс, используемый в качестве маркера, ука зывающего на приход сигнала в узел, единица в К-м разряде M-й группы которого, где М=1,...,P — номер вер0 г шины в графе, К=1,...,P (P-1) — номер ветви, входящей в M-ю вершину графа, P — количество вершин в графе, определяет номер ветви, по которой сигнал пришел в М-ю вершину графа.

Посылаемый сигнал задерживается в моделях 4 ветви. Величина задержки в ветви выбирается равной 2", где

Н=К. М вЂ” номер ветви. Этим достигается исключение возможности одновременного прихода двух сигналов в одну и ту же модель 3 узла. При поступлении сигнала в какую-либо модель 3 в него вводится признак ветви, по которой он пришел в данный узел графа, т.е. записывается единица в разряд сигнала, местоположение которого определяет номер ветви, после чего сигнал посылается дальше по всем ветвям, исходящим из данного узла.

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

Сигнал, пришедший в конечный узел и содержащий импульсы, соответствующие ветвям, инцидентных всем узлам сетевого графика, запоминается. Если во время работы устройства поступает еще один сигнал с признаками ветвей, инцидентных всем узлам, и в результа- . те анализа будет установлено, что длительность пути, пройденного этим сигналом, меньше, чем длительность пути, пройденного ранее запомненным, сигналом, то запоминается новый т сигнал, а предыдущий стирается. По окончании анализа в модели конечного узла отображается путь и его длительность. Время работы устройства, равное К+1, выбирается для обеспечения анализа всех возможных путей, соответствующих полным циклам графа, и выбора кратчайшего из них.

Модель 3 работает следующим образом.

С приходом сигнала по какой-либо из ветвей начальный импульс устанавливает триггер 7 и один из триггеров

5, соответствующий данной ветви, в единичное состояние. При этом открывается элемент И 8 и на регистр 10 поступают тактовые импульсы от генератора ГИ, одновременно через элемент ИЛИ 12 сигнал поступает в регистр 14. При этом через элемент К+1 и элемент ИЛИ 12 импульс регистра 10, 137424 соответствующий ветви, по которой пришел сигнал, запишется в регистр

14 по импульсам от генератора СГИ.

Если сигнал приходит в данный узел не первый раз, то в двух разрядах регистра 14, соответствующих двум входящим ветвям, по которым пришел сигнал, будут записаны единицы.

Импульсы, соответствующие единицам в этих разрезах, через элементы

ИЛИ 16, И 17 и через элемент ИЛИ 18 поступают на вход элемента И 9. Импульс с (Н+1)-ro выхода регистра 10 переводит в нулевое состояние триггеры 5 и 7 и поступает на первый вход элемента И 9. При этом на его выходе появляется импульс, который устанавливает регистр 14 в нулевое состояние.

Если сигнал приходит в данный узел первый раз, то импульс на выходе элемента И 9 не будет сформирован и содержимое регистра 14 будет выдаваться через повторитель 13 во все исходящие ветви.

Приемная часть 2 модели начального узла работает следующим образом.

Сигнал, поступающий по какой-либо из ветвей, через элементы ИЛИ 20 и

24 импульса СГИ записывается в регистр 31.

Единичный сигнал с выхода триггера 19, соответствующего ветви, по которой пришел сигнал, открывает определенный элемент И 25. Импульс, пос35 тупающий с выхода счетчика 23 на вто рой вход элемента И 25, записывается через элемент ИЛИ 24 в регистр 31, в разряд, соответствующий ветви, по которой поступил сигнал. Сдвиг им-. пульсов СГИ относительно импульсов

ГИ необходим для учета времени, необходимого для установления кода в счетчике 23, и времени срабатывания

45 элементов И 25 и ИЛИ 24, а также для обеспечения правильности записи сигнала в регистр 31. (Н+1)-й импульс с выхода счетчика

23 подается на второй вход элемента

И 27. Если сигнал прошел все узлы се- 5О ти, то на входах всех элементов ИЛИ, соответствующих узлам сети, появляются импульсы, вызывающие импульс на выходе элемента И 29. Этот импульс подается на первый вход элемента И-НЕ 55

27 и через элемент И 28 подается на первые входы элементов И 32 и второй вход элемента ИЛИ 26. На выходах эле0

4 ментов И 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 в нулевое состояние, прекращая процесс анализа. Если sa время анализа поступает несколько сигналов, прошедших все узды сети. то устройство 37 анализа выбирает путь минимальной длины.

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

Перед началом решения задачи в каждый из регистров 38 заносится число, равное длине соответствующей ветви, а в регистр 42 — число, превышающее сумму длительностей всех ветвей сети. При поступлении в приемную часть начального узла сигнала, прошедшего все узлы, с прямых выходов триггеров 33 сигналы поступают на первые входы тех из элементов И 39 и на вторые входы тех элементов И 44, которые соответствуют ветвям, прой1374240 6

Формула из о бре те н ия

40

45 денным сигналом. Элементы И 39, на которые подается сигнал с прямых выходов триггеров 33, открываются, и числа, записанные в регистрах 38, через открытые элементы И 39 подаются на сумматор 40, определяющий длину пройденного пути. С выхода сумма. тора 40 число, соответствующее длине пройденного пути, поступает на первый вход схемы 43 сравнения, на второй вход которой подается число, записанное в регистр 42.

Если число на первом входе схемы 43 сравнения меньше числа на его втором входе, то с выхода схемы 43 ,подается единичный сигнал на первые входы всех элементов. И 44, на второй вход элемента И 41, на второй вход счетчика 47 и на инверсные входы триггеров 45. Тем самым триггеры 45 подготавливаются к записи новой информации, а в счетчик 47 записывается единица.

Число, хранящееся в сумматоре 40, через открытый элемент И 41 записывается в регистр 42. Импульсы с выходов элементов 44, на обоих входах .которых имеются единичные сигналы, переводят в единичное состояние те триггеры 45, которые соответствуют ветвям, пройденным сигналом, обеспечивая фиксацию ветвей пути, проходящеro через все узлы.

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

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

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

1. Устройство для решения задачи коммивояжера, содержащее модель начального узла графа, P-1 моделей промежуточных узлов графа, где P — - количество вершин графа и Р(Р-1) моделей ветвей, соединенные в соответствии с топологией графа, причем модель начального узла графа содержит передающий и приемный модуль, тактовый вход устройства подключен к тактовому входу приемного модуля модели начального узла графа и тактовым входам всех моделей промежуточных узлов графа, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, Т-тая модель ветви (T=1,..., P (P-1) ) содержит элемент задержки, величина которой пропорциот нальна 2

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

3. Устройство по п.1, о т л и— ч а ю щ е е с я тем, что И-я модель промежуточного узла графа (M=1

Р-1) содержит блок сопряжения, регистр сдвига и схему сравнения, причем тактовый вход модели промежуточного узла графа подключен к тактовому входу блока сопряжения и входу признака сдвига регистра сдвига, последовательный информационный выхад которого является информационным выходом модели промежуточного узла графа, К-й информационный вход которой (К=1,, Р-1) подключен к К-му информационному входу блока сопряжения, информационный выход которого подключен к информационному входу регистра сдвига, К-й разряд М-й группы парал- : лельного информационного выхода которого подключен к К-му входы схемы сравнения, выход признака конца слова блока сопряжения подключен к входу опроса схемы сравнения, выход признака "Больше" которой подключен к входу установки в "0" регистра сдвига.

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

7 13742 сдвига, две схемы сравнения М Групп иэ К ключей, блок задания топологии, сумматор, регистр и блок памяти, причем К-й информационный вход блока

5 сопряжения является К-м информационным входом приемного модуля модели .начального узла графа, информационный выход блока сопряжения подключен к информационному входу регистра 1ð сдвига, вход признака сдвига которого является тактовым входом приемного модуля модели начального узла графа и соединен с тактовым входом блока сопряжения, выход признака конца 15 слова которого подключен к входу onроса первой схемы сравнения, выход признака наличия единиц во всех группах информационных входов которой подключен к управляющим входам всех 20 ключей всех групп, К-й разряд М-й группы информационного выхода регист-!

8 ра сдвига подключен к К-му информационному входу И-й группы первой схемы сравнения и информационному входу К-го ключа М-й группы, выход которого подключен к Н-му разряду информационного выхода блока памяти (H=K-М) и к К-му входу опроса М-й группы блока задания топологии, Н-й информационный выход кото:рого является выходом веса пути в М-ю вершину графа по К-й входящей ветви и подключен к входу Н-го слагаемого сумматора, выход которого подключен к первому информационному входу второй схемы сравнения и информационному входу регистра, выход которого подключен к второму информационному входу второй схемы сравнения, вы-. ход признака "Меньше" которой подключен к входам признаков записи регист- ра и блока памяти.

1374240

Фиг.4

/50

Фиг. Х

Составитель А. Мишин

Редактор Е. Копча Техред Л.Сердюкова Корректор A. Тяско

Заказ 604/46 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4