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

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

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

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

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

Устройство содержит группы 1-6 элементов И, элементы И 7-15, группы 16 и 17 элементов ИЛИ, элементы ИЛИ 18-21, дешифратор 22, схему 23 сравнения, элементы 24-26 задержки, генератор 27 импульсов, регистр 28. блок 29 памяти, регистр 30 с разрядами данных 31, признака 32, левого 33 и правого 34 указателей, распределитель 35 импульсов с выходами 36-41, триггер 42, регистр 43, стековую память 44 и 45, триггер 46, группу 47 элементов И, входы 48 признака, вход 49 запуска, выход 50 признака конца работы, информационные выходы 51 устройства, элемент ИЛИ 52.

Вход генератора 27 является входом 49, а выход соединен с входом распределителя 35, входы сброса генератора 27, распределителя 35, стека 44 подключены к выходу элемента ИЛИ 52, второй вход которого является выходом 50, а первый вход подключен к первым входам элементов И группы 47 и выходу элемента И 7, первый вход которого подключен к выходу схемы 23,

(Л

первые входы которой подключены к выходам 32, а вторые входы подключены к выходу регистра 43, информационные входы которого яв-ляются входом 48, выходы элементов ИЛИ 16 соединены с входами дешифратора 22 и информационными входами регистра 28, выход которого соединен с адресным входом блока 29, выход которого соединен с информационным входом регистра 30, выходы разрядов 31 которого соединены через элементы И 47 с информационными выходами устройства, выход элемента ИЛИ 19 соединен черезэле- мент 25 с входом обратного сдвига стека 44, выходы разрядов 33 соединены через элементы И 3, ИЛИ 17 м И 5 с входами стека 44, вход прямого сдвига которого соединен с выходом элемета И 9, а рыходы подключены через элементы И 1 к первым входам элементов ИЛИ 16, выходы разрядов 34 соединены через элементы И 4, ИЛИ 16 и И 6 с входами стека 45, вход сброса которого подключен к выходу элемента ИЛИ 52, вход обратного сдвига подключен через элемент 26 к выходу элемента ИЛИ 20, вход прямого сдвига подключен к выходу элемента И 8, а выходы подключены через элементы И 2 к вторым входам элементов ИЛИ 16, выход 36 распределителя 35 соединен с входом элемента ИЛИ 18, выход которого подключен k первым входам элементов И 8 и 9, а второй вход подключен крез элемент 2$ к счетному входу триггера 42, входу 5 т .irrGpd 46, первому входу элемента И 15 и выходу дешифратора J2, а ьгорой вход подключен к выходу 37 выход 38 соединен с зходом записи регистра 30, выход 39 соединен с входом элемента И 7, выход 40 соединен с входами элементов И 4, 11 и 12, а выход 41 соединен с входами элементов И 3, 13 и 14, вход 49 соединен с входом григгера 42, прямой выход которого соединен с входами элементов И 1, 6, 9, 12 и 14, а инверсный выход соединен с входами элементов И 2, 5, 8, 11 и 13, входы элементов ИЛИ 20 и 19 подключены к выходам элементов И 12, 14 и 11, 13 соответственно, выходы элементов ИЛИ 17 подключены через элемент ИЛИ 21 к входу 5 триггера 46, ин верений выход которого подключен через элемент И 15 к сходу элемента ИЛИ 52.

В исходном состоянии генератор 27 остановлен, выходы распределителя 35 в нулевом состоянии.

8 первые ячейки стеков 44 и 45 записывается уникальный код, расшифровываемой дешифратором 22. Кроме того, в стек 45 записывается адрег. корневого узла и его содержимое погружается на одну ячейку

(входы записи не показаны). По входу 48 в регистр 43 записывается признак искомого узла. В дальнейшем содержимое стеков показывается.

Цикл работы устройства состоит из шести тактов. Импульсом по входу 49 запускается генератор 27 и обнуляется триггер 42. По импульсу с выхода 36 распределителя 35, проходящему через элементы ИЛИ 18 и И 8,

0 выталкивается содержимое стека 45 на одну ячейку (УК, 1). При этом на его выходах появляется адрес корневого узла, который через элементы группы 2 записывается в регистр 28. По импульсу с выхода 37 произ5 водится опрос дешифратора 22 на предмет поступления в регистр 28 УК (в данном случае элемент И 10 заперт). По импульсу с выхода 38 код узла дерева, адрес которого находится в регистре 28, принимается из

0 блока 29 в регистр 30. Признак узла с разрядов 32 сравнивается с признаком искомого узла, а в случае сравнения схема 23 выдает сигнал. При импульсе с выхода 39, когда искомый узел найден, срабатывает элемент

5 И 7, открывается группа 47 элементов И, и данные с разрядов 31 регистра 30 проходят на выход 51, а через элемент ИЛИ 52 затормаживается генератор 27, обнуляются стеки 44 и 45 и распределитель 35 По импульсу с

0 выхода 40 в стек 44 записывается адрес правого узла - сына с разрядов 34 через элементы И группы 4, элементы ИЛИ группы 17 и элементы И группы 5, затем стек 44 погружается на одну ячейку импульсом,

Ь прошедшим через элементы И 11 и ИЛИ 19, задержки 25, длительность задержки которого определяется временем записи в стек 44 (УК, 3,0). По импульсу с выхода 41 в стек 44 записывается адрес левого узла - сына с

0 разрядов 33 через элементы И группы 3 элементы ИЛИ группы 17 и элементы И группы 5, а затем стек 44 погружается на одну ячейку импульсом, прошедшим элементы И 13 и ИЛИ 19, задержки 25 (УК, 3, 2,

5 0). По импульсу с выхода 36 содержимое сгека 45 выталкивается на ячейку (УК), УК проходит элементы И группы 2, ИЛИ группы 16 и поступает на дешифратор 22. По импульсу с выхода 37 переходит в состояние

0 Г триггер 42, производя свопинг стеков 44 и 45. Теперь для каждого узла - отца из стека 44 ищутся узлы - сыновья, которые записываются в стек 45, Таким образом, свопинг производится в случае опустоше5 ния одного и заполнения другого стека (в вершине опустошенного стека содержится УК). Соответственно в процессе работы в стеке 45 последовательно храняется узлы нечетных уровней (УК, 2, 0), (УК 5, 4, 7, 6, 0), (2К, О, 0, 0, 0. О, 0, 0, 0, 0, 0, 0. 0. О, О, О, О, 0), а в

стеке 44 последовательно хранятся узлы четных уровней (УК, 3, 2, 0), (УК, О, О, О, 8, О, О, О, О). С выхода элементов И 10 импульс, задержанный на элементе 24 на время срабатывания триггера 42, проходит через элементы ИЛИ 18 и 19 и выталкивает содержимое стека 44 на ячейку (УК, 3, 2). Теперь по импульсу 38 в регистр 30 заносится код узла 2, а по импульсам 40 и 41 формируется содержимое стека 45 (УК, 5, 4. 0). По импульсу 36 содержимое стека 44 (УК, 3), а по импульсам 40 и 41 формируется содержимое стека 45 (УК, 5,4, 7, 6, 0). По импульсу 36 стек 44 опустошается и происходит свопинг стеков. Критерием конца просмотра в ширину всего дерева является заполненный нулями стек. Для рассматриваемого дерева это стек 45 с содержимым (УК, О, О, О, О, О, О, О, О, О, О, О, О, О, О, О, О, О,). В момент свопинга импульс с выхода элемента И 10 обнуляет триггер 46. Длительность импульса подобрана с условием, чтобы его хвост не проскочил через элемент И 15, открытый переброшенными им триггером. Если в какой-нибудь ячейке стека 45 содержится ненулевой код, то на выходе элемента ИЛИ 21 формируется импульс, переводящий триггер 46 в состояние 1. При этом при следующем свопинге импульс с выхода элемента И 10 не пройдет через элемент И 15. В противном случае на выходе 50 появляется импульс, который также блокирует генератор 27 и обнуляет распределитель 35 и стеки 44 и 45.

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

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

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

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

0 элементов И, с седьмого по девятый элементы И, пятый элемент ИЛИ, второй и третий элементы задержки, вторая стековая память, два триггера, причем выходы разрядов левого указателя второго регистра

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

0 И, а выходы подключены через элементы И второй группы к первым входам элементов ИЛИ первой группы, выходы разрядов правого указателя второго регистра соединены через элементы И пятой группы элементов

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

5 второй вход подключен к второму выходу распределителя импульсов, третий выход которого соединен с входом записи второго регистра, четвертый выход соединен с вторым входом первого элемента И, пятый выход соединен с вторыми входами элементов

I/I пятой группы, вторым входом пятого и первым входом шестого элементов И, а шестой выход соединен с вторыми входами элементов И четвертой группы, вторым входом седьмого и первым входом восьмого элементов И, вход запуска соединен с нулевым входом первого триггера, прямой выход которого соединен с вторыми входами элементов И второй и седьмой групп, вторыми входами третьего, шестого и восьмого элементов И, а инверсный выход соединен с вторыми входами элементов И третьей и

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

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

4V

Hi

50