Введение в теорию игр. Жариков И.А - 41 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

41
а)
C
B
A
б)
A
B
C
1
2
3
1
2
3
Рис. 10
Посмотрим, как можно решить эту задачу методом редукции за-
дач. Ключевая идея редукции состоит в том, что для перемещения всей
пирамидки необходимо переложить самый нижний диск 3, а это воз-
можно, только если располагающаяся над ним пирамидка из двух
меньших дисков 1 и 2 перенесена на колышек В (рис. 10, а). Таким
образом, исходную задачу можно свести к следующим подзадачам:
1) переместить диски 1 и 2 с колышка А на колышек В (1, 2 : А → В);
2) переместить диск 3 с колышка А на колышек С (3 : А → С);
3) переместить диски 1 и 2 с колышка В на колышек С (1, 2 : В → С).
На рисунке 10, б показано исходное состояние для третьей задачи.
Каждая из трех указанных задач проще исходной: действительно, в
первой и в третьей задачах требуется переместить всего два диска, вто-
рая же задача может рассматриваться как элементарная, так как ее ре-
шение состоит ровно из одного хода – перемещения диска. В первой и
третьей задачах можно вновь применить метод редукции задач, и свести
их к элементарным задачам. Весь процесс редукции можно схематиче-
ски представить в виде дерева на рис. 11. Вершины дерева соответст-
вуют решаемым задачам
/
подзадачам, причем листья дерева – элемен-
тарным задачам перемещения дисков, а дуги связывают редуцируемую
задачу с ее подзадачами.
Заметим, что рассмотренная стратегия сведения задачи к сово-
купности подзадач может быть применена и в случае, когда начальная
конфигурация задачи о пирамидке содержит не три, а большее число
дисков. В любом случае существенным является порядок, в котором
решаются результирующие задачи: например, вторая задача не может
быть решена ранее первой.
Таким образом, в случае подхода, основанного на редукции задач,
мы получаем также пространство, но состоящее не из состояний, а из
задач/подзадач (точнее, их описаний). При этом роль, аналогичную
операторам в пространстве состояний, играют операторы, сводящие
задачи в подзадачи. Точнее, каждый оператор редукции преобразует
описание задачи в описание множества результирующих подзадач,
причем это множество таково, что решение всех подзадач обеспечива-
ет решение редуцированной задачи.

Страницы