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

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

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

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

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

Устройство содержит группу 1 элементов ИЛИ, группы 2-5 элементов И, элементы И 6-11, элементы 12-15, дешифраторы 16- 19, схему 20 сравнения, элемент 21 задержки, стековую память 22 с первым 23 v, вторым 24 разрядами, регистры 25-27, разряды 28 данных и 29 признака, левого 30,

О 00

о о

CJ

правого 31 и обратного 32 указателей регистра 27, блок 33 памяти, распределитель 34 импульсов с выходами 35-40, генератор 41 импульсов, реверсивный счетчик 42, дешифратор 43, элементы ИЛИ 44-47, элемент 48 задержки, элемент ЗАПРЕТ 49, регистр 50, схему 51 сравнения, группу 52 адресных входов устройства, входы признака искомого узла 53, задания кода начальной глубины 54, задания кода предельной глубины 55 и запуска 56 устройства, выход 57 признака конца работы устройства и информационные 58 выходы устройства. В исходном состоянии генератор 41 остановлен, выходы распределителя 34 и стека 22 - нулевые. По группе 52 входов в регистр 26 записывается адрес корневого узла, по входу 53 в регистр 25 - признак искомого узла, по входу 54 в счетчик 42 - код начальной глубины, а по входу 55 в регистр 50 - код предельной глубины просмотра дерева. Цикл работы устройства состоит из шести тактов. Импульсом по входу 56 запускается генератор 41. По импульсу с выхода 35 код узла дерева, адрес которого находится в регистре 26. принимается в регистр 27. Признак узла сравнивается с признаком искомого узла, и в случае сравнения схемы 20 выдает сигнал. Поля левого 30 и правого 31 указателей анализируется дешифраторами 18 и 19 на нулевой код, при обнаружении которого дешифраторы выдают сигналы. При импульсе с выхода 36, когда искомый узел найден, срабатывает элемент И 7. Открывается группа 2 элементов И. Данные проходят на выход 58. Через элемент ИЛИ 47 затормаживается генератор 41 и через элементы ИЛИ 47 и 12 обнуляются распределитель 34 и стек 22. По импульсу с выхода 37, если на выходе дешифратора 18 1, разряд 23 стека

22устанавливается в 1. По импульсу с выхода 38, если на выходе дешифратора 19 1, разряд 24 устанавливается в 1. Единица в разрядах 23 и 24 запрещает выбор узлов - сыновей, так как соответствующие указатели пусты. Если разряды 23 и 24 или

23находятся в О, то появляется сигнал на первом выходе дешифратора 17, подготавливая к открытию группу 5 элементов И. Если разряд 24 в О, то сигналом с второго выхода дешифратора 17 подготавливается к открытию группы 4 элементов И. Если разряды 23 и 24 в 1, то сигналом с третьего выхода дешифратора 17 подготавливается к открытию группа 3 элементов И. Импульсом с выхода 39 открывается одна из групп 3-5 элементов И, и код левого, правого или обратного указателей из регистра 27 записывается в регистр 26. Если все указатели пусты (просмотрено дерево на текущую глубину, код которой записан в счетчике 42), то на выходе дешифратора 16 появляется положительный перепад, а с выхода элемента ЗАПРЕТ 49 снимается импульс, длительность которого равна длительности задержки элемента 48 и составляет три, который через элемент ИЛИ 46 увеличивает на единицу содержимое счетчика 42 и через элемент ИЛИ 12 обнуляет распределитель 34 и

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

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

на ячейку вверх, а содержимое счетчика 42 увеличивается на единицу. Если в счетчике остается нулевой код (достигнут узел с текущей глубиной), то сигнал с выхода дешифратора 43 блокирует на элементах ИЛИ 44 и 45

прохождение О с выходов разрядов 23 и 24 на входы дешифратора 17, обеспечивая возвращение к узлу-отцу. Таким образом, признак узла с текущей глубиной залегания в дереве сначала имитируется под терминальный узел и поиск продолжается по другой ветви дерева. В случае, если в дереве с текущей глубиной узел с искомым признаком отсутствует, увеличивается на 1 глуби- на просмотра и поиск повторяется.

Увеличение глубины происходит до момента, когда содержимое счетчика 42 и регистра 50 уравниваются (достижение предельной глубины поиска), и сигнал с выхода схемы 52 появляется на выходе 57, блокирует генератор 41 и обнуляет распределитель 34 и стек 22.

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

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

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

27

Изобретение относится к вычислительной технике и может быть использовано в средствах аппаратной поддержки систем управления базами знаний (СУБЗ) Цель изобретения - расширение функциональных возможностей за счет реализации стратегии ступенчатого поиска в глубину. Поставленная цель достигается тем. что устройство содержит группу 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-47, элемент 48 задержки, элемент запрет 49, регистр 50, схему 51 сравнения, группу 52 адресных входов устройства, входы признака искомого узла 53, задания кода начальной глубины 54, задания кода предельной глубины 55 и запуска 56 устройства, выход 57 признака конца работы устройства и информационные 58 выходы устройства. 1 ил. Ё