前言
本文介绍一种经典算法——回溯法，可作为迷宫问题的一种解法。
一、回溯法
回溯是一种算法思想，用递归实现，类似于枚举的搜索尝试过程。主要思想在于搜索尝试过程中寻找问题的解，当发现不满足求解条件时，则立刻回溯返回，尝试别的解决方案。可作为一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现该选择不优或者无法达到目标，就退回一步重新进行选择，而满足回溯条件的某个状态点称为“回溯点”。
二、算法应用——迷宫问题
1.问题描述
迷宫问题是回溯法的一种应用。迷宫问题的描述为：假设主体放在一个迷宫地图入口处，迷宫中有许多墙，使得大多数的路径都被挡住而无法行进。主体可以通过遍历所有可能到出口的路径来到达出口。当主体走错路时需要将走错的路径记录下来，避免下次走重复的路径，直到找到出口。主体需遵从如下三个原则：
- 一次步进只能走一格；
- 遇到路径堵塞后，退后直到找到另一条路径可行；
- 走过的路径记录下来，不会再走第二次。
2.解题思路
先创建一个二维数组Map[row][col]并进行初始化，Map[i][j]=1表示该位置有墙体无法通过，Map[i][j]=0表示该位置未走过，Map[i][j]=2表示该位置已经走过并且可以走通，Map[i][j]=3表示该位置已经走过并且无法走通。假设Map[1][1]为入口，Map[6][5]为出口。
当主体在迷宫行进的时候有四个方向即上下左右可以选择，如图所示：
三、Java代码实现
public class MiGong
{
public static void main(String[] args) {
//创建二维数组模拟迷宫
int[][] map = new int[8][7];
//使用1表示墙
//上下置为1
for (int i = 0; i < 7; i++)
{
map[0][i] = 1;
map[7][i] = 1;
}
//左右置为1
for (int i = 0; i < 8; i++)
{
map[i][0] = 1;
map[i][6] = 1;
}
//挡板
map[3][1] = 1;
map[3][2] = 1;
map[2][2] = 1;
map[6][4] = 1;
map[5][4] = 1;
map[4][4] = 1;
//输出地图
System.out.println("原地图:");
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 7; j++)
{
System.out.print(map[i][j]+"\t");
}
System.out.println();
}
setWay(map,1,1);
System.out.println("递归回溯后得到路线:");
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 7; j++)
{
System.out.print(map[i][j]+"\t");
}
System.out.println();
}
}
/**
* 使用递归回溯找路
* 1.i和j表示从地图的(i,j)开始出发
* 2.如果能走到map[6][5]则说明通路已经找到
* 3.map[i][j]中 0:该点没有走过 1:墙 2:该通路可以走 3:已经走过但是无法走通
* 走迷宫时确定一个策略: 下->右->上->左 该点走不通再回溯
* @param map 表示地图的数组
* @param i 从哪个位置开始找
* @param j
* @return 找到通路返回true 否则返回false
*/
public static boolean setWay(int[][] map,int i,int j)
{
//通路已经找到
if (map[6][5] == 2)
{
return true;
}else
{
//该点没有走过
if (map[i][j] == 0)
{
//策略: 下->右->上->左
//先赋值2假定可以走通
map[i][j] = 2;
//向下走
if (setWay(map, i+1, j))
{
return true;
}
//向右走
else if (setWay(map, i, j+1))
{
return true;
}
//向上走
else if (setWay(map, i-1, j))
{
return true;
}
//向左走
else if (setWay(map, i, j-1))
{
return true;
}
else
{
//该点走不通
map[i][j] = 3;
return false;
}
}
else
{
//map[i][j]!=0 ---> 1/2/3
return false;
}
}
}
}
测试结果如下：
原地图:
1 1 1 1 1 1 1
1 0 0 0 0 0 1
1 0 1 0 0 0 1
1 1 1 0 0 0 1
1 0 0 0 1 0 1
1 0 0 0 1 0 1
1 0 0 0 1 0 1
1 1 1 1 1 1 1
递归回溯后得到路线:
1 1 1 1 1 1 1
1 2 2 2 0 0 1
1 3 1 2 0 0 1
1 1 1 2 2 2 1
1 3 3 3 1 2 1
1 3 3 3 1 2 1
1 3 3 3 1 2 1
1 1 1 1 1 1 1
以上。
如有不足或者错误欢迎评论指正。