14 16 Цель

Рисунок 10.11. Поиск в глубину для игры в "пятнашки" с 8 фишками, ограниченный 5 уровнями

На рис. 10.11. рассмотрен поиск в глубину на примере ГОЛОВОЛОМКИ с 8 фишками. Как отмечалось ранее, пустая клетка передвигается согласно одному из четырех возможных правил (вверх, вниз, влево и вправо). Числа рядом с состояниями указывают порядок, в котором они были рассмотрены и удалены из списка ореn. Не показаны состояния, на­ходящиеся в ореn, когда цель уже найдена. Глубина поиска в данном случае была огра­ничена пятью уровнями, чтобы не "затеряться в глубинах" пространства состояний.

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

Типичной проблемой, связанной с поиском, является комбинаторная сложность. При наличии нетривиальных проблемных областей количество вариантов, подлежа­щих рассмотрению, становится столь значительным, что наибольшее значение при­обретает существенное увеличение затрат ресурсов на исследование данных вариан­тов. Можно легко проанализировать причины того, почему это происходит. Для уп­рощения такого анализа предположим, что пространство состояний представляет собой дерево с единообразным ветвлением b. Это означает, что каждый узел в дереве, за исключением листьев, имеет точно b преемников. Предположим, что кратчайший путь решения имеет длину d, и в дереве на глубине d или меньшей отсутствуют ли­стья. Количество альтернативных путей длины d от начального узла равно b^d. При поиске в ширину количество рассматриваемых путей пропорционально b^d. Это обозначается как О (b^d). Итак, количество возможных путей очень быстро возрастает при увеличении их длины, что приводит к так называемому "ком6инаторному взрыву ".

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

для каждого уровня поиска находятся в списке open для глубокого поиска (когда цель расположена глубоко) или для пространства состояний С высоким коэффициентом ветвления этот поиск может быть весьма громоздким.

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

open, что может быть нежелательно, если путь к решению достаточно длинный.

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

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

Так что же лучше: поиск в глубину или поиск в ширину? На этот вопрос можно отве­тить так. Необходимо исследовать пространство состояний и проконсультироваться с экспертами в данной области. В шахматах, например, поиск в ширину просто невозможен. В более простых играх поиск в ширину не только возможен, но даже может оказаться единственным способом избежать проигрышей или потерь в игре.