ТИПИС

1

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

Д. А. Перфильев

МЕТОДЫ ПОИСКА

Утверждено редакционно-издательским советом университета в качестве учебного пособия

Красноярск ИПК СФУ

2010

2

УДК 004.9(075) ББК 32.81я73 П26

Рецензенты:

Вдовенко В. В. – кандидат технических наук, доцент кафедры ИВТ Сибирского Аэрокосмического университета им. академика М. Ф. Решетнева; Морозов Н. Д. – кандидат экономических наук Красноярского НИИ

сельского хозяйства Россельхозакадемии.

Перфильев, Д. А.

П26 Методы поиска : учеб. пособие / Д. А. Перфильев. – Красноярск :

ИПК СФУ, 2010. – 104 с.

ISBN 978-5-7638-2005-8

В пособии проанализирована работа традиционных методов поиска и проблемы, связанные с разработкой интеллектуальных методов поиска и преследования цели. Рассмотрены понятие поиск, задачи поиска, выбор способа генерации для различных условий поиска, влияние апостериорной информации на определение «граничной глубины» поиска, влияние априорной информации на планирование оптимального пути поиска, организация n-направленного поиска.

Предназначено для студентов 3–4-го курсов направлений 220000 «Автоматизация и управление», 230000 «Вычислительная техника и информационные технологии», а также для специалистов в области информационных систем и технологий, для разработчиков интеллектуальных методов поиска и преследования цели.

УДК 004.9(075) ББК 32.81я73

Учебное издание

Перфильев Дмитрий Альбертович

МЕТОДЫ ПОИСКА

Учебное пособие

Редактор А. А. Быкова Компьютерная верстка: М. В. Саблина

Подписано в печать 28.06.2010. Печать плоская Формат 60×84/16. Бумага офсетная

Усл. печ. л. 6,04. Тираж 100 экз. Заказ № 2027

Издательско-полиграфический комплекс Сибирского федерального университета 660041, Красноярск, пр. Свободный, 82а

	Сибирский федеральный
	университет, 2010
ISBN 978-5-7638-2005-8	Оформление, оригинал-макет.
	ИПК СФУ, 2010

Введение	3

Введение

Разработки в области методов поиска и преследования цели известны с начала средних веков. Изначально методы применялись в мореходстве, позднее – в военном деле. Сегодня методы поиска стали неотъемлемым средством в решении задач оптимизации, управления предприятием, прогнозирования событий.

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

разработка способов изменения сектора обзора в процессе поиска и преследования цели;

разработка способов корректировки оценки и цели поиска;

разработка способов эффективного управления методами поиска в n-направленном режиме.

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

4		Введение

способных формировать модель пространства поиска и распределения целей.

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

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

Впервой главе учебного пособия рассматривается понятие поиск. Выделены задачи, связанные с разработкой управляемых методов поиска и применения их в n-направленном режиме. Изучены способы представления состояния, пространства состояний и пространства поиска.

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

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

5

Глава 1

ПОИСК, ЗАДАЧИ ПОИСКА И ПРОСТРАНСТВО СОСТОЯНИЙ

6	Глава 1. Поиск, задачи поиска и пространство состояний

§ 1.1. Понятие поиск

Понятие поиск достаточно детально раскрывается в работах [1–8]. Резюмируя информацию, представленную в указанных источниках, можно отметить, что поиск представляет собой комплекс действий, выполняемый поисковой системой (ПС) в процессе преследования цели. Комплекс действий включает последовательное выполнение следующих процедур:

1)генерации возможных или ограниченных априорной и/или апостериорной информацией о пространстве поиска решений;

2)проверки результатов генерации (идентификации полученных решений с целью поиска, их последующие хранение, учет, ранжирование и т. д.);

3)планирования способа достижения цели.

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

1) начальная ситуация или множество начальных состояний –

Sо={s1, s2, …, sm}, где m количество всех состояний множества Sо (open); 2) цель поиска или множество целевых состояний – St={s1, s2, …, sn},

где n количество всех состояний множества St (target);

3)множество операторов преобразования ситуаций – F ={f1, f2, …, fr}, где r количество операторов множества F;

4)множество текущих ситуаций (состояний) – Sc={s1, s2, …, sk}, где

k количество всех состояний множества Sc (current).

§ 1.1. Понятиепоиск	7

Задание множества текущих состояний не всегда является обязательным условием инициализации поиска. В большинстве случаев мощность множества текущих состояний Sc ограничивается возможным разнообразием видовых свойств состояний пространства поиска, что вполне достаточно для инициализации поиска (см. задачи в прил. 1, 2).

В самом общем виде, в начале поиска операторы множества F применяются к начальным состояниям множества So. При этом порождаются (генерируются) новые текущие состояния множества Sc. В [1, 7, 8] выделяют секторные ( [1; 2 – 1]) и круговой ( = 2 ) способы генерации. В общем случае генерацию состояний и результат генерации (текущее множество Sc) можно представить в виде следующего выражения:

So F = Sc.

Затем сгенерированные состояния идентифицируются с целью поиска состояниями множества St. В общем случае проверка состояний такова:

si Sc sjt St.

Если в результате проверки констатируется, что цель поиска не достигнута, то процедура генерации применяется уже к новым текущим состояниям множества Sc.

Пару последовательно выполняемых в поиске процедур «генерация + проверка» принято называть итерацией. В общем виде i-я итерация поиска может быть представлена следующей моделью:

… < Sci Fj = Sci+1 «+» si Sci+1 sjt St >i …

Схематично процесс поиска дан в виде обобщенного алгоритма на рис. 1.1. Для осуществления поиска вполне достаточно выполнять последовательно две процедуры: генерацию и проверку.

Можно принять за аксиому, что независимо от назначения, предметной области и видовых отличий в архитектуре поисковых систем и сегодня применяемые в них алгоритмы обработки данных и знаний содержат базовые процедуры поиска генерацию и проверку. На таком принципе была построена поисковая система в одном из первых прототипов экспериментальной экспертной системы (ЭС) DENDRAL. ЭС DENDRAL разрабатывалась в Станфортском университете США с 1975 по 1980-е годы и предназначалась для расшифровки соединений органической химии [3, 9].

8	Глава 1. Поиск, задачи поиска и пространство состояний

Начало

Ввод данных:

Sо, St, F

Sci F = Sci+1

Нет

si Sci+1 sjt St

Вывод

результатов

Конец

Рис. 1.1. Обобщенный алгоритм поиска

Центральное место в прототипе 1976 года ЭС DENDRAL занимала программа генерации химических структур CONGEN. Программа генерировала все возможные варианты организации молекулы. При этом возникали проблемы, связанные, в основном, с отсутствием ограничений в работе программы: генерировалось много таких структур, которые экспертами обычно без труда исключались уже на начальной стадии формирования.

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

Заметим, что в рассмотренной организации поиска ЭС DENDRAL отсутствует процедура планирования. На самом деле, в первых разработках поисковых систем планирование поиска выполнялась до его начала, поэтому в явном виде процедура планирования в организации поиска отсутствовала. Аналогичная организация поиска с явно отсутствующей процедурой планирования была реализована практически во всех первых раз-

§ 1.1. Понятиепоиск	9

работках поисковых подсистем для ЭС в период с 1970 по 1980-е годы

[3, 9–11].

Особенностью современного поиска является то, что для его реализации необходимо явное планирование, иначе поиск следует назвать слепым [2, 3, 5, 7] или анти-интеллектуальным [1], или неуправляемым [1, 6]. Для организации слепого или неуправляемого поиска, включающего только две базовые процедуры (генерацию и проверку), необходимо тщательное планирование. Подготовка к выполнению слепого поиска требует создания точной математической модели каждого состояния и пространства поиска, задания начального и целевого состояния и, главное, логически обоснованного способа остановки поиска. Поэтому практическая реализация слепого (неуправляемого) поиска в действительности трудоемка.

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

Основную идею планирования поиска, направленную на ограничение генерации, можно сформулировать следующим образом: «Порождать только те состояния и выбирать только то состояние, которое приводит к оптимальному пути достижения цели» [1–5, 7, 8].

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

<Li = {f1, f2, ..., fn}>,

где Li F.

В качестве примера можно привести описание планирования поиска, выполняемого в более позднем прототипе ЭС Heuristic DENDRAL (1978 год). В ЭС Heuristic DENDRAL планирование осуществлялось программой PLANNER. Основным назначением программы была выработка правил продукции, направленных на ограничение генерации структуркандидатов. Планирование выполнялось на основе априорной экспертной информации. Экспертные знания в виде продукционных правил первоначально вводились в поисковую подсистему ЭС.

10		Глава 1. Поиск, задачи поиска и пространство состояний

На рис. 1.2 представлена схема работы поисковой подсистемы ЭС

Heuristic DENDRAL.

Этап планирования

PLANNER		Правила
		продукции

Экспертные		Список
знания		оптимальных
		структур

Рис. 1.2. Схема работы поисковой подсистемы ЭС Heuristic DENDRAL

В процессе поиска программа PLANNER должна была обеспечить значительное сокращение структур-кандидатов, подлежащих дальнейшей проверке. Однако на практике значительного сокращения не произошло. Поэтому в дальнейших разработках ЭС DENDRAL (Мета-DENDRAL) были предприняты попытки разработки способов, позволяющих модифицировать априорную информацию, т. е. генерировать или удалять правила продукции и тем самым более гибко управлять поиском.

Принципиально процедура генерации может быть ограничена:

1)по направлению генерации в пространстве поиска;

2)по количеству итераций в некотором направлении;

3)изменением способа генерации от текущих результатов поиска или преследования цели.

Наглядно способы ограничения генерации представлены на схеме рис. 1.3, где показан поиск «принцессы» «чудовищем».