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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

>s 6 06 F 15/40

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4720753/24 (22) 20.07.89 (46) 07.09.91. Бюл. № 33 (71) Таганрогский радиотехнический институт им, B.Ä.ÊàëìûêoBà (72) А.В.Пришибской, В.M. Глуша нь и В.М.Курейчик (53) 681.325(088.8) (56) Авторское свидетельство СССР

¹ 1228116, кл, G 06 F 15/40, 1985.

Авторское свидетельство СССР

¹ 1325514, кл. G 06 F 15/40, 1986, (54) УСТРОЙСТВО ДЛЯ ПОИСКА ИНФОРМАЦИИ

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

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

Из теории эвристического поиска известно, что для большинства систем искусственного интеллекта, в которых решается задача поиска в одном пространстве состояний, стратегия поиска в ширину дает большие преимущества в сравнении с поиска B глубину, Известно несколько экспертных систем (например R1, MOGLEN), в которых управляющая структура задает метод выбора пути решения — поиск в ширину, Реализация этого метода в устройстве позволит повысить эффективность поиска в древовидных структурах, . На чертеже приведена структурная схема устройства,,«: Я Ы „„1675906 A l (57) Изобретение относится к вычислительной технике, Цель изобретения — расширение функциональных возможностей за счет реализации стратегии поиска методом полного перебора в ширину. Устройство содержит две группы элементов ИЛИ, семь групп элементов И, девять элементов

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

Устройство содержит группы 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, i675906

3 1

50 первые входы котс)рой падкгначены к ныхадам 32, а Вторые н;(ады подключены к выходу регистра 43, ин >ормацианные входы которо..а явг)я)отся входом 48, выходы элементов ИЛИ 16 сгоединены с входами дешифратора 22 и информационными входами регистра 28, выход которого соединен с адресным нходс)м бг ока 29, выход кстарого соединен с, информационным входом регистра 30, выходы разрядон 31 которого соединены ереэ элементы И 47 с информационными выходами устройства, выход элемента ИЛИ l9 соединен через элемент 25 с входом обратнога сднига стека 44, выходы разрядов 33 соединены через элементы И 3, I JIM 17 и И 5 с Входами стека 44„ вход прямого сдни.а катсрого соединен с выходам элемен а И!!, а выходь) подключены .ерез элеме)п.-.. И 1 первым вхоцам элементов ИЛИ I6, выходы разрядон 34 соединены через элементы И 4, ИЛИ 16 и И 6 с входами стека 45, нхад сброса которап) падкл)ачен I: выходу элемента ИЛИ 52, вход обратного сдвига г:од(лючен через элемент

26 к выходу элемента ИЛИ 2С, нход прямого сдвига подключен к выходу элемента И 8, i выходы подключе)..ы чере: элементы И 2 к

BTGpbl) Входам элементов 4Л И 1 6, ны)(од . 6) распределителя 35 соединен cВходом :э:-лемента ИЛИ 18, выход I(oò(:Iëio подключен ., первым входам глеменTQВ I/1 8 и 9,;;i нтс;, О:.) вход подклю ен -:ере:- элемен1 24 v, сче ному входу тр iI) el:a 42, н o,„у 5 - .иггера ";6, первому входу эле. ента I i 15 Выхсду це шифаатора 22, а В горой I).: lj I !)Дкл)с:чен к ныхаду 37, Bblxop, 38 саед,i .ен с вход гм з"-.:писи регистра 30, выход, З соедине) с входом элемента И <, Выход 40 соедлнен с входами элементов И 4, 11 и 12, а выход 41 соединен с нходамл элементов И 3, 13 и 14, вход 49 соединен с Входам;. риггера 42, и рямой выход которого соединен с входами элементов И 1, 6, 9, . I2» !4., а инверсный

В ы х ОД с О еД и н е н с В х од ":) м и э л e I - ) е н ) О н И г ., 5., 8, 11 и )3, входы .элементов ИЛИ 20 и 19 подключены к выходам элементов И 2, 14 и 11., 13 сс1ответстненно, нь!ходы элементов

ИЛИ 17 подключены через:-:г)емент ИЛИ 21 к ВХОДУ .) триггера 16 ив верон .:й эы)(;)Д t(0торого подкгпочен врез эл эмент И 15 к GxQду элемента ИЛИ 52.

В исходном состоянии генера гор 27 Остановлен, выходы распределителя 35 в нулезом сас;:оянии, В первые ячейки стеков 44 и 45 записывае)ся унлкальный код, расшлфроны: leмый ДешифоатОрам 22, Кроме тОга, aО:.тек 45 записывав гся йдоес I(<3pII(.ÂÃIÃ() узла и его содеожимае погружается на одну я- ейку (нходы записи не показаны). По входу 48 в регистр 43 записывается признак искомого узла, В дальнейшем содержимое стеков показывается.

Цикл работы устройства состоит из шести тактов, Импульсом па входу 49 запускается генератор 27 и обнуляется триггер 42.

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

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

i;IcI(GMbli. узел найден, срабатывает элемент

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

44 и 45 и распределитель 35. По импульсу с выхода 40 в стек 44 записывается адрес пранога узла — сына с разрядов 34 через элементы И группы 4, элементы ИЛИ группы

17 и элеме ITbl И группы 5, затем стек 44 погружается на одну ячейку импульсом, прошедшим через элементы И 11 и ИЛИ 19, задержки 25, длительность задержки которогс определяется временем записи в стек

44 (УК, 3,0). По импульсу с выхода 41 в стек

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

16 и поступает на дешифратор 22. По импульсу с выхода 37 переходит в состояние

" 1" триггер 42, произвоця свопинг стеков 44 и 45. Теперь для каждого узла — отца из стека 44 ищутся узлы — сыновья, которые записываются в стек 45. Таким. Образом, свопинг производится в случае опустошения одного и заполнения другого стека (в вершине опустошенного с ека содержится

УК). Соответственно в процессе работы в стеке 45 последовательно храняется узлы нечетных уровней (УК, 2, 0), (УК5, 4, 7, 6, 0),(2К, О, О, О. О, О, О, О, 0, О, О, 0, 0, О, О, О, О, О), а в

1675906 стеке 44 последовательно хранятся узлы четных уровней (УК, 3, 2, О), (УК, О, Î, О, 8, О, О, О, О). С выхода элементов И 10 импульс, задержанный на элементе 24 на время срабатывания триггера 42, проходит через элементы ИЛИ 18 и 19 и выталкивает содержимое стека 44 на ячейку (УК, 3, 2).

Теперь по импульсу 38 в регистр 30 заносится код узла 2, а по импульсам 40 и 41 формируется содержимое стека 45 (УК, 5, 4, 0).

По импульсу 36 содержимое стека 44 (УК, 3), а по импульсам 40 и 41 формируется содержимое стека 45 (YK. 5, 4, 7, 6, О). По импульсу

36 стек 44 опустошается и происходит свопинг стеков. Критерием конца просмотра в ширину всего дерева являет я заполненный нулями стек. Для рассматр,BaeMoro дерева это стек 45 с содержимым (УК, О, О, О, О, О, О, О, О, О, О, О, О, О, О, О, О, О,). В момент свопинга импульс с выхода элемента И 10 обнуляет триггер 46. Длительность импульса подобрана с условием, чтобы его "хвост" не проскочил через элемент И 15, открытый переброшенными им триггером. Если в какой.-нибудь ячейке стека 45 содержится ненулевой код, то на выходе элемента ИЛИ 21 формируется импульс, переводящий триггер 46 в состояние "1". При этом при следующем свопинге импульс с выхода элемента

И 10 не пройдет через элемент И 15. В противном случае на выходе 50 появляется импульс, который также блокирует генератор 27 и обнуляет распределитель 35 и стеки

44 и 45.

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

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

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

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

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

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

30 И, а выходы подключены через элементы И второй группы к первым входам элементов

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

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

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

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

1675906

Составитель П, Чистобородов

Техред М,Моргентал Корректор Л.Бескид

Редактор Г. Гербер

Заказ 3004 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат Патент", г. Ужгород, ул.Гагарина, 101

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

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

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