Модель узла графа

 

Изобретение относится к вычислительной технике и может быть использовано при решении на графах задач коммивояжера. Целью изобретения является расширение функциональных возможностей модели узла графа за счет уничтожения кода, вес пройденного которым пути не меньше веса пути, пройденного ранее поступившим кодом. Поставленная цель достигается тем, что в известную модель узла, содержащую первый 2 и второй 6 элементы ШШ, модель пути, выполненную в виде регистра 9 сдвига, генератор 4 импульсов, триггер 10, элемент 12 задержки и распределитель 5 импульсов , введены модель входящих ветвей, выполненная в виде первого регистра памяти 1, группа элементов И 7, третий 3 и четвертый элементы ИЛИ 11, блок 13 элементов И, сумматор 14, блок 17 ключей, схема сравнения 15, второй регистр памяти 16 и коммутатор 8. Работа устройства заключается в йередаче поступающего в узел первого кода без задержки по всем исходящим ветвям с записью 1 на позицию ветви, по которой код поступил в узел; определении веса пройденного кодом пути; уничтожении очередного поступившего в узел кода и передачи очередного кода по всем исходящим ветвям в противном случае. 1 ил. i (Л to со о о

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

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

РЕСПУБЛИК

„„80„„1297070 (50 4 G 06 F 15/20

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

Н А BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

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

¹ 717777, кл. G 06 F 15/20, 1977.

Будинский Я. Логические цепи в цифровой технике ° M.: Связь, 1977, с, 269-273.

Авторское свидетельство СССР № 227716, кл. G 06 G 7/122, 1967. (54) МОДЕЛЬ УЗЛА ГРАФА (57) Изобретение относится к вычислительной технике и может быть использовано при решении на графах задач коммивояжера. Целью изобретения является расширение функциональных возможностей модели узла графа за счет уничтожения кода, вес пройденного которым пути не меньше веса пути, пройденного ранее поступившим кодом, Поставленная цель достигается тем, что в известную модель узла, содержащую первый 2 и второй 6 элементы ИЛИ, модель пути, выполненную в виде регистра 9 сдвига, генератор

4 импульсов, триггер 10, элемент 12 задержки и распределитель 5 импульсов, введены модель входящих ветвей, выполненная в виде первого регистра памяти 1, группа элементов И 7, третий 3 и четвертый элементы ИЛИ 11, блок 13 элементов И, сумматор 14 блок 17 ключей, схема сравнения 15, второй регистр памяти 16 и коммутатор 8. Работа устройства заключается в передаче поступающего в узел первого кода без задержки по всем исходящим ветвям с записью "1" на позицию ветви, по которой код поступил в узел; определении веса пройденного кодом пути; уничтожении очередного поступившего в узел кода и передачи очередного кода по всем исходящим ветвям в противном случае ° 1 ил.

129707С 2 ствующего элемента И 7. Кроме того, пройдя через элементы ИЛИ 2 и 3, маркер запускает генератор 4, им1О

Модель узла графа содержит первый

9-разрядный регистр 1 памяти (g — !5 число ветвей, входящих в данный узел графа), элемент ИЛИ 2, элемент ИЛИ 3, генератор 4 импульсов, распределитель 5 импульсов, элемент ИЛИ 6, группу из g элементов И 7, коммута- 20 тор 8, модель пути, выполненную в виде (R + 1)-разрядного регистра 9 сдвига (R — число ветвей графа), триггер 10, элемент ИЛИ 11, элемент

12 задержки, блок 13 элементов И, 25 сумматор 14, схему сравнения 15, второй регистр !6 памяти, блок 17 ключей.

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

Первоначально устанавливают в нулевое состояние регистры 1 и 9, распределитель 5, триггер 10, в регистр 16 записывают число, заведомо большее возможного веса пути, пройденного первым поступившим кодом.

На вход задания весов ветвей выдают коды этих весов. Ключи 17 разомкнуты, первый информационный вход коммутатора 8 соединен с выходом. 40

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

KIH 2 и 6 и коммутатор 8 на выход модели и передается по всем исходящим из узла ветвям. При этом на позицию, соответствующую ветви, по которой код поступил в модель узла, записывается "1" следующим образок.

Маркер поступает на соответствующий информационный вход (например, на t-й) регистра 1 и записывает

"1" в f.-й разряд; единичный потенциал с выхода этого разряда регистра

1 поступает на первый вход соответ1

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

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

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

"вставляется " на t-ю позицию кода, маркер и все R разрядов которого проходят через элемент ИЛИ 6. При этом код, поступая на информационный вход регистра 9, записывается в него под воздействием сдвинутых тактовых импульсов, поступающих с соответствующего выхода генератора 4 на вход регистра 9 сдвига. Как только все разряды кода, включая маркер, записались в регистр 9 и потенциалы с R его разрядных выходов поступили на соответствующие первые входы блока 13 элементов И, на вторые входы которого поступают коды весов ветвей графа с соответствующих входов модели, единичный потенциал с выхода

2+1 разряда распределителя 5 поступает на третий вход блока 13. В результате веса всех ребер графа, через которые прошел код (на соответствующих его позициях присутствуют

"1"), поступают на входы сумматора

14, которые выдает вес пути, пройденного кодом, на первый вход схемы сравнения 15 и на информационный вход блока 17..На второй вход схемы сравнения 15 с выхода регистра 16 поступает заведомо больший вес, записанный в него первоначально, поэтому схема сравнения выдает сигнал на выход "Меньше".

Кроме того, единичный сигнал с выхода R+1 разряда регистра 9 перебрасывает в единичное состояние триггер

10, с выхода которого единичный потенциал поступает, во-первых, на управляющий вход коммутатора 8, который подключает к выходу свой второй информационный вход (до конца работы устройства), во-вторых, через дифференцирующий вход элемента ИЛИ 11 и элемент задержки 12 импульс поступает на установочный вход регистра 9 и обнуляет его. Кроме того, задним фронтом импульса, выдаваемого с R+I выхода распределителя 5. останавливается генератор 4 и обнуляется регистр °

1297070

5 импульсов подключен к выходу последо10

При поступлении в узел очередного кода запись "1" на позицию соответствующей ветви производится аналогич20 но, как и запуск генератора 4, запись кодограммы в регистр 9, определение веса пути, пройденного кодом, Однако код не может сразу пройти на выход коммутатора 8, поскольку его первый информационный вход отключен от выхода. Если вес пути, пройденного этим кодом, равен или больше веса пути, пройденного предыдущим кодом, то схема сравнения 15 выдает на выход

"Больше, равно" сигнал, который через элемент ИЛИ 11 и элемент задержки 12 поступает на установочный вход регистра 9 и обнуляет его ° Если вес пути, пройденного кодом, меньше пути предыдущего кода, то единичный сигнал с выхода "Меньше" схемы сравнения 15 поступает, во-первых, на управляющий вход блока ключей 17, в результате чего вес этого кода 40 проходит с выхода сумматора 14 на вход регистра 16 и записывается в нем. Во-вторых, сигнал с выхода

"Меньше" схемы сравнения 15 через элемент ИЛИ 3 поступает на вход запуска генератора 4, сдвинутые тактовые импульсы которого, поступая на вход сдвига регистра 9, обеспечивают считывание кода из регистра

9 и передачу его через коммутатор 8 по всем исходящим ветвям. Задним фронтом импульса с R+1 выхода распределителя 5 останавливается генератор 4 и обнуляется регистр 1.

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

Прямоугольный импульс (длительность которого больше длительности импульса с R+1 выхода распределителя

5) поступает на управляющий вход блока 17 и открывает ключи, благодаря чему вес пути, пройденного кодом, с выхода сумматора 14 поступает на вход регистра 16 и записывается в нем.

Задним фронтом импульса с выхода

"Меньше" схемы сравнения 15 через элемент ИЛИ 3 запускается генератор

4, который затем останавливается импульсом с R+1 выхода распределителя 5. Работа генератора 4 на этом цикле имеет значения, поскольку регистр 9 обнулен.

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

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

R — число ветвей графа), (R+l)-ый выход группы информационных выходов которого подключен к установочному входу регистра памяти модели входящих ветвей, к первым входам элементов И второй группы и к входу останова генератора тактовых импульсов, вход запуска которого подключен к выходу третьего элемента ИЛИ, первый вход которого подключен к выходу

"Меньше" схемы сравнения, второй вход третьего элемента ИЛИ подключен к выходу первого элемента ИЛИ, выход второго элемента ИЛИ подключен к первому информационному входу коммутато5 1297070 6 ра, выход которого является выходом подключен к первому входу схемы сравустройства, второй информационный нения, второй вход которой подключен вход коммутатора подключен к инфор- к выходу сумматора, выход "Больше или мационному выходу регистра сдвига равно" схемы сравнения подключен к модели пути; выход каждого х-го раз- 5 первому входу четвертого элемента ряда которого 1=1,2,...,R) подключен ИЛИ, второй вход четвертого элемента второму входу j,-го элемента И вто- ИЛИ объединен с управляющим входом рой группы, третьи входы элементов И коммутатора и подключен к выходу второй группы являются входами зада- триггера, вход которого подключен ния весов ветвей графа, выходы эле- f0 к (2+1)-му выходу регистра сдвига ментов И второй группы соответствен- модели пути, выход коммутатора являно подключены к группе входов сумма- ется выходом модели, информационный тора, выход которого подключен к ин- вхоц коммутатора подключен к выходу формационному входу блока ключей, уп-, второго элемента ИЛИ, выход четверравляющий вход блока ключей подклю- 15 того элемента ИЛИ через элемент зачен к выходу "Меньше" схемы сравне- держки подключен к установочнония, выход блока ключей подключен к му входу рег истра сдвига модели входу регистра памяти, Выход которого пути.

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

Редактор Т. Парфенова Техред Л.Сердюкова Корректор Л, Пилипенко

Заказ 783/53 Тираж 673 Подписное

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

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

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