1.3. СОСТОЯНИЯ И ОПЕРАТОРЫ

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

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

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

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

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

Решение игры в пятнадцать можно было бы получить, используя процесс поиска (перебора), при котором прежде всего применяют операторы к начальному состоянию, с тем чтобы получить новые состояния, - к которым также применяют операторы, и т. д. до тех пор, пока не будет построено состояние, отвечающее цели. Методы организации такого поиска целевого состояния удобнее всего объяснять, пользуясь представлением в виде графа рис. 1.2.

Рис. 1.2. (см. скан) Часть графа для игры в пятнадцать.

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

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