1.2. Головоломки и игры как примеры задач

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

Головоломки и игры представляют собой неисчерпаемый источник примеров, полезных для иллюстрации и испытания методов решения задач. Для вычислительных машин были написаны программы решения многих видов головоломок, достаточно трудных для человека. Были написаны также другие программы, которые побеждали опытных игроков в настольные игры, такие, как шахматы и шашки. Как говорит Минский (1968, стр. 12): «Игры и математические задачи берутся не потому, что они просты и ясны, а потому, что они при минимальных начальных структурах дают нам наибольшую сложность, так что мы можем заняться некоторыми действительно трудными ситуациями, относительно мало отвлекаясь на вопросы программирования». В игровых задачах и решениях головоломок возникли и отшлифовались многие идеи, которые оказались по-настоящему полезными для менее легкомысленных задач.

Рис. 1.1. Игра в пятнадцать (слева - начальная конфигурация, справа - целевая).

Для иллюстрации понятий, возникающих при решении задач, мы часто будем пользоваться головоломкой; известной игра в пятнадцать. В ней используется пятнадцать пронумерованных подвижных фишек, расположенных на площадке размером 4Х4 клетки. Одна клетка этой площадки остается всегда пустой, так что всегда одну из соседних с ней фишек; передвинуть на место этой пустой клетки, «передвинув», таким образом, и эту пустую клетку. Игра в пятнадцать иллюстрируется на рис. 1.1, на котором изображены две конфигурации фишек. Рассмотрим задачу перевода начальной конфигурации заданную целевую конфигурацию. Решением этой служит подходящая последовательность ходов, такая, мер, как «передвинуть фишку 12 влево, фишку 15 вниз и т.д.

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

1.3. Состояния и операторы

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

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

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

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

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

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

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