Obeta

汉诺塔问题的思考和动态规划的简单解读

动态规划是一种通过“大而化小”的思路解决问题的算法,也就是将需要解决的问题细分为子问题,子问题再可以细分下去,直至能得到一个结果为止.汉诺塔问题就可以使用这种算法思想解决.

动态规划介绍

第一次接触动态规划算法的时候是大二,那时候看的我很懵,网上的很多解释都是一大堆纯理论,看的似懂非懂,一直拖到今天的一个面试,然后被面试官出的一些简单算法题给虐了,心里还是很失落的,但是没办法嘛,毕竟自己这方面确实不够好,于是下定决心要搞懂.

按照惯例来一个动态规划的理论解释:

动态规划算法通常基于一个递推公式及一个或多个初始状态.当前子问题的解将由上一次子问题的解推出.

通俗点的解释:

也就是说一个大问题由几个子问题组成(子问题也有子子问题),求解出子问题后大问题的结果也就出来了,下面来看一个小例子

阶梯问题

有一个 n 级的阶梯,每次只能上一步或者两步,问我从 0 级要到 n 级阶梯有多少种方法?

我们先定义一个函数(应该说是一种关系)fn(n)=m,含义是 n 级阶梯有 m 种方法上去,下面我们试试写出 1 到 6 级阶梯的关系:

fn(1) = 1;//很明显一级阶梯只有一种方法上去
fn(2) = 2;//有1,1和2
fn(3) = 3;//有1,1,1和1,2和2,1
fn(4) = 5;//有1,1,1,1和,1,2,1和2,1,1和2,2和1,1,2
fn(5) = 8;
fn(6) = 13;
//....

从上面的一些式子能观察出一些规律吗?

通过观察我们会发现:fn(n) = fn(n-1) + fn(n-2),当然这并不令人信服,我们需要一个理由.

可以尝试使用动态规划中的思想,将一个问题细分为几个子问题.因为阶梯一次只能上一步或者两步,那么我们要上 n 级阶梯的前"一步或者两步"位置是在 n-1 级(走一步)或者 n-2 级(走两步),这里暗含了一个隐藏的状态转移方程:fn(n) = fn(n-1) + fn(n-2).

知道了核心的部分,那么代码就呼之欲出了:

function step(n) {
	if (n === 1) return 1;
	if (n === 2) return 2;

	return step(n - 1) + step(n - 2);
}

console.log(step(6));

汉诺塔问题

汉诺塔问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘.最后需要移动多少次才可以全部移动到第三根柱子上?

说真的我之前真没碰见过这类动态规划问题,这也足以说明我算法知识有多薄弱了....面试时候拿到这个问题想了半天,虽然知道这是动态规划的问题,也是想了半天才有头绪,用时间之久顿时感觉自己废了....

废话不多说了,希望自己以后遇到这类问题不会再出糗了.

这个问题和上面那个阶梯问题类似,找到子问题,但是这个更抽象,有时候你甚至会感觉自己脑子不够用,大脑处理这类递归的问题是很有负担的(这也是我面试时候想了那么久的原因),但是我们可以用较少的数据来说明问题.

先定义三个柱子为:ABC,然后试试将 A 上的三个圆盘根据规则移动到 C 上.为了方便描述将圆盘从上至下依次命名为 1,2,3

A 是开始柱子,B 是过渡柱子,C 是终点柱子.在移动过程中 AB 的角色会互换.按照惯例定义一个函数(关系)fn(n)=m

下面我写出移动的步骤:

第1次:圆盘1移动A->C 第2次:圆盘2移动A->B 第3次:圆盘1移动C->B //这里关键
第4次:圆盘3移动A->C 第5次:圆盘1移动B->A 第6次:圆盘2移动B->C 第7次:圆盘1移动A->C

可以自己试一下移动 4 个圆盘的过程,当然过程很长的....

在这些过程中有没有发现什么规律(老师脸)?

可以预见的是,这是有规律的,请看(自己脑补)上面第三次移动后的画面,此时圆盘 3 在 A 上,而圆盘 1,2 都在 B 上.

无论你有多少个圆盘,总会有类似上面第三次移动后类似的画面,也就是此时的开始柱子中的圆盘可以移动到 C 柱子上(移动后开始柱子为空,此时开始柱子转换角色为过渡柱子),而其它的圆盘都在过渡柱子上(此时角色转换为开始柱子).

总感觉说的太抽象了,我又不太会画图,想了想用 4 个圆盘来说一下:

// 我们只看关键步骤
第一个关键:A柱子上只有圆盘4,B柱子上有圆盘1,2,3,C柱子为空.(此时AB角色互换)
第二个关键:A柱子上有圆盘1,2,B柱子上只有圆盘3,C柱子只有圆盘4.

是否发现fn(4)的步骤包括了fn(3)的步骤,你可以这样想,我将圆盘 4 移动到柱子 C 后就可以把圆盘 4 给抹掉(因为圆盘 4 最大,所有的圆盘都可以放到他上面,相当于是空的),而后你会发现第一个关键把圆盘 4 放到柱子 C 后再去掉,那整个画面就是fn(3)的操作了.

好了,通俗的介绍完了,不容易,下面该说一下抽象点的.我们有n个圆盘,步骤如下:

1. 将除了圆盘`n`的其它`n-1`个圆盘移动到B柱子上. 2. 圆盘`n`移动到柱子C上. 3.
将除了圆盘`n-1`的其它`n-2`个圆盘移动到A柱子上. 4. 圆盘`n-1`移动到柱子C. 5. .....

后面也就是重复的 1~4 的步骤,好抽象的是吧,看多几次多自己写一下过程就好了,需要时间的,下面上代码:

let number = 0; //操作个数

/** 移动单个圆盘操作 */
function move(n, start, end) {
	number++;
	console.log(`${number}次,圆盘${n}移动${start}->${end}`);
}

/**
 * 将n个圆盘由start柱子上移动到end柱子所需要的次数
 * @param  {[type]} n      [圆盘数]
 * @param  {[type]} start  [开始柱子]
 * @param  {[type]} center [过渡柱子]
 * @param  {[type]} end    [终点柱子]
 * @return {[type]}        [null]
 */
function hanio(n, start, center, end) {
	if (n === 1) {
		move(n, start, end);
	} else {
		hanio(n - 1, start, end, center); // 将开始柱子上的n-1个圆盘移动到过渡柱子上(注意参数顺序)
		move(n, start, end); // 移动最后那个圆盘到目标C柱子上

		hanio(n - 1, center, start, end); // 递归调用处理剩下的n-1个圆盘,此时AB柱子角色互换
	}
}

hanio(4, 'A', 'B', 'C');

总结

动态规划涉及到的不止这些简单的两个问题,还有其他的最长字序列等等问题,这是一种思想,如果你理解了动态规划,那么对于你解决一下类似的问题是很有帮助的.

动态规划当然还是可以优化的,比如有些操作是重复计算,对于单个子问题的结果做一个备忘或者缓存,可以很有效的提升计算时间,比如上面那个阶梯问题,计算fn(4)fn(3)的时候都会各自计算一遍fn(3),fn(2),fn(1),这里做一个结果缓存是很常见的优化手段.

还有一种是自底向上的方法,比如阶梯求fn(4),那么我们只需要计算fn(1)fn(2),对于fn(3)完全只需要令fn(1)+fn(2)相加就得到了,同样的fn(4)结果也直接相加就有了,根本不需要递归了.

算法这个东西真是很容易忘掉的,因为平时用的不多,我前几个月写的排序算法现在看的也是似懂非懂,面试前真应该刷一遍算法的,说不定过几天我自己写的文章都忘掉了,看的快忘的也快...这里一个哭脸(╥╯^╰╥)

博主第一次写关于算法的文章,如有人看这篇文章,而且发现文章有错误的话可以到我的 github 上给我提个 issue 让我知道,谢绝打骂~~

个人随笔记录,内容不保证完全正确,若需要转载,请注明作者和出处.