Глубина поиска.

В настоящее время под глубиной поиска понимают количество уровней в графе. Данная характеристика определяется как пространственная глубина поиска. Кроме того, необходимо ввести другую характеристику: временная глубина поиска.

Временная глубина – максимальное количество уровней от начального состояния до конечного.

Рис. 34.

Временная глубина поиска определяется исходя из количества имеющихся активных процессов. Если считать активный процесс единственный, то временная глубина поиска определяется как некоторая величина ≤ m, где m – общее количество состояний в графе.

Поисковые процедуры делятся:

1. по выбору начального и конечного состояния

а) поиск от данных (прямой поиск)

б) поиск от цели (обратный поиск)

Обратный поиск применим, если конечное состояние заранее задано. В этом случае задача поиска понимается как задача анализа. В прямом поиске не требуется знать конечное состояние. Ограничения могут накладывать общие свойства на будущие получаемые состояния. В данном случае задача поиска понимается как задача синтеза.

2. по направлению обхода поиск бывает:

а) в глубину

б) в ширину

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

При поиске на графе (но не на дереве) получаемые потомки обязательно проверяются на повторное вхождение. Генерироваться должны только новые вершины. Для реализации этих действий в поисковой процедуре должен быть предусмотрен некоторый механизм проверки и некоторая структура для хранения ранее просмотренных величин. Поиск в пространстве состояний можно вести в двух направлениях: от исходных данных задачи к цели и в обратном направлении от цели к исходным данным.

При поиске на основе данных, исследователь начинает процесс решения задачи, анализируя ее условие, а затем применяет допустимые ходы или правила изменения состояния. В процессе поиска правила применяются к известным фактам для получения новых фактов, которые, в свою очередь, используются для генерации новых фактов. Этот процесс продолжается до тех пор, пока мы, если повезет, не достигнем цели.

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

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

Наконец заметим, что в обоих случаях (и при поиске на основе данныхи при поиске от цели)исследователь работает с одним и тем же графом пространства состояний, однако порядок и число состояний в процессе поиска могут различаться. Какую стратегию поиска предпочесть, зависит от самой задачи. При этом следует учитывать сложность правил, " форму" пространства состояний, природу и доступность данных задачи. Все это может изменяться от задачи к задаче.

Как пример зависимости сложности поиска от выбора стратегии рассмотрим задачу, в которой нужно подтвердить или опровергнуть утверждение " Я потомок Томаса Джефферсона". Положительным решением является путь по генеалогическому дереву от " Я" до " Томас Джефферсон".Поиск на этом графе можно вести в двух направлениях: начиная от вершины " Я" строить цепочку предков к вершине " Томас Джефферсон", или начиная с вершины " Томас Джефферсон" анализировать цепочку его потомков.

Простая оценка позволяет сравнить сложность поиска в обоих направлениях. Томас Джефферсон родился примерно 250 лет назад. Если считать, что новое поколение рождается каждые 25 лет, то длина искомого пути составляет примерно 10. Поскольку каждый потомок имеет двух родителей, то путь от " Я" требует анализа 2¹⁰ предков. С другой стороны, поиск от вершины " Томас Джефферсон" требует анализа большего числа состояний, поскольку родители обычно имеют более двух детей (особенно это касается восемнадцатого и девятнадцатого столетий). Если допустить, что каждая семья имеет в среднем троих детей, то в процессе поиска нужно проанализировать З¹⁰ вершин генеалогического дерева. Таким образом, этот путь сложнее. Заметим, однако, что оба способа поиска имеют экспоненциальную сложность.

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

1. Цель поиска (или гипотеза) явно присутствует в постановке задачи или может быть легко сформулирована. Например, если задача состоит в доказательстве математической теоремы, то целью является сама теорема. Многие диагностические системы рассматривают возможные диагнозы, систематически подтверждая или отвергая некоторые из них способом поиска от цели.

2. Имеется большое число правил, которые на основе полученных фактов позволяют продуцировать возрастающее число заключений или целей. Своевременный отбор целей позволяет отсеять множество возможных ветвей, что делает процесс поиска в пространстве состояний более эффективным (рис. 3.10). Например, в процессе доказательства математических теорем число используемых правил вывода теоремы обычно значительно меньше количества, формируемого на основе полной системы аксиом.

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

Таким образом, при поиске цели подходящие правила применяются для исключения неперспективных ветвей поиска.

Поиск на основе данных применим к решению задачи в следующих случаях.

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

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

3. Сформировать цель или гипотезы очень трудно. Например, при использовании системы DENDRAL изначально может быть очень мало информации о возможной структуре соединения.

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

ЛЕКЦИЯ 13, 14.

Среди алгоритмов обхода пр-ва состояний по направлению выделяют систематический алгоритм и эвристический.

В первом случае каждое текущее состояние не оценивается на предмет близости его к целевому состоянию.

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

Эффективность обхода пр-ва состояний также определяется соотношением коэффициентов ветвления и коэффициентов сужения. Рассмотрим некоторую абстрактную задачу:

Пусть у каждой семьи имеется 3 детей. Необходимо определить, является ли Иван потомком Евгения. Глубина поиска 250 лет, смена поколений 25 лет.

Решение:

Если обходить данное пространство от цели к данным (обратный поиск), то коэффициент сужения будет равен 2, а количество просматриваемых вершин определяется коэффициентом ветвления.

На временном интервале 250 лет пространство состояний будет содержать 10 уровней => при обратном обходе количество анализируемых вершин определяется величиной L = 1…10(3⁴).

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

Обход в глубину реализуется последовательно упорядоченной генерацией текущих потомков. При этом из списка новых состояний будет браться 1-е генерируемое состояние.