Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ
Посмотреть оригинал

Методы спуска по дереву решений

Неинформированный поиск

Рассмотренные выше примеры демонстрируют неинформированный (слепой) поиск, при котором отсутствует информация о том, в правильном ли направлении он ведется. Такой поиск представляет собой комбинаторную задачу, размерность которой определяется коэффициентом ветвления (Ь) и глубиной (d) по формуле bd+x. В худшем случае при поиске нужно развернуть bd+i - 1 узлов (сам целевой узел не развертывается), а в среднем — bd+l / 2 узлов.

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

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

Поиск в ширину. Вначале развертывается корневой узел, затем все его преемники, затем — преемники преемников и т.д. В отличие от поиска в глубину этот метод быстро обнаруживает решение, которое находится неглубоко, и не впадает в бесконечные углубления. Существенным недостатком данного метода является необходимость запоминать все узлы-предки, количество которых также определяется формулами комбинаторики. Для упомянутой задачи о восьми ферзях при расходе памяти 1000 байт на вершину объем требуемой памяти измеряется сотнями петабайтов (1 терабайт = = 1024 гигабайта, 1 петабайт = 1024 терабайта). Очевидно, что этот недостаток существенно ограничивает применимость метода.

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

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

Поиск в глубину с итеративным углублением — это поиск с ограничением глубины, которая постепенно увеличивается. Вначале устанавливается глубина 1, затем 2 и т.д. Несмотря на то что поиск каждый раз начинается сначала, это нс приводит к большим затратам. Затраты времени ненамного выше, чем при поиске в ширину, зато не требуется хранить данные о вершинах-предках.

Двунаправленный поиск. Эта разновидность поиска используется в тех случаях, когда конечное состояние нам известно, а найти нужно путь к цели. Один поиск запускается с начального узла, другой — с конечного. Задача завершается, когда оба поиска находят общий узел. Преимущество метода очевидно. Пусть глубина поиска

d = 6, а коэффициент ветвления b = 2. Поиск в одном направлении

6

потребует 26 = 64 шага, а двунаправленный поиск — 22 = 8 шагов. Недостатком данного метода является необходимость вычислимости узла-предшественника, что бывает не всегда возможным.

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

Сравнительные характеристики методов неинформированного поиска сведены в табл. 2.1.

Таблица 2.1

Характеристики методов неинформированного поиска

Метод

Полнота

Временная

сложность

Затраты

памяти

Оптимальность

Поиск в ширину

Да

?+'

Да

Поиск но критерию стоимости

Да

b1 + С/п

b1 + С/п

Да

Поиск в глубину

Пет

Ът

Ът

Нет

Поиск с ограничением глубины

Нет

6е

be

Нет

Поиск с итеративным углублением

Да

?

bd

Да

Двунаправленный поиск

Да

/у'/2

Ь

Да

Примечание. В таблице используются следующие обозначения: b — коэффициент ветвления; d — глубина самого поверхностного решения; т — максимальная глубина дерева; е — предел глубины; С — стоимость решения; п — средняя стоимость одного шага.

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

 
Посмотреть оригинал
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы