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

算法思想：

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

回溯法的解题步骤：

1. 针对给定问题确定问题的解空间树，至少包含问题的一个解或者最优解

2. 确定结点的扩展搜索规则

3. 以深度优先搜索解空间树，并采取剪枝手段。

框架：

1. 非递归回溯框架

    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--;   //不存在子节点，返回上一层
        }
    }

2. 递归回溯框架

    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 

样例输出

 4

问题分析

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

假设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<iostream>
 #include<cstring>
 #include<cmath>
 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;
 }

• 还没有人评论，欢迎说说您的想法！

相关课程

C语言编程基础

7281 0元 45元 限免

Web前端页面制作快速入门

5485 9.8元

Cacti网络监控，邮件报警和压力测试

4190 9.8元