梵塔难题

梵塔难题

问题 有3个柱子(1，2，3)和3个不同尺寸的圆盘(A，B，C)。在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上。最初，全部3个圆盘都堆在柱子1上：最大的圆盘C在底部，最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。

归约过程

（1）移动圆盘A和B至柱子2的双圆盘难题；

（2）移动圆盘C至柱子3的单圆盘难题；

（3）移动圆盘A和B至柱子3的双圆盘难题。

由上可以看出简化了难题每一个都比原始难题容易，所以问题都会变成易解的本原问题。

讲述：梵塔问题的来源。

提问：一圆盘问题要走几步？两圆盘问题要走几步？三个、四个．．．等？

4、归约描述

问题归约方法是应用算符来把问题描述变换为子问题描述。

可以用状态空间表示的三元组合(S、F、G)来规定与描述问题；对于梵塔问题，子问题［（111）→(122)］，［(122)→(322)］以及［(322)→(333)］规定了最后解答路径将要通过的脚踏石状态(122)和(322)。

问题归约方法可以应用状态、算符和目标这些表示法来描述问题，这并不意味着问题归约法和状态空间法是一样的。