Резюме

Простейшими методами поиска (перебора) являются поиск в ширину и поиск в глубину. Ни один не позволяет найти оптимальные пути, и оба могут оказаться неэффективными.

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

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

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

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

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

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

Усечения, даваемые процедурой альфа-бета, могут быть дополнены рядом эвристических методов усечения. Однако они все привносят опасность того, что оптимальная игра может быть не найдена.