您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

告诉我,[回溯法]究竟是什么?浅谈回溯法的算法理解

注:这篇文章适合刚接触回溯法,想结合一定的代码轻松理解回溯法的像我一样的算法小白们。

最近在leetcode上面刷题的时候,经常遇到题解里面告诉我们用“回溯法”解决的问题。

例如大家熟悉的求字符串的全排列,求字符串的子串等问题。

我之前是对于回溯法完全不理解的,这个不理解,不是说我不懂回溯是什么。而是完全写不出回溯法的算法来。

所以对于那些问题,自然也就没有用回溯法,一般使用递归或者动态规划的思想完成的。所以我一直没把回溯法放在心上,直到我遇到了这个题目:单词搜索。

单词搜索题

 

但凡是思维正常的人,看到这个题目脑海里面想到的一定就是所谓的“回溯法”了。我之前说过,回溯法的“原理”谁都懂:从某一个点出发,像走迷宫那样,往上下左右尝试走走看,如果符合条件可以走就走下去,直到找到符合题意的路径;如果遇到了走不通的情况,那么就调头回去继续尝试。如果到最后所有的地方都尝试过了,那么就说明找不到符合题意的路径了。

为什么说人人都懂呢?因为这特喵的就是一般人类解决这种问题的思维嘛。

好了,原理懂了,那我们开始写算法把。

。。。

。。。

。。。

算法。怎么写?

 

这就是我刚开始接触到回溯法的感觉,完全不知道怎么写。合情合理地,我就在网络上面搜索了一下。搜索的结果让我特别无语。

要么一上来直接给你扔一长串8皇后问题的代码,说很简单,自己看看代码不就明白了;要么讲完回溯法的思想之后马上开始讲什么,解空间啊,状态空间树啊,约束函数什么的。说实话,我看得有点懵。我希望有一个清晰的,给算法新手讲解回溯法原理的文章。

暂时没发现

于是我在折腾一阵子过后,自己写下了这篇文章,我认为我已经初步了解回溯法的实现原理了。于是我以这道题目为例,给大家讲解一下回溯法的算法究竟是怎么写出来的。我觉得理解回溯法最核心的问题在于:

程序究竟是如何回溯的?假设我走迷宫的时候走到了某一点A发现走不下去了,我现在准备使用我的回溯法调头。我该调头到哪?我需要记录我怎么调头吗?

答:程序的回溯,是靠程序运行时候的递归栈完成的。我该调头到哪,我要不要记录怎么调头,不是我们写代码时候关心的内容。

回溯法里面最重要的回溯,居然是自动完成的。我之前不能完全理解回溯法,就卡壳在这里。

举个例子,我们经过了“ABCD”四个点,然后我们在D点的时候发现走不下去了,要回溯。我们就要调头回去,因为回溯函数是递归调用的,所以所有的回溯函数全部存放在一个递归栈中,程序自然而然地将运行不下去的D点函数出栈,回溯到了C点。然后递归地进行所有的判断。这样就可以完成整个走迷宫的过程。是不是很简单- -

|D|        | |
|C|  回溯  |C|
|B|   -->  |B|
|A|        |A|
- -        - -

既然知道了这个核心思路,那么我们终于可以开始写算法了。

一、全局变量

private boolean[][] marked; //记录这个点是不是被访问过了
private int[][] direction = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};//上下左右四个方向
private int m;// 盘面上有多少行
private int n;// 盘面上有多少列
private String word; //题目给出的word
private char[][] board; //题目给出的矩阵board

为什么回溯法解题需要那么多全局变量呢,自然是因为回溯法的完成是在递归栈里面完成的,不可以把变量当做递归函数的参数进行调用,这样参数可能会在递归运行时发生改变。

二、核心的backtrace函数

三、开始回溯

四、完整代码

import java.util.*;


class Solution {
    private boolean[][] marked;
	    private int[][] direction = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
	    // 盘面上有多少行
	    private int m;
	    // 盘面上有多少列
	    private int n;
	    private String word;
	    private char[][] board;
    
    public  boolean backtrace(int x,int y,int start){
        if(start == word.length()-1&&board[x][y]==word.charAt(start)) return true;
        if(board[x][y]==word.charAt(start)){
            marked[x][y]=true;//x,y这个点走了
            for(int k=0;k<4;k++){//有上下左右四种走法
                int newX = x + direction[k][0];
	            int newY = y + direction[k][1];
                if((marked[newX][newY]==false)&&inArea(newX, newY)){
                    
                    if(backtrace(newX,newY,start+1)==true) return true;
                }
            }
            marked[x][y]=false;//以这个点为起点不满足题意,在结束尝试后将mark置为false
        }
        
        return false;   //以x y为起点无法找到满足题意的路线
        
    }
    
    public  boolean inArea(int x, int y) { //判断是否越界
	        return x >= 0 && x < m && y >= 0 && y < n;
	    }
    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        this.word = word;
        this.board = board;
        marked = new boolean[m][n];
        for (int x = 0; x< m; x++) {
	            for (int y = 0; y < n; y++) { 
	                if (backtrace(x, y, 0)) {
	                    return true;
	                }
	            }
	        }
        return false;
        
        
    }
}

 

编辑于 2020-09-30


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进