Глава 4. ПРЕДСТАВЛЕНИЯ, ДОПУСКАЮЩИЕ СВЕДЕНИЕ ЗАДАЧ К ПОДЗАДАЧАМ

4.1. ПРИМЕР ПРЕДСТАВЛЕНИЯ, ДАЮЩЕГО СВЕДЕНИЕ ЗАДАЧИ К ПОДЗАДАЧАМ

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

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

Имеется три колышка 1, 2 и 3 и три различных диска А, В и С. У дисков в центре имеется отверстие, так что их можно надевать на колышки. Сначала все диски расположены на первом колышке, больший диск С внизу, а меньший диск А — вверху.

Рис. 4.1. Задача о пирамидке (слева — начальное положение, справа — целевое).

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

Конечно эта задача может быть решена методами, использующими пространство состояний. Действительно, на рис. 4.2 показано полное пространство состояний для этой задачи. Граф имеет 27 вершин, каждая из которых представляет одно из допустимых расположений дисков на колышках. Обозначение каждой вершины графа описывает такое состояние,

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

Рис. 4.2. Граф для задачи о пирамидке.

Например, дуга, идущая от (113) к (123), означает, что (113) можно изменить на (123) посредством перекладывания диска В с колышка 1 на колышек 2. Это действие отражается надписью «Переложить этой, дуги. (Путь, выделенный жирными линиями на этом графе, представляет собой решение задачи.)

Задачу о пирамидке можно решить также простым методом сведения задачи к подзадачам. Один из путей сведения исходной задачи о пирамидке, изображенной на рис. 4.1, к совокупности

более простых задач связан со следующей цепочкой рассуждений:

1. Для того чтобы переложить все диски на колышек 3, мы, конечно, должны переложить на этот колышек диск С, причем в момент, непосредственно предшествующий перекладыванию диска С на колышек 3, последний должен быть свободным.

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

3. Затем можно сделать наш основной шаг, переложив диск С с колышка Г на 3, и перейти к решению оставшейся задачи.

Мы видим, что эти рассуждения позволяют свести исходную задачу к следующим трем задачам:

1. Задача с двумя дисками о перемещении дисков А и В на колышек 2:

2. Задача с одним диском о перемещении диска С на колышек 3:

3. Задача с двумя дисками о перемещении дисков А и В на колышек 3:

(кликните для просмотра скана)

Каждая из этих трех полученных задач меньше, а следовательно, и должна быть легче, чем исходная задача. Действительно, задача 2 может рассматриваться как элементарная, так как ее решение состоит ровно из одного хода. Используя подобную цепочку рассуждений, задачи 1 и 3 также можно свести к элементарным, как это схематически изображено на рис. 4.3. (Точно такая же схема сведения задачи к совокупности подзадач может быть применена и в случае, когда начальная конфигурация содержит произвольное число дисков.)

Графовая структура рис. 4.3 носит название «И/ИЛИ» графа (или графа" подзадач); она полезна для иллюстрации решений, получаемых методом сведения задачи к подзадачам. В этой и следующей главах мы подробно рассмотрим различные применения метода сведения задачи к подзадачам. Методы сведения задачи к подзадачам нашли применение к широкому кругу проблем, включая задачу получения выражения, которое было бы интегралом от некоторой функции, и задачу доказательства теорем планиметрии. Мы увидим также, что эти методы полностью аналогичны методам, используемым для вычисления наилучшего следующего хода в таких играх, как шашки или шахматы.