Устройство для поиска информации

ГОУЗ СОВЕТГКИХСОЦИАЛ ИГТИЧЕСКИХРЕСПУБЛИК 167 06 Г 15/40 НИЕ И ЕНИЯ ВИДЕТЕЛЬСТВУ К АВТОР К А ИНФОР 1отехнический инстиВ.М. Глушань льство СС 15/40, 198 льство СС 15/40, 198 зобретение отно ехнике и может тся к вычислительыть использовано в поддержки систем ий (СУБЗ).расширение функей за счет реализаченного поиска в поиска екототвах апп равлен азами зн бретения возможно ии огран ьн элеменементы раторы т 21 за- жащую лубину,лемен соде ака 29,указа- распреГОСУДАРСТВЕННЫЙ КГ" 1 ИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(56) Авторское свидетМ 1206810, кл. 6 06 ГАвторское свидетМ 1325514, кл. С 06 Г Стратегия ограниченного поиска в глубину состоит в следующем. Согласно это стратегии, осуществляется поиск в глубину до определенной границы и поиск по полному поддереву заданной глубины. При достижении заданной глубины выполняется возврат и инициируется исчерпывающий поиск по дереву заданной глубины, Глубина узла в дереве определяется по рекурсивному правилу: глубины корневого узла равна нулю; глубина неначального узла равна единице плюс глубина узла-отца,Поиск в глубину по некоторой ветвидерева завершается в случаях: при достижении целевого узла; при достижении терминаль(5 ") УС ТРОИ СТ В О ДЛ ЯМАЦИИ(57) Изобретенной технике, Цние функционареализации стиска в глубину,элементов ИЛИ, шесть элемИЛИ, пять дения, элемент зтри регистра, бимпульсов, генный счетчик с с ие относится к вычислительель изобретения - расширельных возмокностей за счет ратегии ограниченного по- Устройство содержит группу И, четыре группы элементов ентов И, шесть элементов шифраторов, схему сравнеадержки, стековую память, лок памяти, распределитель ератор импульсов, реверсивоответствующими связями. ного узла, при построении в хоузла, глубина которого превыша нрую граничную глубину.На чертеже приведена структурная схема устройства,Устройство содержит группу 1тов ИЛИ, группы 2 - 5 элементов И, элИ б - 11, элементы ИЛИ 12 15, дешиф16-19, схему 20 сравнения, эдержки, стековую память 22, рпервый 23 и второй 24 разряды, регистры25-27, разряды данных 28 и признлевого 30, правого 31 и обратного 32телей регистра 27, блок 33 памяти,делитель 34 импульсов, содержащий спервого по шестой выходы 35-40, генератор41 импульсов, реверсивныи счетчик 42, дешифратор 43, элементы ИЛИ 44 и 45, группу46 адресных входов устройства, входы признака искомого узла 47, задания кода глубины 48 и запуска 49 устройства, выход 50признака конца работы устройства и информационные выходы 51 устройства.Каждыи узел дерева занимает одну ячейку блока 33 и состоит иэ полей данных (либо укдзэтеля на данные), признака левого, правого и обратного указателей Признак предназначен для идентификации данных, хранящихся в узле. Левый и правый указатели задают адреса узлов - сыновс, а обратный указатель - адрес узла - отца. Пустой указатель задается кодом двоичного нуля, расшифровывается дешифраторами 16, 18 и 19. Корневой узел имеет пустой обратный указатель, а терминальные узлы содержат пустые левые и правые указатели,В исходном состоянии генератор 41 остановлен, выходы распределителя 34 и стека 22 нулевые По группе 46 входов в регистр 26 записывается адрес корневого узла, по входу 47 в регистр 25 - признак искомого узла, э по входу 48 в счетчик 42 - код глубины просмотра дерева,Цикл работы устройства состоит из шести тактов, Импульсом по входу 49 запускается генератор 41, каждый такт определяется импульсом на соответствующем выходе распределителя 34 Если не найден искомый узел и дерево не просмотрено, начинается новый цикл. По импульсу с выхода 35 код узла дерева, адрес которого находится в регистре 26, принимается в регистр 27. Признак этого узла сравнивается с признаком искомого узла, и в случае сравнения схема 20 выдает сигнал. Поля левого 30 и правого 31 указателей анализируются дешифраторами 18 и 19 на нулевой код, при обнаружении которого эти дешифраторы выдают сигналы. При появлении импульса с выхода 36, когда искомый узел найден в блоке 33, срабатывает элемент И 7, открывается группа 2 элементов И и данные проходят на выход 51, генератор 41 останавливается, распределитель 34 и стек 22 обнуляются, После обновления содержимого регистров 25 и 26 устройство можно использовать повторно. По импульсу с выхода 37, если на выходе дешифратора 18 "1", разряд 33 стека 22 устанавливается в "1". По импульсу с выхода 38, если на выходе дешифратора 19 "1", разряд 24 стека 22 устанавливается в "1", 1" в разрядах 23 и 24 запрещают, выбор узлов - сыновей, так как соответствующие указатели пустые,Если разряды 23 и 24 или разряд 23 находятся в "0", то появляется сигнал на первом выходе дешифратора 17, подготавливая к открытию руппу 5 элементов И, Если разряд 24 в "0", то сигналом с второго выхода дешифратора 17 подготавливается к открытию группа 4 элементов И. Если разряды 23 и 24 в "1", то сигналом с третьего выхода дешифратора 17 подготавливается кУстройство для поиска информации, содержащее группу элементов ИЛИ, четыре группы элементов И три регистра, блок памяти, элемент задержки, схему сравнения, шесть элементов И, четыре дешифратора, четыре элемента ИЛИ, генератор импульсов. стековую память, распределитель импульсов, причем вход генератора импульсов является входом запуска устройства, группа адресных входов которого соединена с первыми входами элементов ИЛИ группы, выходы которых соединены г, входами первого 5 10 15 20 25 30 35 40 45 50 55 открытию группа 3 элементов И, Импульсом с выхода 39 открывается одна из групп 3-5 элементов И, и код левого, правого или обратного указателей иэ регистра 27 записывается через элементы ИЛИ группы 1 в регистр 26 и является адресом очередного узла в следующем цикле работы,Если все указатели пусты, то на выходе дешифратора 16 появляется сигнал, устанавливающий на выходе 50 признак конца работы устройства, По импульсу с выхода 40 срабатывает один иэ элементов И б, 8, 9, На этом такте модифицируется вершина стека в соответствии с решением по дальнейшему просмотру дерева Если срабатывает элемент И 8, то через элемент ИЛИ 14 разряд 23 устанавливается в "1", содержимое стека 22 погружается на ячейку и содержимое счетчика 42 уменьшается нд единицу. Если срабатывает элемент И б, то происходят аналогичные операции, но в "1" устанавливается разряд 24 Если срабатывает элемент И 9, то содержимое стека 22 выталкивается на ячейку вверх и содержимое счетчика 42 увеличивается на единицу Вершина 22 отражает результаты анализа указателей узла - отца.Если в счетчике остается нулевой код достигнут узел с заданной глубиной), то дешифрэтоо 43 расшифровывает его и "1" с его выхода блокирует нэ элементах ИЛИ 44 и 45 возможное прохождение "0" с выходов разрядов 23 и 24 на входы дешифратора 17, обеспечивая возвращение к узлу-отцу. Таким образом, признак узла с заданной глубиной залегания в дереве сначала анализируется на предмет совпадения с признаком искомого узла, э затем узел имитируется под терминальный узел и поиск продолжается по другой ветви дерева, В случае, когда в дереве заданной глубины узел с искомым признаком отсутствует, целесообразно увеличить глубину просмотра и повторить поиск. Формула изобретениядешифратора и информационными входами первого регистра, выход которого соединен с адресным входом блока памяти, выход которого соединен с информационным входом второго регистра, выходы разрядов 5 данных которого соединены с первыми входами элементов И первой группы, выходы которых являются информационными выходами устройства, вход признака искомого узла которого соединен с информационным 10 входом третьего регистра, выход которого соединен с первым входом схемы сравнения, второй вход которой соединен с выходом признака узла второго регистра, выходы разрядов левого и правого указате лей которого соединены с первыми входами элементов И второй и третьей групп соответственно, выходы которых соединены с вторыми и третьими входами элементов ИЛИ группы соответственно, выход первого 20 дешифратора является выходом признака конца работы устройства и соединен с первым входом первого элемента ИЛИ, выход которого соединен с выходом останова генератора импульсов, выход которого сое динен с синхровходом распределителя импульсов, выход схемы сравнения соединен с первым входом первого элемента И, выход которого соединен с вторыми входами элементов И первой группы и вторым 30 входом первого элемента ИЛИ, первый выход распределителя импульсов соединен с входом разрешения записи второго регистра, выходы разрядов левого и правого указателей которого соединены с входами 35 второго и третьего дешифраторов, выходы которых соединены с первыми входами второго и третьего элементов И соответственно, выходы которых соединены с первыми входами второго и третьего элементов ИЛИ 40 соответственно, выходы которых соединены с входами установки первого и второго разрядов стековой памяти, вход сброса которой соединен с выходом первого элемента ИЛИ и входом сброса распределителя 45 импульсов, второй выход которого соединен с вторым входом первого элемента И, вторые входы второго и третьего элементов И соединены с третьим и четвертым выходами распределителя импульсов со ответственно, выходы разрядов обратного указателя второго регистра соединены с первыми входами элементов И четвертой группы, выходы которых соединены с четвертыми входами элементов ИЛИ группы, с первого по третий выходы четвертого дешифратора соединены с первыми входами с четвертого по шестой элементов И соответственно и с вторыми входами элементов И с второй по четвертую группу соответственно, третьи входы которых соединены с пятым выходом распределителя импульсов, шестои выход которого соединен с вторыми входами с четвертого по шестой элементов И, выходы четвертого и пятого элементов И соединены с вторыми входами второго и третьего элементов ИЛИ соответственно и с первым и вторым входами четвертого элемента ИЛИ соответственно, выход которого соединен с входом элемента задержки, выход которого соединен с входом обратного сдвига стековой памяти, вход прямого сдвига которой соединен с выходом шестого элемента И, отл ича ю щее с я тем,что, с целью расширения функциональных возможностей за счет реализации стратегии ограниченного поиска в глубину, в него вве. дены реверсивный счетчик, пятый дешифра тор, пятый и шестой элементы ИЛИ, причем выходы первого и второго разрядов стековой памяти соединены с первым и вторым входами четвертого дешифратора через пятыи и шестой элементы ИЛИ соответственно, вторые входы которых подключены к выходу пятого дешифратора, вход которого подключен к выходу реверсивного счетчика, суммирующий вход которого подключен к выходу шестого элемента И, вычитающий вход псдключен к выходу четвертого элемента ИЛИ, а информационный вход является входом задания кода глубины устройства..Даик Т СССР в арина 10 каз 2842 ВНИИП Составитель В,БородинТехред М,Моргентал Тираж 388 Подписноерственного комитета по изобретениям и открытиям и 113035, Москва, Ж, Раушская наб., 4/5 зводственно-издательский комбинат "Патент", г. Ужгоро