回溯法——以皇后摆放问题为例

回溯法(98条消息) （新手向）递归与回溯算法学习（一）——n位逐位整除数_TripleGold.的博客-CSDN博客

算法思想：

（通用的解题法）穷举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现不满足求解条件时就回退，尝试其他路径

创新互联公司专注为客户提供全方位的互联网综合服务，包含不限于网站设计制作、做网站、金塔网络推广、小程序设计、金塔网络营销、金塔企业策划、金塔品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；创新互联公司为所有大学生创业者提供金塔建站搭建服务，24小时服务热线：028-86922220，官方网址：www.cdcxhl.com

回溯法的解题步骤：

针对给定问题确定问题的解空间树，至少包含问题的一个解或者最优解
确定结点的扩展搜索规则
以深度优先搜索解空间树，并采取剪枝手段。

框架：

非递归回溯框架

int x[n]    //x存放解向量，全局变量
void backtrack(int n){
    int i = 1;      //根节点的层次为1
    while(i>=1){    //尚未回溯到头        
    if(ExistSubNode(t)){    //当前结点存在子节点
        for(j=下界;j<=上界;j++){    //对于子集树，j从0到1循环
            x[i]取一个可能的值;
            if(constraint(i)&&bound(i)){    //x[i]满足约束条件和界限函数
                if(x是一个可行的解)
                    输出x;
                else i++;   //进入下一个层次
            }
        }
    }
    else i--;   //不存在子节点，返回上一层
    }
}

递归回溯框架

int x[n]
void backtrack(int i){
    if(i>n)     //搜索叶子结点，输出一个可行解
        输出结果;
    else{
        for(j=下界;j<=上界;j++){    //用j枚举i所有可能的路径
            x[i] = j;   //产生一个可能的解分量
            ...
            if(constraint(i)&&bound(i))
                backtrack(i+1)  //满足约束条件继续下一层
        }
  }
}

result = []
def backtrack(路径, 选择列表):
   if 满足结束条件:
     result.add(路径)
     return
    
   for 选择 in 选择列表:
     做选择
     backtrack(路径, 选择列表)
     撤销选择

例题：皇后摆放问题：

题目描述

国际象棋的棋盘可以看做是一个 8 × 8 的矩阵，上面每一个格子仅能放一枚棋子，现在给出一个 8 × 8 的由 0 和 1 组成的矩阵，代表象棋棋盘，1 代表当前位置放置了一个皇后，0 则代表什么都没有放，上面有 n（n 为小于 8 的正整数）个位置已经放上了皇后棋子（相互之间不冲突，合理摆放），现在另外给你 8 - n 个皇后，问你有多少合理的摆法。

输入描述

一个 8 × 8 的由 0 和 1 组成的矩阵。

输出描述

一个整数，为摆放的种类数。

样例输入

1 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

样例输出

问题分析

判断某位置是否可以摆放皇后

假设i行j列处已摆放上一个皇后，则下面摆放的皇后(x,y)则不能在i行和j列(即x!=i && y!=j)，且不能在已摆放皇后对角线上(即abs(x-i)!=abs(y-j))。

搜索算法

通过初始化，我们可以知道哪些位置有了皇后。通过一个路径数组path[9]来记录（1~8）行哪一列有皇后。还未探索到的行，数组赋值0。

用回溯法，从第一行开始往下，测试1~8列是否能够摆放，能则继续往下探索，不能则返回上一层。

AC代码：

#include
#include
#include
using namespace std; 

int path[9];
//判断某位置是否可以摆放皇后
bool pd(int x){
  for(int i=1;i<=8;i++){
    if(path[i]!=0 &&i!=x && (path[i]==path[x] || abs(i-x)==abs(path[i]-path[x]))){
      return false;
     }
   }
  return true;
}
//搜索算法
void backtrace(int x,int &sum){
  if(x==9){
    sum++;
    return;
   }
  if(!path[x]){
    for(int i=1;i<=8;i++){

      path[x] = i;
      if(pd(x)) backtrace(x+1,sum);
      path[x] = 0;
     }
   }
  else backtrace(x+1,sum);
}

int main(){
  int x,sum = 0;
  memset(path,0,sizeof(path));
  for(int i=1;i<9;i++){
    for(int j=1;j<9;j++){
      cin>>x;
      if(x==1){
        path[i]=j; 
       }
     }
   }
  backtrace(1,sum);
  cout<<sum<<endl;
  return 0;
}

分享题目：回溯法——以皇后摆放问题为例
URL网址：http://6mz.cn/article/dsoipsp.html

网站建设知识