2006年8月28日

通过优化数据结构改进n皇后问题

     摘要: n皇后问题的时间代价除了递归和回溯需要的外，在每一步判断加入的皇后是否与当前棋盘格局冲突也需要不少时间，guarded函数需要扫描所在列以及两条对角线。然而我们可以通过改进数据结构来使后者的时间代价降低为O(1)。

对于n皇后问题来说，每一行每一列每条对角线上最多有一个皇后，那么对于这样的每个元素（行、列或对角线）我们可以用一个bool值来表示是否已经有皇后在该元素上，这样判断是否冲突就变得十分简单，只需要读取一个bool值。另外需要记录棋盘的格局，考虑到一行只有一个皇后，可以建议一个一维数组保存每一行的皇后占用的列号。

这样基本就OK了，只是对于行而言，我们采用了回溯法（剪枝函数）保证了每行只有一个皇后，这样行的bool数组就可以省略了。

  阅读全文

posted @ 2006-08-28 18:45 樱木 阅读(287) | 评论 (0) | 编辑 收藏

n皇后问题实现

     摘要: n皇后问题是递归和回溯法的一个典型应用。问题描述如下：对于一个n×n的棋盘，要求在其中放入互不攻击的n个皇后。皇后的攻击范围包括：
1) 同一行
2) 同一列
3) 同一对角线（包括两个方向）

分析后可见，皇后之间互不攻击当且仅当满足下列条件：
1) 每一行只能有一个皇后
2) 每一列只能有一个皇后
3) 任意条对角线上面只能有一个皇后

若按照从左到右从上到下的顺序手动摆放皇后，会发现算法遵循的是回溯法的思想。于是我们遵循top-down design的顺序来设计整个算法和程序。

  阅读全文

posted @ 2006-08-28 18:44 樱木 阅读(425) | 评论 (0) | 编辑 收藏

递归函数引用参数对递归工作栈大小的影响分析

     摘要: 本文从递归函数参数的角度来分析，递归函数调用时递归工作栈中工作记录减肥的可能性。

用最简单的求阶层函数来举例：
n! = n*(n-1)*(n-2)***2*1

常见的递归实现如下：
int fun(int n)
{
if( n<=1 ) return 1;
return n*fun(n-1);
}
不用多说，这个实现下每次递归调用都会在当前层的工作记录中分配一个4字节（IBM兼容机）的空间来存放n的值。若栈的深度为DEPTH，那么一共需要DEPTH×4个字节存放参数。

  阅读全文

posted @ 2006-08-28 18:41 樱木 阅读(1298) | 评论 (1) | 编辑 收藏