算法笔记回溯法n后问题和01背包问题.docx

《算法笔记回溯法n后问题和01背包问题.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1、n后问题   问题描述：在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。   问题解析：用n元数组x[1:n]表示n后问题的解。其中，x[i]表示皇后i放在棋盘的第i行的第x[i]列。由于不允许将2个皇后放在同一列上，所以解向量中的x[i]互不相同。如果将n*n的棋盘看做是二维方阵，其行号从上到下，列号从左到右依次编号为1,2，……n。设两个皇后的坐标分别为(i,j)和(k,l)。

2、若两个皇后在同一斜线上，那么这两个皇后的坐标连成的线为1或者-1。因此有：   由此约束条件剪去不满足行、列和斜线约束的子树。程序的递归回溯实现如下：[cpp] viewplain copy1.//n后问题 回溯法计算 递归  2.#include "stdafx.h"  3.#include   4.#include "math.h"  5.using namespace std;   6.  7.class Queen  8.{  9.   friend int nQueen(int);  10.   private:  

3、11.      bool Place(int k);  12.      void Backtrack(int t);  13.      int  n,    // 皇后个数  14.          *x;    // 当前解  15.      long sum;  // 当前已找到的可行方案数    16.};   17.  18.int main()  19.{  20.    int n=4,m;  21.    cout<

4、t<

5、

6、(x[j]==x[k]))   5.        {  6.            return false;  7.        }  8.    }  9. 

7、   return true;  10.}   11.  12.void Queen::Backtrack(int t)//t扩展的是行  13.{  14.    if (t>n)  15.    {  16.        sum++;  17.        for (int i=1;i<=n;i++)  18.        {  19.            cout<

8、5.        //探索第t行的每一列是否有元素满足要求  26.        for (int i=1;i<=n;i++)  27.        {  28.            x[t]=i;  29.            if (Place(t))  30.            {  31.                Backtrack(t+1);  32.            }  33.        }  34.    }  35. }  36.  37.int nQueen(int n)  38.{  39.  

9、  Queen X;  40.    X.n=n;  41.    X.sum=0;  42.  43.    int *p=new int[n+1];  44.  1.    for(int i=0;i<=n;i++)  2.    {  3.        p[i]=0;  4.    }  5.  6.    X.x=p;  7.    X.Backtrack(1);  8.  9.    delete []p;  10.    return X.sum;  11.}     数组x记录了解空间树中从根到当前扩展节点的路径，这些信息包含了回

10、溯法在回溯是所需要的信息。利用数组x所含的信息，可将上述回溯法表示成非递归的形式。进一步省去O(n)递归栈空间。迭代实现的n后问题具体代