Меню
Главная
Авторизация/Регистрация
 
Главная 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 — глубина самого поверхностного решения; т — максимальная глубина дерева; е — предел глубины; С — стоимость решения; п — средняя стоимость одного шага.

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

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Популярные страницы