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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК ЯО 1339579 А 1(50 4 С 06 Р 15/20 ОПИСАНИЕ ИЗОБРЕТЕНИЯ 4сф Ф фц Н А ВТОРСНОМЪ/ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) Авторское свидетельство СССРВ 227716, кл. С 06 С 7/122, 1967.Авторское свидетельство СССРУ 1297070, кл. С 06 Р 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 ил.1Изобретение относится к вычислительной технике, в частности к решению на графах задач, сводящихся к задаче коммивояжера,Цель изобретения - расширениефункциональных возможностей эа счетобеспечения воэможности определениявеса пути коммивояжера,На чертеже представлена функциональная схема устройства для моделирона 10ния конечного узла,Устройство содержит модель 1 входящих ветвей, выполненную в виде15разрядного (1, - число входящих в узелветвей графя) регистра памяти, первый элемент ИЛИ 2, триггер 3, элемент И 4, триггер 5, распределитель6 импульсов, первую группу изэлементов И 7, второй элемент ИЛИ 8,элемент И 9, генератор 10 импульсов,счетчик 11, модель 12 пути, выполненную в виде (К+1)-разрядного (К - число ветвей графа) регистра сдвига,25первый К-разрядный регистр 13 памяти,группу иэ -1) элементов ИЛИ 14 (причем число входов элемента ИЛИ 14, соответствующего какому-либо узлу графа.равно числу входящих в этот узел ветвей), элемент И 15, ключ 16, вторую3017 группу элементов И, сумматор 18,схему 19 сравнения, блок 20 ключей,второй регистр 21 памяти, третий элемент ИЛИ 22, ключ 23, элемент 24 задержки.35Первоначально устанавливают в нулевое состояние регистры 1, 12 и 1,триггеры 3 и 5, распределитель б,счетчик 11, в регистр 13 записываютвес, заведомо больший возможного ве- ао са первого пришедшего в узел кода. Навходы задания весов ветвей графа подают коды весов. Ключ 6 закрыт,ключ 23 - открыт,Устройство работает следующим образом,При поступлении на какой-либо информационный вход устройства (например, на 1-й) первого кода, на нулевой позиции которого присутствует единичный сигнал - маркер начала кода инекоторое число единиц на позициях,соответствующих номерам ветвей пройденного кодом пути, маркер записываетединицу в 1-й разряд регистра 1. Пройдя через элемент ИЛИ 2, маркер поступает на единичный вход триггера 3,единичный сигнал с выхода которогозапускает генератор 10. Кроме тогомаркер перебрасывает в единичное состояние триггер 5; элемент И 4 открывается и импульсы генератора 10 начинают поступать на вход распределителя б, который поочередно выдает сигналы на свои выходы, При выдаче единичного сигнала на вход 1-го элементаИ 7 единичный сигнал поступает навход элемента ИЛИ 8, на выход которого проходит поступивший в узел код сзаписанной на 1-й позиции единицей ссоответственно 1-й ветви, по которойкод поступил н узел, С выхода элемента ИЛИ 8 код разряд за разрядом (впереди маркер) поступает на информационный вход регистра 12 и записываетсяв нем под ноздейстнием сдвинутых тактовых импульсов генератора 10, постугяющих на вход сдвига регистра 12 через элемент И 9, открытый едИничнымпотенциалом с выхода триггера 5. ИмОчередной поступивший в конечный узел код обрабатывается аналогично, только вес его пути может бить как меньше веса пути предыдущего кода, так и не меньше. В последнем случае схема 19 сравнения выдает на выход зю ВБольше или равно сигнал, который через элемент ИЛИ 22 и элемент 24 задержки обнуляет регистр 12.Если же записанный в регистр 12 код.не прошел все узлы графа, то на выходе элементы И 15 присутствует нулевой потенциал, при котором ключ 23 открыт, и единичный сигнал с (К+1)-го выхода регистра 12 черезкпюч 23,элемент ИЛИ 22 и элемент 24 задержки обнуляет регистр 12.После истечения установленного времени приема кодов счетчик 11 выдает сигнал переполнения, который поступает на вход останова генератора 10, прекращая выдачу им импульсов, и на выход окончания работы устройства.При этом в регистрах 21 и 13 записаны соответственно номера ветвей и вес пути коммивояжераФормула изобретения Устройство для моделирования конечного узла графа, содержащее первый, второй и третий элементы ИЛИ, генератор импульсов, модель входящих ветвей, выполненную в виде регистра памяти, модель пути, выполненную в виде регистра сдвига, распределитель импульсов, первую группу элементов И, вторую группу элементов И, триггер, первый регистр памяти, элемент задержки, схему сравнения, блок ключей и сумматор, причем каждый -й вход (1 = 1, 2К,где К - число ветвей графа) первого элемента ИЛИ объединить с -м входом группы информационных входов регистра памяти модели входящих ветвей и является 1-м входом группы информационных входов устройства, каждый -й выход группы выходов регистра памяти модели входящих ветвей подключен к первому входу х-го элемента И первой группы, установочный вход регистра памяти модели входящих ветвей подключен к (К+1)-му выходу распределителя импульсов, каждый х-й выход группы выходов которого подключен к второму входу -го элемента И первой группы, выход каждого -го элемента И первой группы подключен к 3 1339579пульс с (К+1)-го выхода распределителя 6 своим задним фронтом обнуляетрегистр 1 и триггер 5, подготавливаяих к поступлению в узел очередного5кода, При этом закрываются элементыИ 4 и 9 для прохода импульсов генератора 10,Единичные или нулевые (соответственно пройденным или непройденным кодом ветвям графа) потенциалы с разрядных виходов регистра 12 поступаютна соответствующие информационныевходи регистра 21 и соответствующиепервые входы блока 17 элементов И,на вторие входы которого поступаюткоды весов ветвей графа. На третийвход блока 17 элементов И поступаетединичный сигнал с (К+1)-го (маркерного) выхода регистра 12, Кроме того, все разрядные выходы регистра 12,соответствующие ветвям, входящим вкакой-либо 1-й (з. = 1,К) узел графа, подключены к выходам 1-го элемента ИЛИ 14 (кроме выходов, соответствующих ветвям, входящим в конечныйузел). Если код прошел все узлы гра-.фа, то на выходах всех элементов ИЛИ14 появляется единичный потенциал,который через элемент И 15 поступает З 0на управляющий вход ключа 16 так, чтоединичный сигнал с (К+1)-го (маркерного) разряда регистра 12 проходитна третий вход блока 1. При этом коды весов ветвей, через которые прошелданный код, поступают на вход сумматора 18, который выдает вес пути напервый вход схемы 19 сравнения и информационный вход блока 20 ключей.На второй вход схемы 19 сравнения 4 Опоступает записанный первоначально врегистр 13 заведомо больший вес, поэтому схема 19 сравнения выдает сигнал на выход "Меньше", который поступает на управляющий вход блока 20 45ключей, через информационные входы которого вес пути, пройденного первымкодом, записывается в регистр 13.Этот же сигнаЛ поступает на вход записи Регистра 11 которыи копирует содержимое регистра 12, а через элементИЛИ 22 - на установочный вход регистра 12, обнуляя его.Таким образом, если первый поступивший код прошел все узлы графа, тоединицы (признаки ветвей пути) записываются в регистре 21, вес пути - врегистре 13, а регистр 12 обнулен дляприема нового кода.1339579 Составитель Т,СапуноваТехред М .Дидык Корректор С.Черни Редактор Е, Папп Заказ 4224/40 Тираж 672 Подписное ВНИИПИ Гасударственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Рауяская наб,) д. 4/5-му входу второго элемента ИПИ,(К+1)-й вход которого подключен к выходу первого элемента ИЛИ, выход второго элемента ИЛИ подключен к инфор 5 мационному входу регистра сдвига модели пути, установочный вход которого подключен к выходу элемента задержки, вход элемента задержки подключен к выходу третьего элемента ИЛИ, первый 10 вход которого подключен к выходу "Больше или ранна" схемы сравнения, первый вход схемь сравнения подключен к выходу первого регистра памяти, вход которого подключен к выходу бло ка ключей, управляющий вход которого подключен к выходу "Меньше" схемы сравнения, информационный вход блока ключей и второй вход схемы сравнения объединены и подключены к выходу сум матора, каждый -й вход груПпы входон которого подключен к выходу 1.-го элемента И второй группы, первый вход каждого 1.-го элемента И второй группы подключен к выходу -го разряда регистра сдвига модели пути, вторые входы элементов И второй группы являются входами задания весов ветвей устройства, о т л и ч а ю - щ е е с я тем, что, с целью расши- З 0 рения функциональных возможностей устройства за счет обеспечения возможнос ти определения веса пути коммивояжера, в устройство введены второй регистр памяти, второй триггер, первый, 35 второй и третий элементы И, счетчик, группа элементов ИЛИ, первый и второй ключи, нхад разрешения записи Второго регистра памяти подключены в выходу "Меньше" схемы сравнения, 40 каждый -й вход группы информационных входов третьего регистра памяти подключен к выходу х-го разряда (1.=1, 2 К) регистра сдвига модели пути, выходМеньпе" схемы сравнения 45 подключен к второму входу третьего элемента ИЛИ, третий вход которого подключен к Входу Рторого ключа уранляюие входы терного и второгоключей объединены и подключены к выходу (К+1)-го разряда регистра сдвигамодели пути, информационные входыпервого и второго ключеи объединеньи подключены к выходу третьего элемента И, выход первого ключа подключен к третьим входам всех элементовИ второй группы, каждый 1-й вход третьего элемента И подключен к выходу1-го элемента ИЛИ группы (: = 1,2 И, где Х - число узлов графа;МК), каждый из входов 1-го элемента ИЛИ группы подключен к выходусоответствующего разряда из 1-й подгруппы разрядных выходов регистрасдвига модели пути, вход сдвига которого подключен к выходу первогоэлемента И, первый вход которого подключен к выходу первого триггера,вход установки н "0" первого триггера подключен к (К+1)-му выходу распределителя импульсов, вход установкив "1" первого триггера подключен квыходу первого элемента ИЛИ, выходпервого триггера подключен к первомувходу второго элемента И, второйвход которого подключен к выходу последовательности тактовых импульсовгенератора импульсов, выход второгоэлемента И подключен к входу распределителя импульсов, второй вход первого элемента И подключен к выходупоследовательности сдвинутых тактовыхимпульсов генератора импульсов, выходпоследовательности тактовых импульсовгенератора импульсов подключен к входу счетчика, выход которого подключенк входу останова генератора импульсови является выходом окончания работыустройства, вход запуска генератораимпульсов подключен к выходувторого триггера, вход которогоподключен к выходу первого элемента ИЛИ.