Алгоритмы поиска решения (в пространстве состояний)

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

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

Известные алгоритмы поиска в пространстве состояний различаются несколькими характеристиками:

использованием или нет эвристической информации;

порядком раскрытия (обхода) вершин;

полнотой просмотра пространства;

направлением поиска.

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

Два основных вида слепых алгоритмов поиска, различающихся порядком раскрытия вершин – это алгоритмы поиска (перебора) вширь и поиска (перебора) вглубь. Как слепые, так и эвристические алгоритмы могут отличаться полнотой просмотра пространства состояний.

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

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

Слепой перебор.

Двумя основными разновидностями слепого перебора являются алгоритмы перебора вширь и перебора вглубь.

В алгоритме перебора вширь вершины раскрываются в том порядке, в котором они строятся. В алгоритме перебора в глубину прежде всего раскрываются те вершины, которые были построены последними.

Рассмотрим вначале простой алгоритм перебора вширь на дереве, который состоит из следующей последовательности шагов:

Шаг 1. Поместить начальную вершину в список нераскрытых вершин Open.

Шаг 2. Если список Open пуст, то окончание алгоритма и выдача сообщения о неудаче поиска, в противном случае перейти к следующему шагу.

Шаг 3. Выбрать первую вершину из списка Open (назовем ее Current) и перенести ее в список Closed.

Шаг 4. Раскрыть вершину Current, образовав все ее дочерние вершины. Если дочерних вершин нет, то перейти к шагу 2, иначе поместить все дочерние вершины (в любом порядке) в конец списка Open и построить указатели, ведущие от этих вершин к родительской вершине Current.

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

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

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

 

Рис. 5.5 Поиск в ширину

Глубину вершины в дереве можно определить следующим образом:

глубина корня дерева равна нулю;

глубина каждой некорневой вершины равна глубине ее родительской вершины плюс единица.

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

Основные шаги алгоритма ограниченного перебора вглубь таковы:

Шаг 1. Поместить начальную вершину в список Open.

Шаг 2. Если список Open пуст, то окончание алгоритма и выдача сообщения о неудаче поиска, в противном случае перейти к следующему шагу.

Шаг 3. Выбрать первую вершину из списка Open (назовем ее Current) и перенести ее в список Closed.

Шаг 4. Если глубина вершины Current равна граничной глубине, то перейти к шагу 2, в ином случае перейти к следующему шагу.

Шаг 5. Раскрыть вершину Current, построив все ее дочерние вершины. Если дочерних вершин нет, то перейти к шагу 2, иначе поместить все дочерние вершины (в произвольном порядке) в начало списка Open и построить указатели, ведущие от этих вершин к родительской вершине Current.

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

В отличие от поиска вширь, алгоритм поиска в глубину с ограничением глубины является неполным алгоритмом, поскольку вершины пространства состояний, расположенные ниже граничной глубины, так и останутся нерассмотренными.

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

Рис. 5.6. Поиск вглубину

 

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

Если перебор осуществляется на графах, а не на деревьях, необходимо внести некоторые очевидные изменения в указанные алгоритмы. В алгоритме полного перебора следует дополнительно проверять, не находится ли уже вновь построенная вершина в списках Open и Closed по той причине, что она уже строилась раньше в результате раскрытия какой-то вершины. Если это так, то такую вершину не нужно снова помещать в список Open. В алгоритме же ограниченного поиска вглубь кроме рассмотренного изменения может оказаться необходимым пересчет глубины порождающейся вершины, уже имеющейся либо в списке Open, либо в списке Closed.

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

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

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