回顾法入门学习之一
回溯法入门学习之一
一： 回溯法
有时我们要得到问题的解，先从其中某一种情况进行试探，在试探过程中，一旦发现原来的选择是错误的，那么就退回一步重新选择， 然后继续向前试探，反复这样的过程直到求出问题的解。比喻:“下棋”： 每一次走棋的位置都要考虑到是否是损人利己，如果是害人害己的走法就要回撤，找下一步损人利己的走法。又如玩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个方向中尝试一个个可以走的点，直到返回起点,不能的话,回溯上一点,继续.
程序运行:
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
源码:
一： 回溯法
有时我们要得到问题的解，先从其中某一种情况进行试探，在试探过程中，一旦发现原来的选择是错误的，那么就退回一步重新选择， 然后继续向前试探，反复这样的过程直到求出问题的解。比喻:“下棋”： 每一次走棋的位置都要考虑到是否是损人利己，如果是害人害己的走法就要回撤，找下一步损人利己的走法。又如玩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
源码: