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

(56)11 о ельст 15/20 еские Связ с ССР1967. тво чи ь исфах з при решени ояжера. Цел пользова дач комм является возможно г тения изокцио расширение футей модели узл ьн а грвес оиденсчет уничтож кода са ого кот рым пути не м йденного ране ньш по пившим пути,УДАРСТВЕННЫЙ КОМИТЕТ СССР ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ ПИСАНИЕ ИЗ ВТОРСКОМУ СВИДЕТ) 15.03.87. Бюл, ММ.М. Овчинников,Штолин и А,В. Тр681.333(088.8)Авторское свидет7777, кл, С 06 РБудинский Я. Логичровой техникеМ.:269-273,Авторское свидетел27716, кл. С 06 С 54) МОДЕЛЬ УЗЛА ГРАФА57) Изобретение относится кительной технике и может бы кодом, Поставленная цель достигаетсятем, что в известную модель узла,содержащую первый 2 и второй 6 элементы ИЛИ, модель пути, выполненнуюв виде регистра 9 сдвига, генератор4 импульсов, триггер 10, элемент 12задержки и распределитель 5 импульсов, введены модель входящих ветвей,выполненная в виде первого регистрапамяти 1, группа элементов И 7, третий 3 и четвертый элементы ИЛИ 11,блок 13 элементов И, сумматор 14,блок 17 ключей, схема сравнения 15,второй регистр памяти 16 и коммутатор 8. Работа устройства заключаетсяв передаче поступающего в узел первого кода без задержки по всем исходящим ветвям с записью на позициюветви, по которой код поступил вузел; определении веса пройденногокодом пути; уничтожении очередногопоступившего в узел кода и передачиочередного кода по всем исходящимветвям в противном случае1 ил,129707 С 2ствующего элемента И 7. Кроме того,пройдя через элементы ИЛИ 2 и 3,маркер запускает генератор 4, им 1 О Модель узла графа содержит первый 1-разрядный регистр 1 памяти (- 5 число ветвей, входящих в данный узел графа), элемент ИЛИ 2, элемент ИЛИ 3, генератор 4 импульсов, распределитель 5 импульсов, элемент ИЛИ 6, группу из 9 элементов И 7, коммута тор 8, модель пути, выполненную в виде (К + 1)-разрядного регистра 9 сдвига (К - число ветвей графа), триггер 10, элемент ИЛИ 11, элемент 12 задержки, блок 13 элементов И, 25 сумматор 14, схему сравнения 15, второй регистр 6 памяти, блок 17 ключей.Модель узла графа работает следующим образом. ЗоПервоначально устанавливают в нулевое состояние регистры 1 и 9, распределитель 5, триггер 1 О, в регистр 16 записывают число, заведомо большее возможного веса пути, пройденного первым поступившим кодом. На вход задания весов ветвей выдают коды этих весов. Ключи 17 разомкнуты, первый информационный вход коммутатора 8 соединен с выходом. 40При поступлении на какой-либо информационный вход модели (например, на 1-й) первого кода, содержащего единичный сигнал-маркер и некоторое количество "1" на позициях, соответствукнцих ветвям, через которые прошел код, он проходит через элементы ИЛИ 2 и 6 и коммутатор 8 на выход модели и передается по всем исходящим из узла ветвям. При этом на по зицию, соответствующую ветви, по которой код поступил в модель узла, записывается "1" следующим образок.Маркер поступает на соответствующий информационный вход (например, 55 на 1-й) регистра 1 и записывает "1" в 1-й разряд; единичный потенциал с выхода этого разряда регистра 1 поступает на первый вход соответ 1Изобретение относится к вычислительной технике и может быть использовано при решениях на графах задач, сводящихся к задаче коммивояжера.Целью изобретения являетсярасширение функциональных возможностей модели за счет уничтожения кода, вес пройденного которым пути не меньше веса пути, пройденного ранее поступившим кодом.На чертеже приведена блок-схема модели узла графа. пульсы которого поступают на входраспределителя 5, который последовательно выдает импульсы на первый,второй, , 1-й, , выходы. Импульс, выдаваемый по 1-му выходу,проходит через 1-й элемент И 7 и"вставляется" на 1-ю позицию кода,маркер и все К разрядов которогопроходят через элемент ИЛИ 6, Приэтом код, поступая на информационныйвход регистра 9, записывается в него под воздействием сдвинутых тактовых импульсов, поступающих с соответствующего выхода генератора 4 навход регистра 9 сдвига. Как тольковсе разряды кода, включая маркер,записались в регистр 9 и потенциалыс К его разрядных выходов поступили на соответствующие первые входы блока 13 элементов И, на вторые входыкоторого поступают коды весов ветвейграфа с соответствующих входов модели, единичный потенциал с выходаК+1 разряда распределителя 5 поступает на третий вход блока 13. В результате веса всех ребер графа, через которые прошел код (на соответствующих его позициях присутствуют"1"), поступают на входы сумматора14, которые выдает вес пути, пройденного кодом, на первый вход схемысравнения 15 и на информационный входблока 17 На второй вход схемы сравнения 15 с выхода регистра 16 поступает заведомо больший вес, записанный в него первоначально, поэтомусхема сравнения выдает сигнал на выход "Меньше",Кроме того, единичный сигнал с выхода К+1 разряда регистра 9 перебрасывает в единичное состояние триггер 10, с выхода которого единичный потенциал поступает, во-первых, на управляющий вход коммутатора 8, который подключает к выходу свой второй информационный вход (до конца работы устройства), во-вторых, через дифференцирующий вход элемента ИЛИ 11 и элемент задержки 12 импульс поступает на установочный вход регистра 9 и обнуляет его. Кроме того, задним фронтом импульса, выдаваемого с К+1 выхода распределителя 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 по всем исходящим ветвям. Задним фронтом импульса с К+1 выхода распределителя 5 останавливается генератор 4 и обнуляется регистр 1. 55формула изобретения Прямоугольный импульс (длительность которого больше длительности импульса с К+1 выхода распределителя 5) поступает на управляющий вход блока 17 и открывает ключи, благодаря чему вес пути, пройденного кодом, с выхода сумматора 14 поступает на вход регистра 16 и записывается в нем. Задним фронтом импульса с выхода "Меньше" схемы сравнения 15 через элемент ИЛИ Э запускается генератор 4, который затем останавливается импульсом с К+1 выхода распределителя 5, Работа генератора 4 на этом цикле имеет значения, поскольку регистр 9 обнулен.1 Модель узла графа, содержащая первый и второй элементы ИЛИ, генератор тактовых импульсов, триггер, элемент задержки, распределитель импульсови модель пути, выполненную в видерегистра сдвига, вход распределителя вательности тактовых импульсов генератора тактовых импульсов, выход последовательности сдвинутых тактовых импульсов которого подключен к входу синхронизации регистра сдвига модели пути, входы первого элемента ИЛИ являются группой информационных входов модели, а выход первого элемента ИЛИ подключен к первому входу второгоэлемента ИЛИ, выход которого подключен к информационному входу регистра сдвига модели пути, о т л и ч а ю -щ а я с я тем, что, с целью расширения функциональных возможностей засчет определения веса пройденногопути и уничтожения кода пути, вескоторого равен или больше веса путипредыдущего кода, в модель узла введена первая группа элементов И, третий и четвертый элементы ИЛИ, втораягруппа элементов И, сумматор, блокключей, схема сравнения, регистр памяти, коммутатор и модель входящихветвей, выполненная в виде регистрапамяти, каждый вход группы информационных входов регистра памяти модели входящих ветвей объединен с одноименным входом первого элемента ИЛИ, выход каждого 1-го разряда регистра памяти модели входящих ветвей подключены к первому входу х-го (=1,2,,К, где К - число ветвей графа)элемента И первой группы, выход которого подключен к 1-му входу (==+1) второго элемента ИЛИ, второйвход каждого -го элемента И первойгруппы подключен к -му выходу группы информационных выходов распределителя импульсов (1=1,2К, гдеК - число ветвей графа), (К+)-ыйвыход группы информационных выходовкоторого подключен к установочномувходу регистра памяти модели входящих ветвей, к первым входам элементов И второй группы и к входу останова генератора тактовых импульсов,вход запуска которого подключен квыходу третьего элемента ИЛИ, первыйвход которого подключен к выходу"Меньше" схемы сравнения, второйвход третьего элемента ИЛИ подключенк выходу первого элемента ИЛИ, выходвторого элемента ИЛИ подключен к первому информационному входу коммутато70 Составитель ХСапуноваРедактор Т, Парфенова Техред Л.Сердюкова Корректор Л, Пилипенко Заказ 783/53 Тираж 673 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5. Производственно-полиграфическое предприятие, г, Ужгород, ул, Проек.ная, 4 5 12970 ра, выход которого является выходом устройства, второй информационный вход коммутатора подключен к информационному выходу регистра сдвига модели пути; выход каждого х-го разряда которого =1,2 К) подключен к второму входу ).-го элемента И второй группы, третьи входы элементов И второй группы являются входами задания весов ветвей графа, выходы эле ментов И второй группы соответственно подключены к группе входов сумматора, выход которого подключен к информационному входу блока ключей, управляющий вход блока ключей подклю чен к выходу "Меньше" схемы сравнения, выход блока ключей подключен к входу регистра памяти, выход которого подключен к первому входу схемы сравнения, второй вход которой подключенк выходу сумматора, выход "Больше илиравно" схемы сравнения подключен кпервому входу четвертого элементаИЛИ, второй вход четвертого элементаИЛИ объединен с управляющим входомкоммутатора и подключен к выходутриггера, вход которого подключенк (2+1)-му выходу регистра сдвигамодели пути, выход коммутатора является выходом модели, информационныйвхоц коммутатора подключен к выходувторого элемента ИЛИ, выход четвертого элемента ИЛИ через элемент задержки подключен к установочному входу рег истра сдвига моделипути.