Устройство для поиска информации Советский патент 1991 года по МПК G06F17/30 

Изобретение относится к вычислительной технике и может быть использовано в средствах аппаратной поддержки систем управления базами знаний (СУБЗ).

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

Стратегия ограниченного поиска в глубину состоит в следующем. Согл асно этой стратегии, осуществляется поиск в глубину до определенной границы и поиск по полному поддереву заданной глубины. При достижении заданной глубины выполняется возврат и инициируется исчерпывающий поиск по дереву заданной глубины. Глубина узла в дереве определяется по рекурсивному правилу: глубины корневого узла равна нулю; глубина неначального узла равна единице плюс глубина узла-отца.

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

На чертеже приведена структурная схема устройства.

Устройство содержит группу 1 элементов ИЛИ, группы 2-5 элементов И, элементы И 6-11, элементы ИЛИ 12 15, дешифраторы 16-19, схему 20 сравнения, элемент 21 задержки, стековую память 22. содержащую первый 23 и второй 24 разряды, регистры 25-27, разряды данных 28 и признака 29, левого 30, правого 31 и обратного 32 указателей регистра 27. блок 33 памяти, распределитель 34 импульсов, содержащий с первого по шестой выходы 35-40, генератор 41 импульсов, реверсивный счетчик 42, дешифратор 43, элементы ИЛ И 44 и 45, группу 46 адресных входов устройства, входы признака искомого узла 47. задания кода глубины 48 и запуска 49 устройства, выход 50 признака конца работы устройства и информационные выходы 51 устройства.

с VI ю

SJ

Каждый узел дерева занимает одну ячейку блока 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, ес/1и на выходе дешифратора 18 1, разряд 33 стека 22 устанавливается в 1. По импульсу с выхода 38. если на выходе дешифратора 19 1, разряд 24 стека 22 устанавливается в 1, 1 в разрядах 23 и 24 запрещают, выбор узлов-сыновей, так как соответствующие указатели пустые.

Если разряды 23 и 24 или разряд 23 находятся в О, то появляется сигнал на первом выходе дешифратора 17. подготавливая к открытию группу 5 элементов И. Если разряд 24 в О, то сигналом с второго выхода дешифратора 17 подготавливается к открытию группа 4 элементов И. Если разряды 23 и 24 в 1, то сигналом с третьего выхода дешифратора 17 подготавливается к

открытию группа 3 элементов И. Импульсом с выхода 39 открывается одна из групп 3-5 элементов И. и код левого, правого или обратного указателей из регистра 27 записывается через элементы ИЛИ группы 1 в регистр 26 и является адресом очередного узла в следующем цикле работы.

Если все указатели пусты, то на выходе дешифратора 16 появляется сигнал, устанавливающий на выходе 50 признак конца работы устройства. По импульсу с выхода 40 срабатывает один из элементов И 6, 8, 9. На этом такте модифицируется вершина стека в соответствии с решением по дальнейшему

просмотру дерева. Если срабатывает элемент И 8, то через элемент ИЛИ 14 разряд 23 устанавливается в 1, содержимое стека 22 погружается на ячейку и содержимое счетчика 42 уменьшается на единицу.

Если срабатывает элемент И 6. то происходят аналогичные операции, но в 1 устанавливается разряд 24. Если срабатывает элемент И 9, то содержимое стека 22 выталкивается на ячейку вверх и содержимое счетчика 42 увеличивается на единицу. Вершина 22 отражает результаты анализа указателей узла - отца.

Если в счетчике остается нулевой код

(достигнут узел с заданной глубиной), то дешифратор 43 расшифровывает его и 1 с его выхода блокирует на элементах ИЛИ 44 и 45 возможное прохождение О с выходов разрядов 23 и 24 на входы дешифратора 17,

обеспечивая возвращение к узлу-отцу. Таким образом, признак узла с заданной глубиной залегания в дереве сначала анализируется на предмет совпадения с признаком искомого узла, а затем узел имитируется под терминальный узел и поиск продолжается по другой ветви дерева. В случае, когда в дереве заданной глубины узел с искомым признаком отсутствует, це- лесообразноувеличить глубину просмотра и

повторить поиск.

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

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

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

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