回溯算法

回溯算法

主要思想

回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。八皇后问题就是回溯算法的典型,第一步按照顺序放一个皇后,然后第二步符合要求放第2个皇后,如果没有位置符合要求,那么就要改变第一个皇后的位置,重新放第2个皇后的位置,直到找到符合条件的位置就可以了。回溯在迷宫搜索中使用很常见,就是这条路走不通,然后返回前一个路口,继续下一条路。回溯算法说白了就是穷举法。不过回溯算法使用剪枝函数,剪去一些不可能到达 最终状态(即答案状态)的节点,从而减少状态空间树节点的生成。回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时,总是先判断该结点是否肯定不包含问题的解。如果肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层向其祖先结点回溯。否则,进入该子树,继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时,只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法,它适用于解一些组合数较大的问题。回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。用回溯算法解决问题的一般步骤为:

  1. 定义一个解空间,它包含问题的解。
  2. 利用适于搜索的方法组织解空间。
  3. 利用深度优先法搜索解空间。
  4. 利用限界函数避免移动到不可能产生解的子空间。

解决迷宫问题

解决思想

将迷宫问题对应为二维数组,数组中只有两种值0和1,其中0,1分别表示通路和墙。不过在解决这个问题的时候一般要在最外面添加一个围墙,这里设置每个围墙都为1,这样有利于防止当走到了迷宫的出口处还会向前走,这个并不一定,只是最一般的方法,也是最有利于理解的方法。这里的利用到了回溯法,需要走到了一个位置,然后向四处试探,如果有一个方向可以走了就将当前的点压入栈,并且标记当前点以便于区分是否走过,如果四处都无出路,只需要回到前一个走到的点,然后从前一个点再换一个方向重新走

代码

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146

import java.util.Stack;/** * Created by chenjiabing on 17-5-5. */class position { public int row; public int col; public position(int row, int col) { this.col = col; this.row = row; } public position() { row = 0; col = 0; } public String toString() { return "(" + (row - 1) + " ," + (col - 1) + ")"; } //这里由于四周围上了墙,所以这里的输出就要在原来的基础上减一}class Main { private int[][] maze = null; private Stack<position> stack = null; //创建一个栈用于存储状态 private int row; //行数 private int col; boolean[][] p = null; //这里的p是用来标记已经走过的点,初始化为false public boolean end(int i, int j) { return i == row && j == col; } public Main(int[][] maze) { stack = new Stack<position>(); row = maze[0].length;// 行数 col = maze.length; //列数 p = new boolean[row + 2][col + 2]; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { p[i][j] = false; //初始化 } } this.maze = maze; } public void findPath() { //创建一个新的迷宫,将两边都围上墙,也就是在四周都填上1的墙,形成新的迷宫,主要的目的就是防止走到迷宫的边界的出口的位置还会继续向前走 //因此需要正确的判断是否在边界线上,所以要在外围加上一堵墙, int[][] temp = new int[row + 2][col + 2]; for (int i = 0; i < row + 2; i++) { for (int j = 0; j < col + 2; j++) { temp[0][j] = 1; //第一行围上 temp[row + 1][j] = 1; //最后一行围上 temp[i][0] = temp[i][col + 1] = 1; //两边的围上 } } // 将原始迷宫复制到新的迷宫中 for (int i = 0; i < row; ++i) { for (int j = 0; j < col; ++j) { temp[i + 1][j + 1] = maze[i][j]; } } int i = 1; int j = 1; p[i][j] = true; stack.push(new position(i, j)); //这里是是将走到的点入栈,然后如果前后左右都走不通的话才出栈 while (!stack.empty() && !end(i, j)) { //下面就开始在四周试探,如果有路就向前走,顺序分别是右,下,上,左,当然这是随便定义的,不过一般都是现向下和右的 if (temp[i][j + 1] == 0 && p[i][j + 1] == false)//这里如果不在四周加上墙,那么在到达边界判断的时候就会出现超出数组的索引的错误,因为到达边界再加一就会溢出 { p[i][j + 1] = true; stack.push(new position(i, j + 1)); j++; } else if (temp[i + 1][j] == 0 && p[i + 1][j] == false)//如果下面可以走的话,讲当前点压入栈,i++走到下一个点 { p[i + 1][j] = true; stack.push(new position(i + 1, j)); i++; } else if (temp[i][j - 1] == 0 && p[i][j - 1] == false) { p[i][j - 1] = true; stack.push(new position(i, j - 1)); j--; } else if (temp[i - 1][j] == 0 && p[i - 1][j] == false) { p[i - 1][j] = true; stack.push(new position(i - 1, j)); i--; } else //前后左右都不能走 { System.out.println(i + "---------" + j); stack.pop(); //这个点不能走通,弹出 if (stack.empty()) //如果此栈中已经没有点了,那么直接跳出循环 { System.out.println("没有路径了,出不去了"); return; //直接退出了,下面就不用找了 } i = stack.peek().row; //获得最新点的坐标 j = stack.peek().col; } //如果已经到达了边界,那么直接可以出去了,不需要继续向前走了,这里是规定边界的任意为0的位置都是出口 //如果不加这个判断的话,那么当到达边界的时候,只有走到不能再走的时候才会输出路线,那种线路相对这个而言是比较长的 if (j == temp[0].length - 2) { //如果已经到达边界了,那么当前的位置就是出口,就不需要再走了 Stack<position> pos = new Stack<position>(); System.out.println("路径如下:"); for (int count = 0; count < stack.size(); count++) { System.out.println(stack.elementAt(count)); } } } } public static void main(String args[]) { int[][] maze = { {0, 1, 0, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 0, 0, 0}, {0, 1, 1, 1, 0}, {0, 0, 0, 1, 0} }; Main main = new Main(maze); main.findPath(); }}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

洛谷P4316 绿豆蛙的归宿(期望)

给出一个有向无环图,起点为1终点为N,每条边都有一个长度,并且从起点出发能够到达所有的点,所有的点也都能够到达终点。绿豆蛙从起点出发,走向终点。 到达每一个顶点...

944
来自专栏tkokof 的技术,小趣及杂念

Sweet Snippet系列 之 随机选择

  平日工作学习时总会遇到一些令人欣喜的代码段子(Snippet),虽然都很短小,但是其间所含的道理都颇有意味,遂而觉得应该不时的将她们记下,一来算作复习整理,...

1112
来自专栏数据结构与算法

BZOJ4872: [Shoi2017]分手是祝愿

Description Zeit und Raum trennen dich und mich. 时空将你我分开。B 君在玩一个游戏,这个游戏由 n 个灯和 n...

2945
来自专栏小樱的经验随笔

回溯算法入门及经典案例剖析(初学者必备宝典)

前言 基于有需必写的原则,并且当前这个目录下的文章数量为0(都是因为我懒QAQ),作为开局第一篇文章,为初学者的入门文章,自然要把该说明的东西说明清楚,于是。。...

4284
来自专栏数据结构与算法

BZOJ2216: [Poi2011]Lightning Conductor(DP 决策单调性)

首先把给出的式子移项,我们要求的$P_i = max(a_j + \sqrt{|i - j|}) - a_i$。

1332
来自专栏深度学习那些事儿

pytorch新手需要注意的隐晦操作Tensor,max,gather

先看官方的介绍: 如果input是一个n维的tensor,size为 (x0,x1…,xi−1,xi,xi+1,…,xn−1),dim为i,然后index必须...

1.2K8
来自专栏数据结构与算法

网络流应用

刷了一天最大流的题,都快刷晕了,, 简单总结几个模型吧。 大部分内容来自学姐的PPT 拆点 一个非常有用的思想 限流 将对点的限制转化为对边的限制 点的合并 ...

3959
来自专栏懒人开发

(5.5)James Stewart Calculus 5th Edition:The Substitution Rule

注意: 这里 自变量改变,对应范围也会改变 不定积分的上下限,由 [a, b] 变为了 [g(a), g(b)]

1033
来自专栏算法修养

POJ 1964&HDU 1505&HOJ 1644 City Game(最大0,1子矩阵和总结)

最大01子矩阵和,就是一个矩阵的元素不是0就是1,然后求最大的子矩阵,子矩阵里的元素都是相同的。 这个题目,三个oj有不同的要求,hoj的要求是5s,...

3174
来自专栏应兆康的专栏

100个Numpy练习【5】

Numpy是Python做数据分析必须掌握的基础库之一,非常适合刚学习完Numpy基础的同学,完成以下习题可以帮助你更好的掌握这个基础库。

60110

扫码关注云+社区

领取腾讯云代金券