`
ttwang
  • 浏览: 334607 次
  • 性别: Icon_minigender_2
社区版块
存档分类
最新评论

回溯法---八皇后问题

 
阅读更多

一、回溯法:
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时,总是先判断该结点是否肯定不包含问题的解。如果肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层向其祖先结点回溯。否则,进入该子树,继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时,只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法,它适用于解一些组合数较大的问题。

二、算法框架:
1、问题的解空间:应用回溯法解问题时,首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个(最优)解。

2、回溯法的基本思想:确定了解空间的组织结构后,回溯法就从开始结点(根结点)出发,以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点,同时也成为当前的扩展结点。在当前的扩展结点处,搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点,并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。换句话说,这个结点不再是一个活结点。此时,应往回移动(回溯)至最近的一个活结点处,并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索,直至找到所要求的解或解空间中已没有活结点时为止。
运用回溯法解题通常包含以下三个步骤:
(1)针对所给问题,定义问题的解空间;
(2)确定易于搜索的解空间结构;
(3)以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索;

3、递归回溯:以八皇后问题来说明:

下面是八皇后问题的程序

八皇后问题是:在八行八列的格子上放8个皇后(棋子),使的他们都不在同一行同一列和同一斜线上.

//回朔法实现八皇后问题

package sf.backDate;


import java.io.*;

public class BackDateQueen{
 private int s[]=null;//存放皇后所在的位置s[i]表示所在行,i表示所在列。
 
 private int count=0;//几个皇后问题,在这里是8
 private int suc;
 public BackDateQueen(int count){
  suc=0;
  this.count=count;
  s=new int[count];
  for(int i=0;i<count;i++){
   s[i]=-1;
   }
  }
  
  public void queen(int n){//核心函数,实现把所有的满足题义的情况列出来
   
   if(n==8){//因为是回朔法,所以用到递归,这里是递归 的出口
    suc++;
    printThis();//打印
    return;
    }
     
    for(int i=0;i<count;i++){//循环对一列中的所有行进行考虑
     s[n]=i;//第n列放在第i行,n表是列.
     if(isCan(n)){//如果这种情况成立,则递归下去。
      queen(n+1);//递归,对第n+1列进行考虑(一般最外面是从0列开始).
      }
     }
   
   }/*注意他在每个递归函数中都有循环,这样就使得,他还会考虑在该活接点的接下来的
   情况,考虑完后,他还会随着递归函数的返回而进行回朔,直到根接点为止,这样就能把所
   的情况都找到*/
   
   
   public boolean isCan(int n){
    for(int i=0;i<n;i++){
     if(s[i]==s[n]) return false;//不在同一行
     if(Math.abs(s[n]-s[i])==n-i) return false;//不在同一斜线上
     }
     
     return true;
    }
    
    public void printThis(){//打印函数
     System.out.println("第"+suc+"种放法"+"皇后分别放在以下列的以下行:");
     for(int i=0;i<count;i++){
      System.out.println("第"+i+"列的第"+s[i]+"行");
      }
     }
     
     public static void main(String[] args){
      BackDateQueen bdq=new BackDateQueen(8);
      bdq.queen(0);
      }
 }
 
 /*在这个问题上一定要知道是用一维数组来存储皇后的存储信息的,列随着数组的标量i(上述类中是n)
  *已经决定了,数组中的值表示皇后所在行(当然你可以倒过来)*/
 
  /*基本思路:先从第0列开始考虑,在第0列的所有行循环试看能否放皇后,如果能则递归下去(找第2列的),又回到同样 的
   *问题(正好是递归的特性),就这样一直递归下去,出口是直到放了八个皇后,递归函数最低层的返回
   *,随着函数返回,向上回朔一层,继续遍历,直到这层遍历完,再向上回朔,一直回朔到起始的
   *最外层递归函数,这样就把所有满足条件的内容打印出来了*/

 

4.综合上面得出结论:

回蒴法是用递归所以问题得满足递归的要求,然后区别在于,一般的递归在调用完了自身之后不会有动作了,

而回溯不同,他在调用完了自身还是有动作的,一般是个循环,在循环中有可能不停的调用自身.

分享到:
评论

相关推荐

    八皇后问题c++回溯法

    经典的算法,八皇后问题,c++实现,回溯法

    回溯法-N皇后问题_N皇后回溯法C++_

    在计算机科学中,尤其在解决约束满足问题(如拼图、八数码难题等)时,回溯法是一种非常有效的工具。 N皇后问题是一个经典的回溯法应用实例。这个问题要求在n×n的棋盘上放置n个皇后,使得任意两个皇后都不能在同一...

    回溯算法--解决 八皇后 四色图 背包

    回溯算法--解决 八皇后 四色图 背包 自己改写的程序 回溯算法--解决 八皇后 四色图 背包 自己改写的程序

    图着色问题 回溯法-C语言

    它常用于解决约束满足问题,如八皇后问题、数独、旅行商问题等,当然也包括图着色问题。 在回溯法解决图着色问题时,通常会采用以下步骤: 1. **定义颜色集**:首先确定可用的颜色数量,比如常见的4色问题,颜色集...

    C#回溯法8皇后问题-实验报告+程序

    使用C#编写回溯法解决8皇后问题的实验报告和程序 有图形界面,可以查看任意一种解法

    利用回溯法解决n皇后问题

    **回溯法是一种重要的算法策略,常用于解决组合优化问题,如八皇后问题、迷宫寻路等。在这个场景中,我们关注的是“n皇后问题”。n皇后问题是在一个n×n的棋盘上放置n个皇后,要求任何两个皇后不能处于同一行、同一...

    八皇后问题的回溯法实现

    八皇后问题的回溯法实现,一维数组,可拓展到N皇后

    实验八 回溯法-数据结构与算法:回溯法在经典组合优化问题的应用与实现

    内容概要:本文详细介绍了回溯法的基本原理及其在解决八皇后问题和0-1背包问题中的具体应用。文中阐述了状态空间的表示方法、约束条件的判断机制以及回溯操作的具体步骤,附带了详细的Python代码示例。实验结果显示...

    使用回溯法求解八皇后问题

    回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法回溯法

    回溯法解八皇后问题 vc++实现

    回溯法解八皇后问题.有源代码,能运行成功,标准的vc++实现

    回溯法解决八皇后问题的程序源码(c++)

    小弟申请ID不久,资源分用的很快,自己写点程序借此赚分以备使用。初出茅庐,学识尚浅。请各路朋友多多指点,不胜感激。

    回溯法解决八皇后问题

    ### 回溯法解决八皇后问题 #### 一、回溯法概述 ##### (一)回溯法的基本概念 回溯法是一种通过不断尝试解决问题的方法,尤其适用于解决那些解空间非常大、可以通过穷举法来寻找解的问题。这种方法的核心在于...

    八皇后回溯法

    八皇后回溯法,八皇后回溯法课件,八皇后回溯法PPT

    八皇后问题详细的解法-23页 PPT PDF版.pdf

    **回溯法**是一种更高效的搜索算法,特别适用于解决约束满足问题,如八皇后问题。这种方法的基本思想是在问题的解空间树中按深度优先策略搜索,同时在遇到不可行的分支时及时回退,从而避免了无效搜索。 1. **算法...

    素数环 回溯法-c语言

    回溯法通常用于解决组合优化问题,如图着色问题、八皇后问题等。它的基本步骤包括: 1. **定义解空间**:确定所有可能的解的集合。 2. **选择策略**:在解空间中选择一个可能的解进行试探。 3. **扩展**:将当前解...

    八皇后(回溯法)

    回溯算法是深度优先搜索的一种变形。在回溯搜索中,从问题的某一种状态(初始状态)出发,搜索从这种状态出发所能达到的所有“状态”,当一条路走到...这种不断“前进”、不断“回溯”寻找解的方法,就称作“回溯法”。

    回溯法解八皇后问题.图形实现

    ### 回溯法解八皇后问题:图形实现详解 #### 回溯法概念与应用 回溯法是一种解决约束满足问题的算法,尤其在解决排列组合类问题时表现出色。其核心思想是尝试构建问题的解空间树,并通过深度优先搜索(DFS)策略...

    用回溯法解决八皇后问题C语言实现

    有多种方法解决八皇后问题,在这里我用的是回溯法解决八皇后问题。大家一起来学习呀!!

    利用回溯法解决8皇后问题

    利用回溯法解决8皇后问题,简单并且和很好理解!

Global site tag (gtag.js) - Google Analytics