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

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