Устройство для моделирования конечного узла графа

 

Изобретение относится к области вычислительной техники, в частности к решению на графах задач, сводящихся к задаче коммивояжера. Целью изобретения является расширение функциональных возможностей устройства за счет, возможности определения веса пути коммивояжера. Б устройство для моделирования конечного узла, содержащее первый 2, второй 8 и третий 22 элементы ШШ, генератор импульсов 10, модель входящих ветвей 1, вьшолненную в виде регистра памяти, модель пути 12, выполненную в виде регистра сдвига , распределитель импульсов 6, первую группу элементов И 7, вторую группу элементов И 17, триггер 5, первый сл со со о ел со

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

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

РЕСПУБЛИК

ÄÄSUÄÄ 1339579 А1 (51) 4 G 06 F 15/20

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

К А ВТОРСНОМЪ СВИДЕТЕЛЬСТВУ

3»

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3921228/24-24 (22) 28.06.85 (46) 23.09.87. Бюл. М 35 (72) M,М.Овчинников, Ю.M.Коптев и В.И.Итолин (53) 681.333(088.8) (56) Авторское свидетельство СССР

М - 227716, кл. G 06 С 7/122, 1967, Авторское свидетельство СССР

N - 1297070, кл, G 06 F 15/20, 1985..(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

КОНЕЧНОГО УЗЛА ГРАФА (57) Изобретение относится к области вычислительной техники, в частности к решению на графах задач, сводящихся к задаче коммивояжера. Целью изобретения является расширение функциональных возможностей устройства за счет возможности определения веса пути коммивояжера. В устройство для моделирования конечного узла, содержащее первый 2, второй 8 и третий 22 элементы ИЛИ, генератор импульсов 10, модель входящих ветвей 1, выполненную в виде регистра памяти, модель пути

12, выполненную в виде регистра сдвига, распределитель импульсов 6, первую группу элементов И 7, вторую группу элементов И 17, триггер 5, первый

133 регистр памяти 13, элемент задержки

24, схему сравнения 19, блок ключей

20 и сумматор 18, введены второй регистр памяти 21, второй триггер 3, три элемента И 4, 9 и 15, счетчик 11, группа элементов ИЛИ 14 и ключи 16 и

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

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

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

15 разрядного (t1, — число входящих в узел ветвей графя) регистра памяти, первый элемент ИЛИ 2, триггер 3, элемент И 4, триггер 5, распределитель

6 импульсов, первую группу из элементов И 7, второй элемент ИЛИ 8, элемент И 9, генератор 10 импульсов, счетчик 11, модель 12 пути, выполнен— ную в виде (К+1)-разрядного (R — число ветвей графа) регистра сдвига, 25 первый R-разрядный регистр 13 памяти, группу иэ (R-1) элементов ИЛИ 14 (при. чем число входов элемента ИЛИ 14, соответстнующего какому-либо узлу графа. равно числу входящих в этот узел ветвей), элемент И 15, ключ 16, вторую

17 группу элементов И, сумматор 18, схему 19 сравнения, блок 20 ключей, второй регистр 21 памяти, третий элемент ИЛИ 22, ключ 23, элемент 24 задержки. 35

Первоначально устанавливают в нулевое состояние регистры 1, 12 и 21, триггеры 3 и 5, распределитель 6, счетчик 11, в регистр 13 записывают вес, заведомо больший возможного веао са первого пришедшего в узел кода. На входы задания несон ветвей графа подают коды весов. Ключ !6 закрыт, ключ 23 — открыт, Устройство работает следующим образом, При поступлении на какой-либо информационный вход устройства (например, на 1-й) первого кода, на нулевой позиции которого присутствует единичный сигнал — маркер начала кода и некоторое число единиц на позициях, соответствующих номерам ветвей пройденного кодом пути, маркер записывает единицу в 1-й разряд регистра 1. Пройдя через элемент ИЛИ 2, маркер поступает на единичный вход триггера 3, единичный сигнал с выхода которого запускает генератор 10. Кроме того„ маркер перебрасывает в единичное состояние триггер 5; элемент И 4 открывается и импульсы генератора 10 начинают поступать на вход распределителя 6, который поочередно выдает сигналы на свои выходы. При выдаче единичного сигнала на вход 1-го элемента

И 7 единичный сигнал поступает на вход элемента ИЛИ 8, на выход которого проходит поступивший в узел код с записанной на 1-й позиции единицей с соответственно l-й ветви, по которой код поступил н узел. С выхода элемента ИЛИ 8 код разряд за разрядом (впереди маркер) поступает на информационный вход регистра 12 и записывается в нем под ноздейстнием сдвинутых тактовых импульсов генератора 10, постугяющих на вход сдвига регистра 12 через элемент И 9, открытый едИничным потенциалом с выхода триггера 5. ИмОчередной поступивший в конечный узел код обрабатывается аналогично, только вес его пути может быть как меньше веса пути предыдущего кода, так и не меньше. В последнем случае схема 19 сравнения выдает на выход аю It

Больше или равно сигнал, который через элемент ИЛИ 22 и элемент 24 задержки обнуляет регистр 12.

Если же записанный в регистр 12 код не прошел все узлы графа, то на выходе элементы И 15 присутствует нулевой потенциал, при котором ключ 23 открыт, и единичный сигнал с (R+1)-го выхода регистра 12 черезкпюч 23,элемент ИЛИ 22 и элемент 24 задержки обнуляет регистр 12.

После истечения установленного времени приема кодов счетчик 11 выдает сигнал переполнения, который поступает на вход останова генератора 10, прекращая выдачу им импульсов, и на выход окончания работы устройства.

При этом в регистрах 21 и 13 записаны соответственно номера ветвей и вес пути коммивояжера °

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

Устройство для моделирования конечного узла графа, содержащее первый, второй и третий элементы ИЛИ, генератор импульсов, модель входящих ветвей, выполненную в виде регистра памяти, модель пути, выполненную в виде регистра сдвига, распределитель импульсов, первую группу элементов И, вторую группу элементов И, триггер, первый регистр памяти, элемент задержки, схему сравнения, блок ключей и сумматор, причем каждый i-й вход (i = 1, 2,...,R,ãäå К вЂ” число ветвей графа) первого элемента ИЛИ объединить с i-м входом группы информационных входов регистра памяти модели входящих ветвей и является -м входом группы информационных входов устройства, каждый i-й выход группы выходов регистра памяти модели входящих ветвей подключен к первому входу i-ão элемента И первой группы, установочный вход регистра памяти модели входящих ветвей подключен к (R+1) ìó BbIxoду распределителя импульсов, каждый

i-й выход группы выходов которого подключен к второму входу х-го элемента

И первой группы, выход каждого i-ro элемента И первой группы подключен к

3 1339579 пульс с (К+1)-го выхода распределителя 6 своим задним фронтом обнуляет регистр 1 и триггер 5, подготавливая их к поступлению в узел очередного

5 кода. При этом закрываются элементы

И 4 и 9 для прохода импульсов генератора 10.

Единичные или нулевые (соответственно пройденным или непройденным ко- 1р дом ветвям графа) потенциалы с разрядных выходов регистра 12 поступают на соответствующие информационные входы регистра 21 и соответствующие первые входы блока 17 элементов И, на вторые входы которого поступают коды весов ветвей графа. На третий вход блока 17 элементов И поступает единичный сигнал с (R+1)-го (маркерного) выхода регистра 12. Кроме того, все разрядные выходы регистра 12, соответствующие ветвям, входящим в какой-либо i-й (i = 1,R) узел графа, подключены к выходам i-ro элемента ИЛИ 14 (кроме выходов, соответст- 25 вующих ветвям, входящим в конечный узел). Если код прошел все узлы гра-. фа то на выходах всех элементов ИЛИ

14 появляется единичный потенциал, который через элемент И 15 поступает 3ц на управляющий вход ключа 16 так, что единичный сигнал с (R+1)-го (маркерного) разряда регистра 12 проходит на третий вход блока 17. При этом коды весов ветвей, через которые пРошел данный код, поступают на вход сумматора 18, который выдает вес пути на первый вход схемы 19 сравнения и информационный вход блока 20 ключей.

На второй вход схемы 19 сравнения 4О поступает записанный первоначально в регистр 13 заведомо больший вес, поэтому схема 19 сравнения выдает сигнал на выход "Меньше", который поступает на управляющий вход блока 20 45 ключей, через информационные входы которого вес пути, пройденного первым кодом, записывается в регистр 13.

Этот же сигнаЛ поступает на вход записи Регистра 11 которыи копирует со- 50 держимое регистра 12, а через элемент

ИЛИ 22 — на установочный вход регистра 12, обнуляя его, Таким образом, если первый поступивший код прошел все узлы графа, то единицы (признаки ветвей пути) записываются в регистре 21, вес пути — в регистре 13, а регистр 12 обнулен для приема нового кода.

1339579

Составитель Т,Сапунова

Техред M .Дидык Корректор С.Черни

Редактор Е, Папп

Заказ 4224/40 Тираж 672 Подписное

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

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

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

i-му входу второго элемента ИПИ, (R+1)-й вход которого подключен к выходу первого элемента ИЛИ, выход второго элемента ИЛИ подключен к инфор5 мационному входу регистра сдвига модели пути, установочный вход которого подключен к выходу элемента задержки, вход элемента задержки подключен к выходу третьего элемента ИЛИ, первый 10 вход которого подключен к выходу

"Больше или равно" схемы сравнения, первый вход схемь! сравнения подключен к выходу первого регистра памяти, вход которого подключен к выходу бло- 15 ка ключей, управляющий вход которого подключен к выходу "Меньше" схемы сравнения, информационный вход блока ключей и второй вход схемы сравнения объединены и подключены к выходу сум- 20 матора, каждый i-й вход груПпы входон которого подключен к выходу i-го элемента И второй группы, первый вход каждого i-го элемента И второй группы подключен к выходу 3.-го разряда регистра сдвига модели пути, вторые входы элементов И второй группы являются входами задания весов ветвей устройства, о т л и ч а ю— щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет обеспечения возможнос ти определения веса пути коммивояжера, в устройство введены второй регистр памяти, второй триггер, первый, 35 второй и третий элементы И, счетчик, группа элементов ИЛИ, первый и второй ключи, нхад разрешения записи

Второго регистра памяти подключены в выходу "Меньше" схемы сравнения, 40 каждый i-й вход группы информационных входов третьего регистра памяти подключен к выходу i-го разряда (i=

1, 2,...,R) регистра сдвига модели пути, выход Меньше" схемы сравнения 45 подключен к второму входу третьего элемента ИЛИ, третий вход которого подключен к В(!ходу Рторого ключа v0 ранляющие входы т!ерного и второго ключей объединены и подключены к выходу (В+1)-го разряда регистра сдвига модели пути, информационные входы первого и второго ключеи объединены и подключены к выходу третьего элемента И, выход первого ключа подклю— чен к третьим входам всех элементов

И второй группы, каждый j-й вход третьего элемента И подключен к выходу

j-ro элемента ИЛИ группы (j = 1, 2,..., N где N — число узлов графа;

N < К), каждый из входов j-го элемента ИЛИ группы подключен к выходу соответствующего разряда из j и подгруппы разрядных выходов регистра сдвига модели пути, вход сдвига которого подключен к выходу первого элемента И, первый вход которого подключен к выходу первого триггера, вход установки н "0" первого триггера подключен к (R+1)-му выходу распределителя импульсов, вход установки в "1" первого триггера подключен к выходу первого элемента ИЛИ, выход первого триггера подключен к первому входу второго элемента И, второй вход которого подключен к выходу последовательности тактовых импульсов генератора импульсов, выход второго элемента И подключен к входу распределителя импульсов, второй вход первого элемента И подключен к выходу последовательности сдвинутых тактовых импульсов генератора импульсов, выход последовательности тактовых импульсов генератора импульсов подключен к входу счетчика, выход которого подключен к входу останова генератора импульсов и является выходом окончания работы устройства, вход запуска генератора импульсов подключен к выходу второго триггера, вход которого подключен к выходу первого элемента ИЛИ.