广义Hanoi塔问题的动态规划算法  

Dynamic Programming Algorithm for the Generalized Towers of Hanoi Problem

作　　者：王晓东[1] 吴英杰[1] 

机构地区：[1]福州大学计算机科学与技术系,福建福州350002

出　　处：《小型微型计算机系统》2005年第5期869-872,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目 (60 172 0 17)资助 ;福建省自然科学基金项目 (A0 2 10 0 12 )的资助

摘　　要：基于动态规划算法思想,深入分析了广义Hanoi塔问题动态规划分割点的特征,给出动态规划分割点的简单计算公式,使得动态规划算法转化为一个非常简单的递归算法,由此可以迅速产生广义Hanoi塔问题的最优移动序列,从而彻底解决了广义Hanoi塔问题的最优移动序列问题.Studied the generalized tower of Hanoi problem based on the dynamic programming algorithm. The properties of the partition points for the dynamic programming algorithm are analyzed thoroughly. A very simple formula for the partition point is given, and the dynamic programming algorithm is then changed to a very simple recursive algorithm. The new algorithm can generate the optimal move sequence for the generalized tower of Hanoi problem very quickly, therefore solves the generalized tower of Hanoi problem thoroughly.

关 键 词：HANOI塔问题 动态规划算法 最优移动序列 

分 类 号：TP30[自动化与计算机技术—计算机系统结构]