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

н

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

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

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

шины в графе, ,...,Р (Р-1) - номер ветви, входящей в М-ю вершину графа, Р - количество вершин в графе, определяет номер ветви, по которой сигнал пришел в М-ю вершину графа.

Посылаемьй сигнал задерживается в моделях 4 ветви. Величина задержки в ветви выбирается равной 2, где .-М - номер ветви. Этим достигается исключение возможности одновременного прихода двух сигналов в одну и ту же модель 3 узла. При поступлении сигнала в какую-либо модель 3 в него

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

20

узла; на фиг. 4 - пример функциональ- 5 вводится признак ветви, по которой ной схемы приемной части модели на чального узла; на фиг. 5 - функциональная схема блока анализа; на фиг. 6 - временные диаграммы работы тактового генератора.

Устройство содержит передающую часть 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 сдвига, элементы л И 32, триггеры 33, элемент ИЛИ 34, триггер 35, элемент И 36, блок 37 анализа.

В блок 37 анализа входят регистры

35

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

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

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

38, элементы И 39, сумматор 40, эле- .g соответствующих полным циклам графа, мент И 41, регистр 42, схемы 43 срав- и выбора кратчайшего из них.

нения, элементы И 44, триггеры 45, элементы И 46, счетчик 47, элемент И 48, счетчик 49, блок 50 индикации.

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

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

5 вводится признак ветви, по которой

5

0

л

5

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

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

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

0

5

Модель 3 работает следукнцим об- разом.

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

соответствующий ветви, по которой пришел сигнал, запишется в регистр 14 по импульсам от генератора СГИ.

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

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

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

Сигнал, поступающий по какой-либо из ветвей, через элементы ИЛИ 20 и 24 имцульса СГИ записьшается в регистр 31 .

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

(Н+1)-й импульс с выхода счетчика 23 подается на второй вход элемента И 27. Если сигнал прошел все узлы сети, то на входах всех элементов ИЛИ,

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

соответствующих узлам сети, появляются импульсы, вызывающие импульс на выходе элемента И 29. Этот импульс

подается на первый вход элемента И-НЕ триггеров 33 сигналы поступают на 27 и через элемент И 28 подается на первые входы тех из элементов И 39 первые входы элементов И 32 и второй и на вторые входы тех элементов И 44, вход элемента ИЛИ 26. На выходах эле- которые соответствуют ветвям, прой10

15

20

25

- ,

74240

ментов И 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 - число, превышающее сумму длительностей всех ветвей сети. При поступлении в приемную часть начального узла сигнала, прошедшего все узлы, с прямых выходов

30

40

45

50

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

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

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

Если при поступлении в приемную

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

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

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

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

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

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

qjus.l

фиг.г

9т ГИ

9mfH

uii р

Om iS

I

Фиг. 5

tr

Фиг.6