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

13

регистр памяти 13, элемент задержки 24, схему сравнения 19, блок ключей 20 и сумматор 18, введены второй регистр памяти 21, второй триггер 3, три элемента И 4, 9 и 15, счетчик 11, группа элемент ов ИЛИ 14 и ключи 16 и 23. Устройство осуществляет запись в Каждый поступающий код признака вет

1

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

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

На чертеже представлена функционалная схема устройства для моделирования конечного узла,

Устройство содержит модель 1 входящих ветвей, вьшолненную в виде разрядного ( гь число входящих в узел ветвей графа) регистра памяти, первый элемент ИЛИ 2, триггер 3, элемент И 4, триггер 5, распределитель 6 импульсов, первую группу из ц элементов И 7, второй элемент ИЛИ 8, элемент И 9, генератор 10 импульсов, счетчик 11, модель 12 пути, выполненную в видте (R+1)-разрядного (R - число ветвей графа) регистра сдвига, первьй R-разрядный регистр 13 памяти группу из (R-1) элементов ИЛИ 14 (причем число входов элемента ИЛИ 14, соответствующего какому-либо узлу графа равно числу входящих.в этот узел ветвей), элемент И 15, ключ 16, вторую 17 группу элементов И, сумматор 18, схему 19 сравнения, блок 20 ключей, второй регистр 21 памяти, третий элемент ИЛИ 22, ключ 23, элемент 24 задержки,

Первоначально устанавливают в нулевое состояние регистры 1, 12 и 21, триггеры 3 и 5, распределитель 6, счетчик 11, в регистр 13 записывают вес, заведомо больший возможного в-е

39579

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

t моделирования ветвей и веса пути коммивояжера. 1 ил.

0

0

0

са первого пришедшего в узел кода. На входы задания весов ветвей графа подают коды весов. Ключ 16 закрыт, ключ 23 - открыт.

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

При поступлении на какой-либо информационный вход устройства (например, на 1-й) первого кода, на нулевой позиции которого присутствует единичный сигнал - маркер начала кода и некоторое число единиц на позициях, соответствующих номерам ветвей пройденного кодом пути, маркер записывает единицу в 1-й разряд регистра 1. Пройдя через элемент ИЛИ 2, маркер поступает на единичньш вход триггера 3, единичньш сигнал с выхода которого запускает генератор 10. Кроме того маркер перебрасывает в единичное состояние триггер 5; элемент И 4 открывается и импульсы генератора 10 начинают поступать на вход распределителя 6, который поочередно выдает сигналы на свои выходы. При вьщаче единичного сигнала на вход 1-го элемента И 7 единичный сигнал поступает на вход элемента ИЛИ 8, на выход которого проходит поступивший в узел код с записанной на 1-й позиции единицей с соответственно 1-й ветви, по которой код поступил в узел. С выхода элемента ИЛИ 8 код разряд за разрядом (впереди маркер) поступает на информационный вход регистра 12 и записьшается в нем под воздействием сдвинутых тактовых импульсов генератора 10, поступающих на вход сдвига регистра 12 через элемент И 9, открытый единичным потенциалом с выхода триггера 5, Им. 1339579

пульс с (R+l)-ro выхода распределителя 6 своим задним фронтом обнуляет регистр 1 и триггер 5, подготавливая их к поступлению в узел очередного кода. При этом закрьшаются элементы И 4 и 9 для прохода импульсов генератора 10.

Единичные или нулевые (соответственно пройденным или непройденным ко- Q жки обнуляет регистр 12.

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

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

На второй вход схемы 19 сравнения поступает записанный первоначально в регистр 13 заведомо больший вес, поэтому схема 19 сравнения выдает сигнал на выход Меньше, которьй поступает на управляющий вход блока 20 ключей, через информационные входы которого вес пути, пройденного первым кодом, записьшается в регистр 13. Этот же сигнал поступает на вход записи регистра 11, который копирует содержимое регистра 12, а через элемент ИЛИ 22 - на установочньй вход регистра 12, обнуляя его.

Таким образом, если первый постуЕсли же записанный в регистр 12 код не прощел все узлы графа, то на выходе элементы И 15 присутствует н левой потенциал, при котором ключ 2

5 открыт, и единичньш сигнал с (R+l)выхода регистра 12 через ключ 23,эле мент ИЛИ 22 и элемент 24 задержки о нуляет регистр 12.

После истечения установленного в

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

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

30

35

40

45

50

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

Устройство для моделирования конечного узла графа, содержащее пер- вьй, второй и третий элементы ИЛИ, нератор импульсов, модель входящих ветвей, выполненную в виде регистра памяти, модель пути, выполненную в виде регистра сдвига, распределител импульсов, первую группу элементов вторую группу элементов И, триггер, первый регистр памяти, элемент задержки, схему сравнения, блок ключе и сумматор, причем каждый i-й вход (, 2,...,R,гдe R - число ветвей графа) первого элемента ИЛИ объединить с i-M входом группы информацио ных входов регистра памяти модели входящих ветвей и является i-м входо группы информационных входов устройства, каждьй i-й выход группы выходо регистра памяти модели входящих ветвей подключен к первому входу i-ro элемента И первой группы, установоч ный вход регистра памяти модели вход щих ветвей подключен к (К+1)-му выхо

пивщий код прощел все узлы графа, то g ду распределителя импульсов, каждый

единицы (признаки ветвей пути) записываются в регистре 21, вес пути - в регистре 13, а регистр 12 обнулен для приема нового кода.

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

жки обнуляет регистр 12.

Очередной поступивший в конечный узел код обрабатывается аналогично, только вес его пути может быть как меньше веса пути предыдущего кода, так и не меньше. В последнем случае схема 19 сравнения выдает на выход Больше или равно сигнал, которьш через элемент ИЛИ 22 и элемент 24 задерЕсли же записанный в регистр 12 код не прощел все узлы графа, то на выходе элементы И 15 присутствует нулевой потенциал, при котором ключ 23

открыт, и единичньш сигнал с (R+l)ro выхода регистра 12 через ключ 23,элемент ИЛИ 22 и элемент 24 задержки обнуляет регистр 12.

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

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

0

5

0

5

0

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

Устройство для моделирования конечного узла графа, содержащее пер- вьй, второй и третий элементы ИЛИ, генератор импульсов, модель входящих ветвей, выполненную в виде регистра памяти, модель пути, выполненную в виде регистра сдвига, распределитель импульсов, первую группу элементов И, вторую группу элементов И, триггер, первый регистр памяти, элемент задержки, схему сравнения, блок ключей и сумматор, причем каждый i-й вход (, 2,...,R,гдe R - число ветвей графа) первого элемента ИЛИ объединить с i-M входом группы информационных входов регистра памяти модели входящих ветвей и является i-м входом группы информационных входов устройства, каждьй i-й выход группы выходов регистра памяти модели входящих ветвей подключен к первому входу i-ro элемента И первой группы, установочный вход регистра памяти модели входящих ветвей подключен к (К+1)-му выходу распределителя импульсов, каждый

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

i-му входу второго элемента ШШ, (К+1)-й вход которого подключен к выходу первого элемента ИЛИ, выход второго элемента ИЛИ подключен к информационному входу регистра сдвига модели пути, установочный вход которог подключен к выходу элемента задержки вход элемента задержки подключен к выходу третьего элемента ИЛИ, первый вход которого подключен к выходу Больше или равно схемы сравнения, первьй вход схемы сравнения подключен к выходу первого регистра памяти вход которого подключен к выходу блока ключей, управляющий вход которого подключен к выходу Меньше схемы сравнения, информационный вход блока ключей и второй вход схемы сравнения объединены и подключены к выходу сумматора, каждый i-й вход группы вхо до-в которого подключен к выходу i-ro элемента И второй группы, первый вход каждого i-ro элемента И второй группы подключен к выходу i-ro разряда регистра сдвига модели пути, вторые входы элементов И второй группы являются входами задания весов ветвей устройства, о тлич аю- щ е е с я тем, что, с целью расширения функциональных возможностей усройства за счет обеспечения возможноти определения веса пути коммивояжера, в устройство введены второй регистр памяти, второй триггер, первый второй и третий элементы И, счетчик, группа элементов ИЛИ, первый и второй ключи, вход разрешения записи второго регистра памяти подключены в выходу Меньше схемы сравнения, каждый i-й вход группы информационных входов третьего регистра памяти подключен к выходу i-ro разряда (i 1, 2,,,.,R) регистра сдвига модели пути, выход Меньше схемы сравнения подключен к второму входу третьего элемента ИЛИ, третий вход которого

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

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

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

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий И3035, Москва, Ж-35, Раушская наб., д. 4/5

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

подключен к выходу рторого ключа,.управляющие первого и второго ключей обт единены и подключены к выхо- ду (К+1)-Г о разряда регистра сдвига модели пути, информационные входы первого и второго ключей объединены и подключены к выходу элемента И, выход первого ключа подключен к третьим входам всех элементов И второй группы, каждый j-й вход третьего элемента И подключен к выходу j-ro элемента ИЛИ группы (j 1, 2,..., N, где N - число узлов графа;

N R), каждый из входов j-ro элемента ИЛИ группы подключен к выходу соответствующего разряда из j-й подгруппы разрядных выходов регистра сдвига модели пути, вход сдвига ко-

торого подключен к выходу первого

элемента И, первый вход которого подключен к выходу первого триггера, вход установки в О первого триггера подключен к.(К+1)-му выходу распределителя импульсов, вход установки в I первого триггера подключен к выходу первого элемента ИЛИ, выход пе.рвого триггера подключен к первому входу второго элемента И, второй вход которого подключен к выходу последовательности тактовых импульсов генератора импульсов, выход второго элемента И подключен к входу распределителя импульсов, второй вход первого элемента И подключен к выходу последовательности сдвинутых тактовых импульсов генератора импульсов, выход последовательности тактовых импульсов генератора импульсов подключен к входу счетчика, выход которого подключен к входу останова генератора импульсов и является выходом окончания работы устройства, вход запуска генератора импульсов подключен к выходу

второго триггера, вход которого подключен к выходу первого элемента ИЛИ.

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