算法详解之回溯法具体实现

  • 更新时间:2022-10-26 08:41:44
  • 编辑:黎若菱
为找教程的网友们整理了算法相关的编程文章,网友龚淑懿根据主题投稿了本篇教程内容,涉及到回溯法、回溯法相关内容,已被657网友关注,下面的电子资料对本篇知识点有更加详尽的解释。

参考资料

正文内容

回溯法

理论辅助:

回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。用回溯算法解决问题的一般步骤为:

1、定义一个解空间,它包含问题的解。

2、利用适于搜索的方法组织解空间。

3、利用深度优先法搜索解空间。

4、利用限界函数避免移动到不可能产生解的子空间。

问题的解空间通常是在搜索问题的解的过程中动态产生的,这是回溯算法的一个重要特性。

还是那个基调,不喜欢纯理论的东西,喜欢使用例子来讲诉理论,在算法系列总结:动态规划(解公司外包成本问题) 的那一节里面 我们举得是经典的0-1背包问题,在回溯算法里面也有一些很经典的问题,当然,动态规划的0-1背包问题其实也可以使用回溯算法来解。在诸如此类似的求最优解的问题中,大部分其实都可以用回溯法来解决,可以认为回溯算法一个”通用解题法“,这是由他试探性的行为决定的,就好比求一个最优解,我可能没有很好的概念知道怎么做会更快的求出这个最优解,但是我可以尝试所有的方法,先试探性的尝试每一个组合,看看到底通不通,如果不通,则折回去,由最近的一个节点继续向前尝试其他的组合,如此反复。这样所有解都出来了,在做一下比较,能求不出最优解吗?

例子先行,现在我们来看看经典的N后问题

问题描述:在n*n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规矩,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n*n格的棋盘上方置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。我们需要求的是可放置的总数。
 

基本思路:   用n元组x[1;n]表示n后问题的解。其中,x[i]表示皇后i放置在棋盘的第i行的第x[i]列。由于不容许将2个皇后放在同一列上,所以解向量中的x[i]互不相同。2个皇后不能放在同一斜线上是问题的隐约束。对于一般的n后问题,这一隐约束条件可以化成显约束的形式。如果将n*n 格的棋盘看做二维方阵,其行号从上到下,列号从左到右依次编号为1,2,...n。从棋盘左上角到右下角的主对角线及其平行线(即斜率为-1的各斜线)上,2个下标值的差(行号-列号)值相等。同理,斜率为+1的每条斜线上,2个下标值的和(行号+列号)值相等。因此,若2个皇后放置的位置分别是(i,j)和(k,l),且 i-j = k -l 或 i+j = k+l,则说明这2个皇后处于同一斜线上。以上2个方程分别等价于i-k = j-l 和 i-k =l-j。由此可知,只要|i-k|=|l-j|成立,就表明2个皇后位于同一条斜线上。

1、从空棋盘起,逐行放置棋子。
2、每在一个布局中放下一个棋子,即推演到一个新的布局。
3、如果当前行上没有可合法放置棋子的位置,则回溯到上一行,重新布放上一行的棋子。
代码:

 

复制代码 代码如下:
#include <stdio.h>  
#include <math.h>  
#include<stdlib.h>  
static int n,x[1000];  
static    long sum;  
int Place(int k)  
{  
for(int j=1;j <k; j++)  
    if((abs(k-j) == abs(x[j]-x[k]))||(x[j]==x[k])) return 0;  
     return 1;  
  } 

 

void Backtrak(int t)  {     if(t>n) sum++;     else         for(int i=1; i <= n; i++)         {              x[t] =i;              if(Place(t))Backtrak(t+1);         }  }

int main()  {      int nn;      while(scanf("%d",&nn)!=EOF)      {      n=nn;      sum=0;      for(int i=0;i<=n;i++)      x[i]=0;      Backtrak(1);      printf("%d\n",sum);  }  }

 

这段代码有必要解释一下,Place(int)即尝试看是否可以,如果不可以则回退到t+1层,再尝试其他的组合。

这里也道出了回溯算法的核心思想:但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择

算法实践:

问题描述:在一个n*n的网格里,每个网格可能为“墙壁”(用‘X'表示)和“街道”(用‘.'表示)。现在在街道放置碉堡,每个碉堡可以向上下左右四个方向开火,子弹射程无限远。墙壁可以阻挡子弹。问最多能放置多少个碉堡,使它们彼此不会互相摧毁。

如下面四张图,墙壁用黑正方形表示,街道用空白正方形表示,圆球就代表碉堡。1,2,3是正确的,4,5是错误的。以为4,5里面在某一行或者某一列有两个碉堡,这样他们就会互相攻击了。意思明白了吗?可能我的表达很不清晰,呵呵….

输入输出示例

Sample input:       ——————输入的n值  .X..  .... 

XX.. ....  XX  .X  .X.  X.X  .X.  ....  ....  ....  ....

Sample output:

初拿到这个问题,你会不会想到回溯算法呢?有人说遍历墙的位置,然后再墙的上下左右四个格子放置碉堡会得到最优解,这个我没有验证过,细细的用笔画了画,好像是这么回事,但是很多时候要知道最优解用什么方法是很难发现的,利用通用解题方法回溯法,我们可以在一片茫然的时候开始我们的编程

首先我们来分析一下这个问题:使用回溯法,我们尝试每一种可能放置的情况,然后进行判断是否满足要求,若不满足,尝试放到下一个单元格,如此反复,最终,我们将所有可能放置的情况全部遍历出来了,连所有情况都出来了,难不成还找不到最优解吗?哈哈。。说做就做…

 

复制代码 代码如下:
#include <stdio.h>
     char map[4][4];
     int best,n;
     int canput(int row, int col)
     {
        int i;
        for (i = row - 1; i >= 0; i--) 
        {
          if (map[i][col] == 'o') return 0; 
          if (map[i][col] == 'x') break;
        }
        for (i = col - 1; i >= 0; i--)
        {
          if (map[row][i] == 'o') return 0; 
          if (map[row][i] == 'x') break;
        }
        return 1;
     }

     void solve(int k,int tot)
     {
        int x,y;
        if(k==n*n)
        {
          if(tot>best) 
          {
           best=tot;   return;
          }
        }
        else
        {
          x=k/n;
          y=k%n;
          if((map[x][y]=='.') && (canput(x,y) ) )
          {
            map[x][y]='o';
            solve(k+1,tot+1);
            map[x][y]='.';
          }
         solve(k+1,tot);
         }
      }

     int main()
     {
        int i,j;
        scanf("%d",&n);
        while(n>0)
        {
          for(i=0;i< n;i++)
             for(j=0;j< n;j++)
                 scanf("%1s",&map[i][j]); 
          best=0;
          solve(0,0);
          printf("%d\n",best);
          n=0;                             
          scanf("%d",&n);
        }
        return 0;
 }

 

对上面的代码做一下点解释,canput是做检验的,检验放在某个地点到底行不行得通,solve才是真正进行递归回溯的函数。。

算法相关教程

  • 实现Python3数组旋转的3种算法实例

    在本篇文章里小编给大家整理的是一篇关于实现Python3数组旋转的3种算法实例内容,需要的朋友们可以学习参考下。

    发布时间:2021-04-16

  • java微信小程序开发中加密解密算法总结

    这篇文章主要为大家详细介绍了java实现微信小程序加密数据解密算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

    发布时间:2019-06-05

  • PHP面试关于算法问题整理

    下面小编就为大家带来一篇PHP面试常用算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧

    发布时间:2019-12-14

  • Java数字签名算法DSA详解

    这篇文章主要介绍了Java数字签名算法DSA,结合实例形式分析了Java数字签名算法DSA具体定义与使用技巧,需要的朋友可以参考下

    发布时间:2021-05-15

  • python机器学习之KNN分类算法

    python机器学习之KNN分类算法

    给大家整理了关于python的教程,这篇文章主要为大家详细介绍了python机器学习之KNN分类算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

    发布时间:2022-08-01

  • Python实现的选择排序算法的实例及代码

    这篇文章主要介绍了Python实现的选择排序算法,结合实例形式分析了Python选择排序的概念、原理及简单实现技巧,需要的朋友可以参考下

    发布时间:2019-12-30

  • python em算法的实现

    这篇文章主要介绍了python em算法的实现,帮助大家更好的理解机器学习,感兴趣的朋友可以了解下

    发布时间:2021-05-18

  • JS中的算法与数据结构之字典(Dictionary)示例效果

    这篇文章主要介绍了JS中的算法与数据结构之字典(Dictionary),结合实例形式详细分析了javascript数据结构中字典的概念、原理、定义与常见使用方法,需要的朋友可以参考下

    发布时间:2020-01-26

  • Java常用排序算法整理分享

    在本文里我们给大家整理了关于Java常用排序算法以及实例代码分析,需要的朋友们跟着学习下。

    发布时间:2019-09-10

用户留言