算法系列之回溯算法

回溯算法
也称试探法，一种系统地搜索问题的解的算法。其基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试（类似穷举法）。
还记得中学时代的排列组合吗？太像了。

废话就不多说了看题估计就明白了，大概叙述一下昨天一家游戏公司的机试题：
骑士巡游：在一个8X8的格子中，骑士从任意一个格子出发，只能左、右、上、下走，走遍全部格子（不能重复走走过的格子），一共有多少种走法？

个人思路：

• 首先、定义一个二维boolean数组变量boolean[][] pan，走法总数solution_nums;对应值作为判断是否骑士走过该格子，一开始设定为false（全部没走过），然后每走过一个格子便设定其值为true。当走完一次完整的64个格子之后将走法总数+1；
• 其次，定义方法goNext（），即骑士即将走的格子，当然需要判断骑士是否越位，格子是否走过了以及判断是否已经走完所有格子了；
• 最后，当然是入口了，定义入口方法first（），假设开始点是（0,0），则first入口里就需要调用goNext（），根据根据参数判断有向上、向下、向左、向右。

实现代码：

package test.aglorith;

public class Recall {
	static int solution_nums=0;
	static boolean[][] pan=new boolean[8][8];
	
	//设置入口函数
	static void first(int i,int j){
		pan[i][j]=true;
		//up
		goNext(i-1, j, 1);
		//down
		goNext(i+1, j, 1);
		//left
		goNext(i, j-1, 1);
		//right
		goNext(i, j+1, 1);
	}
	
	static void goNext(int i,int j,int nums){
		//判断是否越界，是否走过
		if ((i>=0&i<8) && (j>=0&j<8) && pan[i][j]==false) {
			pan[i][j]=true;
			nums++;
			//判断是否走遍了所有格子
			if (nums==64) {
				solution_nums++;
				System.err.println(solution_nums+"~~");
				pan[i][j]=false;
				return;
			}
			
			//up
			goNext(i-1, j, nums);
			//down
			goNext(i+1, j, nums);
			//left
			goNext(i, j-1, nums);
			//right
			goNext(i, j+1, nums);
			
			//做好扫尾工作，擦除走过的轨迹
			pan[i][j]=false;
		}
	}
	
	public static void main(String[] args) {
		first(0, 0);//假设从（0，0）点开始
		System.err.println(solution_nums);
	}
}

时间有点长，以至于一直怀疑自己的算法有问题，可能陷入死循环。如果嫌时间太长，可以将二维数组，判断变量稍微改一下，7X7就需要挺久时间了。
经典的回溯算法中还有三着色，八皇后问题，迷宫问题。

据说这家公司的技术总监14岁就可以做出这道题了。见仁见智。

Have a nice day~

评论

2 楼 edr_ 2013-11-01  

ping2010 写道

你这个算法直接死循环了，

额，尝试把格子设为4X4或者5X5，也可以设置更小的，当然判断条件稍微改一下就好了。昨天试了7X7的走法是1570446次。8X8的就没试了~

1 楼 ping2010 2013-11-01  

你这个算法直接死循环了，