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

1

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

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

На чертеже приведена блок-схема модели узла графа.

Модель узла графа содержит первый 1-разрядный регистр } памяти ( (j - число ветвей, входящих в данный узел графа), элемент ИЛИ 2, элемент ИЛИ 3 генератор 4 импульсов, распределитель 5 импульсов, элемент ИЛИ 6, группу из элементов И 7, коммутатор 8, модель пути, выполненную в виде (R + I)разрядного регистра 9 сдвига (R - число ветвей графа), триггер 10, элемент ИЛИ 11, элемент 12 задержки, блок 13 элементов И, сумматор 14, схему сравнения 15, второй -регистр 16 памяти, блок 17 ключей.

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

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

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

Маркер поступает на соответствующий информационный вход (например, на 1-й) регистра 1 и записывает 1 в t-й разряд; единичный потенциал с выхода этого разряда регистра 1 поступает на первый вход соответ, 29707G 2

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

5 распределителя 5, который последовательно выдает импульсы на первый, второй, ..., Е-й, ... выходы. Импульс, выдаваемый по Е-му выходу, проходит через 1-й элемент И 7 и

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

20, записались в регистр 9 и потенциалы с R его разрядных выходов поступили на соответствующие первые входы блока 13 элементов И, на вторые входы которого поступают коды весов ветвей

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

рез которые прошел код (на соответ- ствуюп1их его позициях присутствуют 1), поступают на входы сумматора 14, которые выдает вес пути, пройденного кодом, на первый вход схемы

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

40 схема сравнения выдает сигнал на выход Меньше.

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

Прямоугольный импульс (длительность которого больше длительности импульса с R+1 выхода распределителя 5) поступает на управляющий вход блока 17 и открывает ключи, благодаря чему вес пути, пройденного кодом, с выхода сумматора 14 поступает на вхо регистра 16 и записывается в нем. Задним фронтом импульса с выхода Меньше схемы сравнения 15 через элемент ИЛИ 3 запускается генератор 4, который затем останавливается импульсом с R+1 выхода распредели те- ля 5, Работа генератора 4 на этом цикле имеет значения, поскольку ре- гистр 9 обнулен. I

При поступлении в узел очередного

кода запись 1 на позицию соответствующей ветви производится аналогич но, как и запуск генератора 4, запис кодограммы в регистр 9, определение веса пути, пройденного кодом. Однако код не может сразу пройти на выход коммутатора 8, поскольку его первый информационный вход отключен от выхода. Если вес пути, пройденного эти кодом, равен или больше веса пути, пройденного предыдущим кодом, то схема сравнения 15 выдает на выход Больше, равно сигнал, который через элемент ИЛИ 11 и элемент задержки 12 поступает на установочный вход регистра 9 и обнуляет его. Если вес пути, пройденного кодом, меньше пути предьщущего кода, то единичный сигнал с выхода Меньше схемы сравнения 15 поступает, во-первых, на управляющий вход блока ключей 17, в результате чего вес этого кода проходит с выхода сумматора 14 на вход регистра 16 и записывается в нем. Во-вторых, сигнал с выхода Меньше схемы сравнения 15 через элемент ИЛИ 3 поступает на вход за- пуска генератора 4, сдвинутые тактовые импульсы которого, поступая на вход сдвига регистра 9, обеспечивают считывание кода из регистра 9 и передачу его через коммутатор 8 по всем исходящим ветвям. Задним фронтом импульса с R+1 выхода распределителя 5 останавливается генератор 4 и обнуляется регистр 1.

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

Модель узла графа, содержащая первый и второй элементы ИЛИ, генератор

5

5 Q Q 5 Q

5

5

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

Редактор Т. Парфенова

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

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

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

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

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

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

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

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