数据结构 --- 回溯算法

回溯算法

活动地址：CSDN21天学习挑战赛

一、什么是回溯算法

• 宏观的来看，回溯算法是一个十分类似于枚举的搜索尝试算法，其功能是在每一次的尝试过程中寻找问题的解；

• 在发现当前尝试的情况不满足条件的时候，就返回到上一步（实现一个回溯的效果），再进行另一种方案的尝试；

1.1 基本思想

从一方案往前探，能进则进，不能进则退回一步，换一个方案再进行探测；

二、如何理解回溯算法

（1）例题

有如下图的一个房间，房间内有一只老鼠，现在在房间入口放一只猫，现要求编写一个 FindingWay() 方法，用于判断猫可不可以找到老鼠；

（ | | 是墙，不可通过，因为只需要测试入口到老鼠的路径是否存在，故可忽略老鼠移不移动的问题； FindingWay() 方法为布尔型，内有三个参数一个是代表房间的数组，一个为数组的行坐标，一个为数组的列坐标）

图 2.1

（2）图解法

2.2.1

这个问题本质上是跟我们小时候玩的迷宫游戏一个道理，我们很难一次就把迷宫走通，一般情况下我们都是通过对每一条路的尝试，最终得到一条达到终点的路径；

回到这个问题，我们将其看成一个迷宫从入口开始对每一条路径进行排查，直到找到老鼠或走遍每一条路径为止；

图 2.2.1

2.2.2

当猫每处于一个路口的时候，都有可能走任意一个方向；

图 2.2.2

2.2.3

当猫走到一条死路的时候，需要回头继续寻找新的路径；

图 2.2.3

2.2.4

最终猫到达鼠的位置，证明了入口到老鼠的位置的路径存在；

图 2.2.4

（3）代码演示

2.3.1

如果当前位置是老鼠则返回 true 表示存在入口到老鼠的路径；

图 2.3.1

2.3.2

如果当前坐标不为老鼠就代表还未找到老鼠，这时候再进行判断是否为为走过的路，如果是未走过的路就将这个坐标标记为 Y 代表走过这个位置已走过，反之则代表当前位置无法进入并返回 false ；

图 2.3.2

2.3.3

如果当前路可以走就再往上下左右任意一个方向继续探测，如果没有能走的路就将当前位置标记为 X 表示是一条死路；

图 2.3.3

如果最终所有路径都走完了就代表无法找到老鼠；

三、代码分享

public class test {

    public static String[][] room = new String[10][10];
    public static void main(String[] args) {

        for (int i = 0; i < room.length; i++) {
            for (int j = 0; j < room[0].length; j++) {
                room[i][j] = " ";
            }
        }

        for (int i = 0; i < room.length; i++) {
                room[i][0] = room[0][i] = room[i][9] = room[9][i] = "| |";
        }
        for (int i = 0; i < 6; i++) {
            room[2][i+2] = room[7][i+2] = room[i+2][2] = room[i+2][7] = "| |";
        }
        room[6][3] = "鼠";
        room[0][1] = "入口";
        room[3][7] = " ";
        room[8][7] = "| |";

        if ( FindingWay(room, 1, 1) ){
            System.out.println( "可以找到老鼠。" );
        }else {
            System.out.println( "无法找到老鼠。" );
        }
    }

    public static boolean FindingWay( String[][] Now , int i , int j ){
        if ( Now[i][j].equals("鼠") ){
            return true;
        } else {
            if ( Now[i][j].equals(" ") ){
                Now[i][j] = "Y";
                if (FindingWay( Now, i - 1, j)){
                    return true;
                }else if (FindingWay( Now, i, j + 1)){
                    return true;
                }else if(FindingWay( Now, i + 1, j)){
                    return true;
                }else if(FindingWay( Now, i, j - 1)){
                    return true;
                }else {
                    Now[i][j] = "X";
                    return false;
                }
            }else {
                return false;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53