PART3 (Печатные лекции)

Способы формализации задач. Представление задач в пространстве состояний

Типичным представителем класса задач, для которых подходит представление (формализация) в пространстве состояний, является головоломка, известная как игра в пятнадцать. В ней используется пятнадцать пронумерованных (начиная с 1) подвижных фишек, расположенных в клетках квадрата 4x4. Одна клетка этого квадрата остается всегда пустой, так что одну из соседних с ней фишек можно передвинуть на место этой пустой клетки (изменив, тем самым, местоположение пустой клетки). На рис.1а изображены две конфигурации фишек. Рассмотрим задачу перевода начальной (первой) конфигурации в целевую (вторую) конфигурацию. Решением этой задачи будет подходящая последовательность сдвигов фишек, например: «передвинуть фишку 8 вверх, фишку 6 влево и т.д.». Более простым вариантом этой головоломки является квадрат 3x3 и восемь фишек на нем – пример соответствующей задачи показан на рис.1б.

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

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

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

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

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

Итак, формализация задачи с использованием пространства состояний включает выявление и определение следующих составляющих:

• формы описания состояний и описание исходной задачи;

• множество операторов и их воздействий на описания состояний;

• указание свойств целевых состояний (или же явное их задание).

Эти составляющие задают (неявно) пространство, в котором требуется провести поиск решения задачи.

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

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

Описание состояния этой задачи должно включать следующие элементы: местоположение (координаты) обезьяны в комнате – в горизонтальной плоскости пола и по вертикали (на полу обезьяна или на ящике), местоположение ящика на полу и наличие у обезьяны бананов. Эти элементы можно представить в виде четырехэлементного списка (ПолОб, ВертОб, ПолЯщ, Цель), где ПолОб и ПолЯщ – соответственно положение обезьяны и ящика на полу, ВертОб – это П или Я в зависимости от того, где находится обезьяна, на полу или на ящике, а Цель – это 0 или 1 в зависимости от того, достала ли обезьяна бананы или нет.

Операторы в задаче об обезьяне соответствуют четырем ее возможным действиям:

1. Подойти(X) – переход обезьяны к точке X горизонтальной плоскости пола;

2. Передвинуть(Y) – передвижение обезьяной ящика в точку Y пола;

3. Взобраться – обезьяна взбирается на ящик;

4. Схватить – обезьяна хватает связку бананов.

По сути, для решения задачи значимы лишь три точки:

То - точка первоначального местоположения обезьяны;

Тя - точка первоначального расположения ящика;

Тб - точка, над которой подвешены бананы.

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

Получающееся пространство состояний представлено деревом, показанном на рис.5.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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