ВУЗ:
Составители:
Рубрика:
40
3.8.5. РЕДУКЦИЯ ЗАДАЧ
Кроме уже рассмотренного подхода – представления задач в про-
странстве состояний – для решения ряда задач возможен и другой, бо-
лее сложный подход. При этом подходе производится анализ исходной
задачи с целью выделения такого набора подзадач, решение которых
означает решение исходной задачи. Каждая из выделенных подзадач в
общем случае является более простой, чем исходная, и может быть
решена каким-либо методом, в том числе – с использованием про-
странства состояний. Но можно продолжить процесс, выделяя после-
довательно из возникающих задач подзадачи – до тех пор, пока не по-
лучим элементарные задачи, решение которых уже известно. Такой
путь называется подходом, основанным на сведении задач к подзада-
чам, или на редукции задач.
Для иллюстрации этого подхода рассмотрим один из вариантов
известной головоломки – задачи о пирамидке, или ханойской башне.
В ней используются три колышка (обозначим их буквами A, B, C) и
три диска разного диаметра, которые можно нанизывать на колышки
через отверстия в центре. В начале все диски расположены на колыш-
ке А, причем диски меньшего диаметра лежат на дисках большего
диаметра – рис. 9 (диски занумерованы в порядке возрастания диамет-
ра). Требуется переместить все диски на колышек С, двигая их по оче-
реди и соблюдая следующие правила. Перемещать можно только са-
мый верхний диск, и нельзя никакой диск класть на диск меньшего
размера. На рисунке 9 показаны начальное и целевое состояния задачи
о пирамидке.
Эта задача легко может быть формализована в пространстве со-
стояний: состояние задачи задается списком из трех элементов, каж-
дый из которых указывает местоположение соответствующего диска
(первый элемент – первого диска, второй – второго, третий – третьего).
Начальное состояние описывается списком (ААА), а целевое – (ССС).
При этом предполагается, что если на одном колышке находится более
одного диска, то любой больший диск расположен ниже любого
меньшего.
A
B
C
1
2
3
A
B
C
1
2
3
⇒
⇒⇒
⇒
Рис. 9
Страницы
- « первая
- ‹ предыдущая
- …
- 38
- 39
- 40
- 41
- 42
- …
- следующая ›
- последняя »
