Приемный модуль модели начального узла графа Советский патент 1992 года по МПК G06F15/419 

VJ

О

ел

00 00 00

М.юбрыенир относится к вычисли ел ь- ной техника и может быть использовано в качестве составной масти устройства для определении путей коммивояжера, проходя щи lej.i j «СР пункты (уплм) анализируемой сети

Известно устройство, которое мо;:сич оы MCf iG. iMOHriHij е качестве приемного мом- мя начально. :1 /зла ус гроиг;твз для ре L;I ..M« задачи коммивояжер (модуля),

едос ЛУГОМ этого устройства являет...г огрсжиченчсл ь это Функциональных воз мощностей проявляющаяся в способноптн

ВЫЯВЛЯТЬ ИЗ .:-/. ВОЗМОЖНЫ:; ПуМеЙ КОМММв о я .;;. о р а лишь муть минимального веса

.: ратчайший). Кром; ого, о нем необходимо

; оу Ц| мгэля1ь I Pj.-Hiy.or-iny ацию соединений

.-. V..JV-1 i кок ..-I : то элементами чрн ил ...- . « огь -и. Г .1 i моделируемой сети. Э го

iyi.:помнено nf)1,- вязкг.и длины принимае ...; HP-.; -о..о- г.г i i количеству не i-.ей R

.. .. ; ,..-. .-.( ;. ч Г. И результате П(Г ПС -. ,if-,:. - ( .: (.-.:, ei.,1,.1 --(ИСПП -1 В01 ВРИ i г.ч f. ;t :: ПрИ i : : l .. I. .С г. . - . . /С Г рой Г i В EJ

- ч ; .,-з сос;оян 1 по iii:/BOwy сординчт1. нь..- ,ц:- oacnpf AP 1 пеля с входами группы

.- /и--IB И ; i--:/i :. регистра - с в/одами

: il ll..| .- l: --l ii : В ; / I -.

(.i lfjc :0 ft. in и-1 к i 1 вдлйгаемому мо :1/ |Ю яиля ; 1:1- ii,.i,i гл :дя часть мидучя н,г

|Я,-;ьио о . ;:.гройс ;ва для решения

.ciAV. K(.;i h- iv1Bi;P;Kepd, В КОТОРОМ КОПИЧвС

1О разрядка пс иниг-. аемых кодограмм Н - Рх ( 1) зависит оль О от числа узлов Р г. о / лируемс й сет 1 В результате при перехо . м-. ) i одной модели сети к другой с од|-1на .пвим ч -г/ чом узлов Р отпадает «соГ;- хпдиг Н/ .;ть н 1 :рен-,(- ерацпи ветвей

.гч, а знач1. И и ь связанной с этим пег коммутации i. Kfr; чдгп.ю элементов пост

111Г 3 .

ОДИРКО ..: i ,j i приемный модуль опреде- /iHci , п; i . -v iHHt a.iLHbiM весом, из лр|-.;--.е(1 ..ищи ij Rcex возг ожнь.,,| .t. l .i.u--if.lM|ion I -.-p -j ь 0 ГЭ1; Г- МГ-ае

лир, - MO -i ; .fjTH к,очхет Г , -)чагьс 1 нес/.оль: я дру|их путей, близких кратчайшему, но более предпочтительных с других точек зое

НИП. 1. 1СКЛЮЧ Н 1.: -Я НХ Ну ГРЙ ИЗ fl4; C.MOTpf:

ьмя может v (н..мп, каче:пзо результлтск: рс1иеч 1я задячи кo 1миьoяжepa.

Цепь изобп ген,1я - paciunpeHi/ie функ мионтльпых возможностей приемного моV- Лй 33 ГЧРТ ОПП ДЙЛОНИЯ ДОПОЛНИТЕЛЬНЫХ

гей коммич(. Я.- с- ;;, бл- чайил- /. к гччч ,

ильному

У уэннач цепь достшлетгя .ем. чтг- .

to/.;vHi. /юоопчитеп .мо введешь1 илемес. Фиргчироазю и. сиг и-мо в с им неясным дм. а

i-VJ 4 K-V 1 ВХОДОМ :- ЦИО 1ИГОР ;Н1 К1- pt

I

гислр сдвига, две группы по I элементов НЕ, устройство ранжирования, вход изменения номера считываемой кодограммы, третья группа из п информационных выходов модуля (n - loij/:m{), причем второй управляющий выход блока сопряжения через элемент И, на другой вход которого подключен пход сдвигонь х тактовых импульсов, подключен к входу управления сдвигом регистра сдвига, информационные выходы которого дополнительно подключены к одноименным информационным входам секционированного регистра сдвига и блока задания топологии ьыход схемы сравнения через форммпчв Лель сигналов подключен к чзр- вому управляющему входу устройств оан- л ировань .я к второму управляющему входу которого подключен вход изменения номера считываемой кодограммы, каждый из еы- x viou сумматора через одноименный ; г;/мент червой группы элементов HF под- | /;.ОЧРН к одноименному информационному ;(лоду усгпойг,гва ранжм.зовэния пнходы .иг-рвои второй и третьей групп у Ч апняк щ.ж устройства ранжировани-i подключены к одноименным входам чер- вои, второй L. гретьей групп управляющих вхтдос се.кц.онированно; о регистра сдчига cooine;u гэч.ю, выходы гругты информационных выходов которого подключены к о г,, поименным выходам первой .руты и ч Ь ,1)1лационных выходов модуля, первой и второй управляющие входы секционированного регистра сдвига подключены к одно именным управляющим г и /. одаг f. тройства ранжирования, к а я-1 дм и ил выхо 4t f первой группы информационны4, выхо до в которого под к л ю |-, с через )дчоименпый элемент второй группы эле - ентов НЕ к одноименному вькоду тс рои группы информационных выход о s- г плу.ля, яыходы третьей группы управляющих выхо- ГДМР, устройства ранжирования дополнитель- 1 п п.л -/почетi к однсыменным выходам i ре -.. О группы инфорг ионных выходов

МОДУ/i:-).

На фиг. 1 представлена структурная схема приемного модуля; на фиг.2 - функциональная схема секционированного регистра .двига этого -lOДyля.

Приемный модуль содержит блок 1 со- |;рях°ния. э/ емент И 2 регистр 3 сдвига, лок -I сравнения, формирователь 5 сигналов с инверсным динамическим входом, сек- mtjit,.ропанний регистр 6 сдвига, блок 7 Tono iof iii, сумматор 8, группу 9 из элементов НЕ, при этом

1 Г оаг A,vitгде V) - вес j-й ветви моделируемой сети;

Х - символ округления до ближайшего верхнего числа X.

блок 10 ранжирования и группу 11 из I элементов НЕ.

На фиг 1 приняты обозначения: AI - Ak - группа информационных входов модуля. (p - число узлов в моделируемой сети); В - вход тактовых импульсов (ТИ); С -- вход сдвинутых (во времени по отношению к ТИ) тактовых импульсов (СТИ); - группа информационных выходов. Н р х х(р-1); Е - сигнальный выход; F - управляющий вход; - группа информационных выходов: И-ln группа информационных выходов, п Iog2m.

Схема регистра сдвига приемного модуля состоит из элементов ИЛИ 12i-12m-i; группы элементов 2И-ИЛИ 13i-13m по Н элементов в каждой элементов И 14r 14т. Н - разрядных регистров 15i-15m с синхронизацией приема, коммутатора 16 с m H- разрядными группами информационных входов, п -разрядной группой управляющих входов и Н-разрядной группой выходов и Н-разрядных регистров 17i-17m-i с синхронизацией приема.

На фиг. 2 К обозначает группу из Н информационных входов, НСЗ - группу из гп управляющих входов. НСС - группу из (т-1) управляющих входов. СС1. СС2 -; управляю- aine входы и ИСК - группу из п управляющих входов.

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

Элемент И 2 служит для пропускания сдвинутых тактовых импульсов со входа С модуля в регистр 3 пои работе модуля толь ко в режиме приема. Один из входов этого элемента соединен с выходом трипера блока 1 сопряжения.

Регистр 3 сдвига преобразует очередную (Н+1)-разрядную кодограмму, поступившую в модуль, из последовательного кода в параллельный.

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

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

5Секционированный регистр 6 сдвига предназначен для приема, хранения и выдачи кодограмм, отобранных модулем, вес которых входит на текущий момент времени в число m наименьших весов принятых кодрг0 рамм.

Блок 7 задания топологии формирует вес ветвей, по которым прошла очередная принятая кодограмма.

Сумматор 8 служит для формирования

5 веса очередной кодограммы, принятой модулем.

Группа из I элементов НЕ 9 представляет вес очередной принятой кодограммы в обратном коде.

0Блок 10 предназначен ранжирования совместно с группой элементов НЕ 9 для отбора из всех кодограмм, поступивших в модуль, m кодограмм с наименьшим веоом, для ранжирования, хранения и выдачи ве5 сов этих кодограмм в обратном коде и их рангов.

Группа из I элементов НЕ 11 представляет в прямом коде веса m кодограмм, pj- нимых в обратном коде в устройстве 10

0 ранжирования.

По входам Ai - Ak ведется прием кодограмм, последовательно поступающих по одной из k входных ветвей МОДУЛЯ, по ;хсдам В и С в модуль подаются ТИ и СТИ, обесгод5 чивающие синхронизацию его работы по выходам DI-CH происходит еыдача m ксдог- рамм, считываемых по одной из регистра б, по выходу Е - выдача сигнала, разрешающего считывание одной из m кодограмм, сочра0 ненных модулем, по входу г увеличивайся на единицу номер кодограммы, подлежащей считыванию из модуля, по выходам GvGi производится выдача кодов весе в m кодограмм, считываемых по одному из Зло- 5 ка 10 ранжирования, по выходам Ir In - выдача ранга кодограммы, считываемой из регистра 6.

Элементы ИЛИ 12i-12m-i предназначены для снятия блокировки прохождения

0 синхронизирующего сигнала с входа СС2 при записи в (/ 2, т-1) секцию регистра 6 очередной принятой кодограммы или содержимого(д-1)-1 секции при проведе нии сдвигов

Элементы 2И-ИЛИ -13,, служат для пропускания в ff-ю секцию регистра 6 очередной кодограммы или содержимого (-1)-й секции.

Элементы И 14v 14|П управляют прохождением синхронизирующего сигнала с входа СС2 нз управляющий вход одноименного регистра 15i 15m, которые образуют основной регистр одноименной секции секционированного регистра б

Коммутатор 16 используется дня выдачи содержимого выбранной секции регистра В на выходы D г-Ои.

Регистры 17i - 17in 1 образуют вспомогательный регистр одноименной секции регистра 6,

По входам НСЗ осуществляется прием из блока 10 ранжирования т-разрядного унитарного кода номера основной секции, которая выбряия записи очередной кодограммы, по i-ходам k - прием Н-разряд- jtf1 очспедно i-..щограммы из росисгра 3

модуля, .ю входам HCC - прием из блока 10 ранжирования (м- -разрядных кодов номе чов секгий в | а; аую из которых, должен иг.щестяпятьс -: сдвиг из секций с номером на елпницу .шим ее номера.

праолг.ющие входы СС1 и СС2 пред,, эчсны для синхронизации процессов записи соответственно во вспомогательные и основные регистры секционированного

; V -:-lC1 P- - l В.

Группа сходен iCK предназначена дп приема п-разрядноч; кода номера считыза- емой кодограммы из Стека 10 ранжирования, группа Di-Dn - для выдачи И-разрядного содержимого выбранной секции регистра 6.

Перед началом работы в блоке 7 задания топологии выеi являют веса ветвей моделируемой сети В начальное состояние модуль переводят сигналом начальной уста новки. Под воздействием этого сигнала г гистры 3 и 6. а также все триггеры блок с 1 сопряжения и блока 10 оанжирования уста нлтивэются в О. На входы В и С подаются соответственно Т И и СТИ, На входах Ai-Ai- и F присутствуют нупевые потенциалы.

Приемный модуль работает по ЦИКЛУ;- количество которых равно количеству поступивших кодограмм. В каждом цикле модуль находится в одном из четырех режимов работы: ожидания, приема, анализа и ранжирования, По окончании последнего цикля и по истечении допустимого времени приема ьсех кодограмм наступает режим считывания.

8 режиме ожидания модуль ожидает поступление очередной кодограммы по одно му из входов A i -A|, k р-1 о число узпоп ч моделируемой сети. При нахождении моду ля в начальном г.осточнии имеет место час. тныи случай р лима ом;- дания ,. поступлением марке: - ереднр ч ;в м,к; :- 0сти, первой} (ИПоразрядной кодограммы по i-му (|-1.k) входу AI модуль переходит в режим приема. Это сопровождается установкой единичного сигнала на выходе блока

1 сопряжения,соединенном с элементом И 2. В результате снимается блокировка для прохождения СТИ на вход управления сдвигом на один разряд влево в сторону старших разрядов регистра 3. Очередная кодограм0 мапоразрядно проходит через блок 1 сопряжения в регистр 3, по ТИ записывается в младший разряд регистра 3, а по СТИ сдвигается на один разряд влево.Кроме гою. в j-й разряд кодограммы (j 1, Н в перечне

5 номеров ветвей моделируемой сети и соот ветствует номеру i-й ветви в перечне номеров ветвей, входящих в модуль). поступающей в ретистр 3. заносится 1. Таким образом отмечается факт постучле0 пил в модуль очередной кодограммы по j-й ветви моделируемой сети, или по i-й модуля. В процессе записи кодограммы в регистр 3 его выходные сигналы дру ими устройствами модуля не воспринимаются

5 На (Н+1)-мТИ режим приема заканчивается. При этом на выходе блока 1 сопряжения, соединенном с элементом И 2, устанавливается нулевой потенциал, а через выход блока 1 сопряжения, соединенный с блоком 4

0 сравнения, проходит (Н-Н)-й ТИ. В разрядах регистра 3 с 1-го по Н-й оказывается з апи санной информационная часть гон кодограммы. Модуль переходит в режим анализа. Содержание режима анализа со5 ставляет анализ гого, побывала ли принятая, т.е. записанная в регистр 3. кодограмма ее всех узлах моделируемой сети. Положительный результат анализа имеет место, ес- 1и в одном из разрядов каждой группы

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

5 pe M-;v; ран мафсваиия. ; случае положи- емьного результата анализа блок 4 сравнения по (Н-Н)-му ТИ формирует единичный сигнал, поступающий на формирователь 5 сигналов. В процессе осуществления рсжи0 мз анализа па информационных входах 5ло- к а 10 ранжирования формируется l-разр ;дныи обратный код веса (например, длины пройденного пуп;) очередной кодограммы. Формирование этого кода осушест5 чл втся поэтапно В Олоке 7 задания юпологии по местоположению единиц в разрядах регистра 3 воспроизводятся коды весов (пример, длин; чех ветвей, которые aout/iH в путь, пройдонт -;й очередной кодог- .-1о-л В сумматор- Ь и коды арифметически суммируются. Полученный результат инвертируется группой элементов НЕ 9. Кроме того, по заднему фронту выходного сигнала блока 4 сравнения срабатывает формирователь 5. Длительность выходного сигнала этого формирователя гарантированно больше времени окончания переходных процессов в блоке 7 задания топологии. cvM- -м оре 8 и группе элементов НЕ 9. Ре- жмм анализа заканчивается к моменту формирования заднего Фронта выходного сигнала формирователя 5. Одновременно с этим начинается режим ранжирования. В начале режима ранжирования на информационных входах блока 10 ранжирования находится код вэса очередной кодограммы в обратном г:д. ранее сформированный в режиме анализа. Использование обратного кода позволяет осуществлять отбор и ранжирование кодограмм наименьшего веса на блок 10 ранжирования кодограмм, предназначенный для выполнения указанных операций над кодограммами наибольшего веса. Блок 10 ранжирования устанавливает ся по заднему фронту сигнала с выхода формирователя 5 в начальное состояние. При этом на группе входов К регистра 6 (см.фиг.2) продолжает находиться информа- ционноя Н-разрядная часть очередной кодограммы (бе, маркера), поступающей с выходов регистра 3 и сформированной в режиме приема. Каждый разряд этой Н-раз- рядной кодограммы поступает на одноименный информационный вход регистра 151 и информационный :чход первой группы входов одноименных элементов 2И ИЛИ каждой из групп 13r t3mi. Пс заднему фронту выходного согнала формирователя 5 блок 10 ранжирования устанавливается в начальное состояние. При этом на управляющих входах НСЗ регистра б устанавливается 1 в ni-разрядмом унитаргэм коде. С первого входа группы управляющих входов НСЗ подается единичный сигнал на один из входов элемента И 14. С остальных входов этой группы подается нулевой потенциал. Единичный сигнал подается ча все т-1 входы группы управляющих входов НСС регистра 6 и далее на управляющий вход второй группы входов каждого элемента 2И--ИЛИ каждой из групп 13i 13m-i. На каждом информационном входе второй группы входов каждого элемента 2И-ИЛИ каждой из групп 13v-13m-i устанавливается содержимое одноименного разряда вспомогательного регистра секции с номером, на единицу меньшим номера секции основного регистра. Этими сигналами регистр 6 подготавливается к записи очередной кодограммы с группы входов К в первую секцию регистра 6 и к приему содержимого секций с 1-й по (т-1)-ю в секции со 2-й по т-ю соответственно. На управляющих входах СС1 и СС2 устанавливается нулевой по- тенциал. не разрешающий ни проведение записей, ни проведение сдвигов в регистре 6.

Ранжирование веса очередной кодограммы в обратном коде осуществляется

0 блоком 10 ранжирования и заключается в определении того, должна ли быть сохранена очередная кодограмма и каково ее мисто (ранг) среди ранее отобранных кодограмм. В случае принятия решения о сохранении

5 блок ранжирования размещает код eec;i сохраняемой кодограммы в соответствии с его величиной среди кодов весов ранее отобранных и отранжированных кодограмм в своих регистрах, а также осуществляет не0 обходимые для этого размещения сдвиги. Кроме того, оно вырабатывает управляющие сигналы регистру 6 на точно такие же размещение сохраняемой и сдвиг отобранных кодограмм соответственно.

5 При этом кодограмма m-ro (наибольшего) ранга и ее вес в обратном коде исключаются из числа отобранных. В случае принятия отрицательного решения о сохранении никаких изменений среди ранее отобранных

0 кодограмм не производится.

В ходе осуществления режима ранжирования в регистре 6 используются сигналы только на группах входов НСЗ, НСС и бхо5 дах СС1 и СС2. При этом на группе входов НСЗ устанавливается г кода веса очередной кодограммы (.т), установленный блоком 10 ранжирования. Ранг г поступает в унитарном m-разрядном коде для указа0 ния номера секции г в регистре 6. в которую необходимо осуществить запись очередной кодограммы, подаваемой с выхода регистра 3 При этом единичный сигнал поступает на один из входов элемента И 14i, если ,

5 или на управляющий вход первой группы входов каждого элемента 2И-ИЛИ группы 13Г, если 2 г т-1. Это приводит Е последнем случае к поступлению каждого разряда очередной кодограммы через

0 информационный вход первой группы входов одноименного элемента 2И-ИЛИ гэуп- пы 13г-1 на одноименный информационный вход регистра 15Г. Кроме того, единичный сигнал с r-го входа группы входов НСЗ через

5 элемент ИЛИ 12r-i поступает на один из входов элемента И 14Г. если 2 г гл-1, блокируя подачу сигнала с входа на управляющий вход регистра 15г через элемент И 14Г.

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

При этом единичный сигнал подается на входы с r-го по (гп-1)-й группы входов НСС и далее на каждый из управляющих входов второй группы входов каждого из элементов 2И--ИЛИ групп 13r-l3m i. В результате разрешается подача на информационные вхо ды каждого из основных регистров 15rH-15m содержимого одноименных разрядов вспомогательных регистров 17r-17m.i соответственно. Кроме того, этот сигнал через каждый из элементов ИЛИ 12r 12m-i подается на один из входов одного из элементов И 14г-и 14т соответственно, блокируя подачу сигнала с входа СС2 на управляющий вход каждого из регистров через одноименный элемент И из чиспа элементов 14ги--14т.

По установлении ранга веса очередной кодограммы на входе СС1 регистра б появляются единичный сигнал, который поступает чз управляющие входы вспомогательных регистров 17i Г/rr -1 При этом осуществляется запись содержимого каждого из основных регистров 15г- 5т 1 в одноименные вспомогательные регистры 17i-17m-i. По окончании действия сигнала с входа СС1 единичный сигнал появляется на входе СС2. По этому сигналу происходит запись очередной кодограммы в основной регистр 15г и запись содержимого каждого из вспомога- тепьных регистров 17,- 17т-1 в соответствующий из основных регистров 15г-и--15т. этгм работа модуля в режиме ранжироп- ния, а вместе с ним и очередной цикл раба; и модуля заканчиваются.

Режим считывания начинается по окончании последнего цикла работы модуля и истечение допустимого времени приема модулем кодограмм. Этот момент сопровождается установлением единичного потенциала на выходе Е модуля. При этом блок 10 ранжирования устанавливается в начальное состояние, а внешней нагрузкой с выходов воспринимается содержимое кодограммы 1-го ранга. С выходов Gv-Gi и выходов 11 11 снимают вес и ранг этой кодограммы соответственно.

На группе входов НСК устанавливается единица в n-разрмдном ДРОИЧНОМ коде, ко торый поступает на группу управляющих сходов коммутатора 16. Это приводит к аы- дэче содержимого основного регистра 15i через коммутатор 16 на выходы Гн-Он. Сигналы на указанных выходах остаются неизменными до поступления единичного сигнала на входе F. увеличивающего на единицу номер считываемой кодограммы. При подаче нэ F-вход s единичных сигналов 1 s т- 1 на выходы Di-Он выдается содержимое кодограммы (s-H)-ro ранга, а на выходах Gv-Gi и Ii-{n - соответственно вес и ранг этой кодограммы. При этом на группе

входов НСК формируется п-разрядный двоичный код числа s+1, который по аналогии с указанным приводит к выдаче содержимого основного регистра 15S+1 на выходы Di DH. В режиме считывания управляющие сигналы на входах СС1 и СС2 не вырабатываются, а сигналы на группах входов НСЗ и НСС регистром 6 не воспринимаются При поступлении очередного единичного сигнала на вход F в момент выдачи кодограммы .п-го

ранга происходит изменение номера считываемой кодограммы с m на 1. Режим считывания производится до установки модуля в начальное состояние, осуществляемое оператором.

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

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

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

50

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

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

(.;/ ока сравнения - к одноименному входу приемного модуля, информационный выход и первый управляющий выход блока сопряжения - к информационному входу регистра сдвига и к управляющему входу блока срав- нения соотпетственно. информационный выход регистра сдвига - к информационному Ei;;, блока сравнения, выходы группы бл1.кн задания топологии - к одноименным зхоп,; м сумматора, о т л и ч а ю щи и с я тем. что. с целью расширения функциональных оозможностей модуля путем определения дополнительных путей коммивояжера, ближайших к минимальному, в него введены элемент И, формирователь сигналов с ин- версным динамическим входом, секционированный регистр сдвига, две группы элементов НЕ и блок ранжирования, причем второй управляющий выход блока сопряжения подключен к первому входу элемента И. выход которого подключен к входу управления сдвигом регистра сдвига, разряды информационного выхода которого подключены к соответствующим информационным входам секционированного реги- стра сдвига и соответствующим входам опроса блока задания топологии, второй вход.элемента И является входом сдвинутых тактовых импульсов приемного модуля, выход блока сравнения через формирователь

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

Изобретение относится к вычислительной технике и может быть использовано а моделирующих устройствах, предназначенных для решения на графах задач, сводящихся к задаче коммивояжера. Целью изобретения является расширение функциональных возможностей устройства за счет определения дополнительных путей коммивояжера, ближайших к минимальному. Устройство содержит блок 1 сопряжения, элемент И 2, регистр 3 сдвига, блок 4 сравнения, формирователь 5 сигналов с инверсным динамическим входом, секционированный регистр б сдвига, блок 7 задания топологии, сумматор 8, группу 9 элементов НЕ, блок 10 ранжирования и группу 11 элементов НЕ. 2 ил.