当前位置:  编程技术>c/c++/嵌入式

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

    来源: 互联网  发布时间:2014-10-23

    本文导语:  理论辅助: 回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。用回溯算法解决问题的一般步骤为: 1、定义一个解空间,它包...

理论辅助:

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

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  
#include  
#include 
static int n,x[1000]; 
static    long sum; 
int Place(int k) 

for(int j=1;j n) sum++; 
   else 
       for(int i=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("%dn",best);
          n=0;                            
          scanf("%d",&n);
        }
        return 0;
 }

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


    
 
 

您可能感兴趣的文章:

  • 一种求正整数幂的高效算法详解
  • 深入串的模式匹配算法(普通算法和KMP算法)的详解
  • 解析C#彩色图像灰度化算法的实现代码详解
  • 使用Deflate算法对文件进行压缩与解压缩的方法详解
  • 深入第K大数问题以及算法概要的详解
  • 字符串的模式匹配详解--BF算法与KMP算法
  • 算法之排列算法与组合算法详解
  • 采用C++实现区间图着色问题(贪心算法)实例详解
  • 算法详解之分治法具体实现
  • C语言位图算法详解
  • 基于一致性hash算法(consistent hashing)的使用详解
  • 算法详解之分支限界法的具体实现
  • C语言实现排序算法之归并排序详解
  • 基于稀疏图上的Johnson算法的详解
  • 基于一致性hash算法 C++语言的实现详解
  • unix/linux知识 iis7站长之家
  • 使用C++实现全排列算法的方法详解
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • <<大话数据结构>>中冒泡排序算法改进
  • 那位高人有任务分配问题的禁忌搜索算法、模拟退火算法的算法实现程序啊
  • 二叉树常用算法(求总节点个数和叶子节点个数)
  • 求对称加密DES算法与非对称加密RSA算法!(可用)
  • boost unordered_map和std::list相结合的实现LRU算法
  • java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述
  • 中文网页快速去重算法研究
  • 谁能给出一个最快最高效的求素数的算法?(高分求算法)
  • 使用java jdk中的LinkedHashMap实现简单的LRU算法
  • 谁有这样的算法:给定两个区域,用直线或折线来连接,以及移动其中线段的算法。
  • 广告系统中weak-and算法原理及编码验证
  • 算法之排序算法的算法思想和使用场景总结
  • c++实现MD5算法代码示例
  • 【算法】扑克发牌算法实现
  • c语言实现MD5算法完整代码示例
  • php加密算法之实现可逆加密算法和解密分享
  • MD5算法的C语言实现
  • C++实现查找中位数的O(N)算法和Kmin算法
  • PHP中对各种加密算法、Hash算法的速度测试对比代码
  • 关于加密算法的效率问题
  • 哈希算法计算 Generic Hash and HMAC Program


  • 站内导航:


    特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3