1.2. ГОЛОВОЛОМКИ И ИГРЫ КАК ПРИМЕРЫ ЗАДАЧ

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

Головоломки и игры представляют собой неисчерпаемый источник примеров, полезных для иллюстрации и испытания

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

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

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

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