`
128kj
  • 浏览: 601371 次
  • 来自: ...
社区版块
存档分类
最新评论

回溯法入门学习之一

阅读更多
一: 回溯法
   有时我们要得到问题的解,先从其中某一种情况进行试探,在试探过程中,一旦发现原来的选择是错误的,那么就退回一步重新选择, 然后继续向前试探,反复这样的过程直到求出问题的解。比喻:“下棋”:  每一次走棋的位置都要考虑到是否是损人利己,如果是害人害己的走法就要回撤,找下一步损人利己的走法。又如玩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
分享到:
评论

相关推荐

    N后问题的回溯法实现C#

    N后问题,也被称为汉诺塔问题,是一个经典的递归问题,源于印度的传说,它涉及到将N个大小不一的圆盘从一根柱子移动...通过这个项目,不仅可以学习到基础的编程技巧,还能深入理解递归和回溯法在解决复杂问题中的应用。

    中科大 算法导论 课件(全套11)回溯法

    - **教学意义**: 在中国科学技术大学的算法导论课程中,回溯法作为计算机科学与技术专业学生必须掌握的重要内容之一,有助于培养学生的算法设计与分析能力。 **2. 搜索算法简介** - **穷举搜索**: 对所有可能的...

    c#精典五大算法 分治,动态规划,回溯法

    在IT行业中,算法是解决问题的核心工具之一,尤其是在编程领域。C#作为一款强大的面向对象的编程语言,同样可以用来实现各种高效算法。本压缩包文件包含的五个经典算法分别是分治策略、动态规划和回溯法,这些都是...

    python回溯法实现数组全排列输出实例分析

    对于希望掌握回溯算法的开发者来说,理解和实现全排列是学习过程中的一个基础且重要的环节。这个过程不仅有助于加深对回溯法工作原理的理解,也能加深对递归思想的掌握。 希望这篇文章能够帮助大家在使用Python进行...

    学习电脑信息五大常用算法之五:分支限界法.docx

    回溯法的目标是找出满足约束条件的所有解,而分支限界法的目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解。 分支限界法的搜索策略是:在扩展结点处,先生成其...

    算法第5章PPT学习教案.pptx

    《算法第5章》的学习教案主要探讨了回溯法这一重要的算法设计策略。回溯法是一种用于解决组合优化问题的有效方法,特别是在面对需要找到解集或寻找满足特定约束条件的最佳解的问题时。它通过深度优先搜索策略来避免...

    穷举算法 回溯算法 介绍

    穷举算法是最简单、最基础的算法之一,也是通常被认为非常没效率的算法。但是,穷举拥有很多优点,它在算法中占有一席之地。首先,穷举具有准确性,只要时间足够,正确的穷举得出的结论是绝对正确的;其次,穷举拥有...

    C++背包问题穷举回溯备忘录动态规划.zip

    在提供的压缩包文件中,有名为"0-1.cpp"和"0-1.py"的源代码文件,它们很可能是用C++和Python实现的上述算法之一。"input.txt"文件可能包含输入数据,如物品的价值和重量,以及背包的容量。".gitattributes"文件则是...

    C语言入门-leetcode练习之第52题N皇后II.zip

    N皇后问题是一个经典的回溯法问题,它的目标是在一个n×n的棋盘上放置n个皇后,使得任意两个皇后都不能在同一行、同一列或同一对角线上。LeetCode的第52题,N皇后II,不仅要求我们找出一种可行的放置方案,还要计算...

    基础算法入门

    《基础算法入门》这个压缩包文件是为初学者设计的一份宝贵的资源,旨在帮助学习者掌握算法的基础知识。标签中的“java”表明这份资料可能涵盖了使用Java语言实现算法的内容,而“算法”则是核心主题,涵盖了算法的...

    javascript-leetcode面试题解递归与回溯问题之第1291题顺次数-题解.zip

    回溯法是一种试探性的解决问题的方法,它尝试逐步构建解决方案,如果在某一步发现无法达到目标,就会撤销上一步甚至更多步的操作,返回到一个分支点,再尝试其他的可能性。回溯法常用于解决约束满足问题,如八皇后...

    算法设计与分析 分枝限界法PPT学习教案.pptx

    它与回溯法有相似之处,但两者的目标和搜索策略有所区别。回溯法致力于找到所有满足条件的解,而分支限界法则旨在找到一个解或最优解,它通常采用广度优先或最小耗费优先的搜索策略。 1. **分支限界法的基本思想** ...

    软件设计师学习计划(谁都适用,很实用)

    算法设计是软件设计师考试的基础知识之一,需要掌握四种算法(动态规划法、分治法、贪心算法、回溯法)的策略。上午部分占比4分左右,下午题型为第4题共15分。 第七周:软件系统分析与设计 在第七周,需要学习...

    排列组合有重复

    换言之,排列组合是指从一个集合中选择一些元素,并且考虑这些元素的顺序。 二、回溯算法的应用 回溯算法是一种常用的算法,用于解决排列组合问题。该算法的基本思想是,通过递归地选择元素,并且在每一步骤中,...

    java与cpp基础学习

    Java的特点之一是"一次编写,到处运行",这意味着编写的Java代码可以在任何支持Java虚拟机(JVM)的平台上运行。Java的基础知识包括基本语法、数据类型、控制结构(如if语句和循环)、类和对象的创建、异常处理等。...

    ACM程序设计基础之贪心法学习教案.pptx

    总的来说,贪心法是一种以局部最优策略为导向的算法,它在很多问题中提供了有效的近似解,但需要谨慎使用,因为不是所有问题都能通过贪心策略达到全局最优。在ACM程序设计竞赛和实际编程中,理解贪心法的原理和应用...

    suanfafenxi.rar_动态规划法

    3. **回溯法**:回溯法是一种试探性的解决问题的方法,当遇到局部最优解时,能够“回退”并尝试其他路径。它常用于解决组合优化问题,如八皇后问题、图着色问题等。“回溯法.rar”应该包含了回溯法的基本原理、实现...

    ACM国际大学生程序设计竞赛:知识与入门

    ACM(Association for Computing Machinery)国际大学生程序设计竞赛是全球最具影响力的计算机科学竞赛之一,旨在提升学生们的算法设计、问题解决和编程能力。这本书涵盖了从基础到高级的算法,适合不同水平的参赛者...

    C++程序设计入门训练

    总的来说,"C++程序设计入门训练"涵盖了一系列基础的编程概念和算法,包括回溯法、动态规划、递归、循环、条件判断、数组操作、链表、树结构、图论、搜索算法和数值计算等。通过解决这些问题,初学者不仅能掌握C++...

Global site tag (gtag.js) - Google Analytics