数据结构重读 – 回溯法与树的遍历 (幂集问题 八皇后问题)

有许多问题,可以利用试探和回溯的搜索技术求解。

求解的过程实际是先序遍历一棵“状态树”的过程

例1:有集合A = {1, 2, …n},求A的全部子集。

思路:从求全部子集(幂集)这个事情上,实际上对每个元素只有两个状态:要么在一个子集中,要么不在。

因此,可以逐一对A中每个元素进行“取”和“舍”,从而构造一棵完全二叉树。

算法如下:

注意这里是1~n,不是0~n

 

然而,很多问题用回溯法求解时,描述求解过程的状态树并不是一棵满二叉树。当位于和解矛盾的状态时,不能继续试探下去,而要剪去哪些不满足条件的分支。

下面来看一下八皇后问题:

八皇后问题即有八个皇后,要放到8×8的棋盘上,要求任何时刻,棋盘的同一行、同一列、同一对角线都只有一个皇后。

最基础解法就是回溯。

首先说下合法条件:

(1)行、列不说了。
(2)假设两个皇后位于(i, j)和(m, n),则斜对角线的条件是abs(m-i) = abs(n-j)。

此外,我们可以不用n*n的数组记录皇后位置,而是用n数组表示,其中a[0]表示第0行皇后位于第几列。

其他就很简单了!

 

Leave a Reply

Your email address will not be published.