当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

回溯法入门学习之一

发表于: 2012-11-10   作者:128kj   来源:转载   浏览:
摘要: 一: 回溯法    有时我们要得到问题的解,先从其中某一种情况进行试探,在试探过程中,一旦发现原来的选择是错误的,那么就退回一步重新选择, 然后继续向前试探,反复这样的过程直到求出问题的解。比喻:“下棋”:  每一次走棋的位置都要考虑到是否是损人利己,如果是害人害己的走法就要回撤,找下一步损人利己的走法。又如玩RPG游戏中碰到“迷宫”大家是怎样出来的? &nb
一: 回溯法
   有时我们要得到问题的解,先从其中某一种情况进行试探,在试探过程中,一旦发现原来的选择是错误的,那么就退回一步重新选择, 然后继续向前试探,反复这样的过程直到求出问题的解。比喻:“下棋”:  每一次走棋的位置都要考虑到是否是损人利己,如果是害人害己的走法就要回撤,找下一步损人利己的走法。又如玩RPG游戏中碰到“迷宫”大家是怎样出来的?

  回溯跟深度优先遍历是分不开的,我们倾向于把回溯看做深度优先遍历的延伸。我们知道,图的深度优先遍历每个节点只会被访问一次,因为我们一旦走过一个点,我们就会做相应的标记,避免重复经过同一个点。而回溯的做法是,当走过某一个点时,标记走过,并把该点压栈;当该节点出栈时,我们再把它标记为没有走过,这样就能保证另外一条路也能经过该点了。

二:"深度优先搜索+回溯"递归框架:

函数DFS(节点){

  如果(节点=目标节点) {找到目标,跳出}
  遍历所有下一层节点for(int i=0;i<k;i++){
   标记下一层节点i已访问;
   DFS(下一层的节点i)
   恢复i为未访问
  }

}


三:举例

题目描述:
    在一个4*5的棋盘上,马的起始位置坐标有键盘输入,求马能返回起始位置的不同走法总数并输出每一种走法(马走过的位置不能重复,马走“日”字。
输入输出样例

Sample input
1 1

Simple output
4596

分析:经典回溯。搜索过程是从起点(x,y)出发,按照深度优先的原则,从8个方向中尝试一个个可以走的点,直到返回起点,不能的话,回溯上一点,继续.

import java.util.*;
 public class Main {
  static int array[][] = {{-1, -1, -2, -2, 2, 2, 1, 1},{-2, 2, 1, -1, 1, -1, 2, -2}};//表示马跳的8个方向
  private int chess[][];//chess[x][y]=k表示马的第k步的坐标为(x,y)

  private int total = 0;//统计走法的种数
  private int sx, sy;//(sx,sy)表示马的起始坐标

  public Main(int sx,int sy){
     this.sx=sx;
     this.sy=sy;
     chess=new int[4][5];
     chess[sx][sy] = 1;
  } 

  public int getTotal(){
    return this.total;
  }
   
 public void find_way(int p1, int p2,int step){//DFS+回溯

   int i, pi, pj;
   for(i = 0; i < 8; i++){//向8个方向试探
    pi = p1 + array[0][i];
    pj = p2 + array[1][i];
    if((sx == pi)&&(sy == pj)){
        total++;//找到一种走法,(sx,sy)表示起点
         output();//输出走法
    }
      
    else if( (pi >= 0)&&(pi < 4)&&(pj >= 0)&&(pj < 5)&&(chess[pi][pj] == 0)){//继续试探
            chess[pi][pj] = step;//马的第step步的坐标是(pi,pj)
           find_way(pi, pj,step+1);//从(pi,pj)出发继续找
           chess[pi][pj] = 0;// 回溯,恢复未走标志   
         }
  }//for
}

 public void output() {   
        
        System.out.println("total=" + total);   
        for (int y = 0; y < 4; y++) {   
            System.out.println("");   
            for (int x = 0; x < 5; x++) {   
                System.out.printf("%4d",chess[y][x]);   
            }   
        }   
        System.out.println("");   
    }   


public static void main(String args[]){
    
    Scanner sc=new Scanner(System.in);
   
    System.out.printf("输入马的起始坐标:\n");
    int sx=sc.nextInt();
    int sy=sc.nextInt();

    System.out.printf("sx = %d, sy = %d\n", sx, sy);
     if ((sx < 0)||(sx >= 4)||(sy < 0)||(sy >= 5))
	   System.out.printf("ERROR\n");
     else{  
         Main m=new Main(sx,sy);
	 
	   m.find_way(sx, sy,2);//从起始位置开始试探
	 //  System.out.printf("total = %d\n", m.getTotal());
     }
   }
}


程序运行:
D:\tutu>java Main
输入马的起始坐标:
1 1
sx = 1, sy = 1
total=1

   5   8  11   2   0
  10   1   4   7   0
   0   6   9  12   3
   0   0   0   0   0
total=2

   5   8   0   2   0
  10   1   4   7   0
   0   6   9  12   3
   0  11   0   0   0
total=3

   5   8  11   2   0
   0   1   4   7  10
   0   6   9  12   3
   0   0   0   0   0
total=4

   5   8  11   2   0
  12   1   4   7  10
   0   6   9  14   3
   0  13   0   0   0
total=5

   5   8   0   2   0
   0   1   4   7   0
   0   6   9   0   3
  10   0   0   0   0
total=6

   5   8   0   2   0
   0   1   4   7   0
   9   6   0   0   3
   0   0  10   0   0
total=7
...........

total=4595

   0   0   0   0   0
   4   1  10   7   0
  11   8   5   2   0
   0   3  12   9   6
total=4596

   0   0   0   0   0
   4   1   0   0   0
   0   0   5   2   0
   6   3   0   0   0

源码:

回溯法入门学习之一

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
回溯法(英语:backtracking)是暴力搜寻法中的一种。 回溯法采用试错的思想,它尝试分步的去解决一
回溯法的基本做法是搜索解空间,一种组织得井井有条的,能避免不必要搜索的穷举式搜索法。上文“回
一. 回溯法 – 深度优先搜素 1. 简单概述 回溯法思路的简单描述是:把问题的解空间转化成了图或者树
回溯算法 今天我们来学习一下回溯算法,什么是回溯?根据搜索结果所做选择:如果发现已经得到最优解
回溯算法 今天我们来学习一下回溯算法,什么是回溯?根据搜索结果所做选择:如果发现已经得到最优解
~_~今天刚刚接触Ruby这门语言。Ruby一种为简单快捷的面向对象编程(面向对象程序设计)而创的脚本语
1.回溯法算法思想: 定义: 回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目
问题: 给定n个正整数wi和一个正整数m,在这n个正整数中找出一个子集,使得子集中的正整数之和等于m
1.回溯法算法思想: 定义: 回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目
1.回溯法算法思想: 定义: 回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号