2019-10-17

回溯算法

回溯法：
回溯在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就 “回溯” 返回，尝试别的路径。按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，
回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

例子：
八皇后问题
在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？
思路：
通过分析题目可以得到，就是每一行就必须有一个皇后。
①第一种想法是假设8*8的棋盘是一个矩阵形式，那么假设皇后i和皇后j的位置为(i,Xi)和(j,Xj),只要保证两个坐标的点斜率不是1和-1就行。
②采用回溯法：
假设现在有四个皇后需要放置：
(1)假设第一个皇后放在第一行第一列的位置，那么第二行的皇后就只能放在第二行第三列/第四列位置。
(2)现在让第二个皇后放在第二行第三列的位置，那么第三行的皇后就没有位置可以放了，没有满足题意的位置了。

因此我们需要返回考虑第二个皇后的安置问题：
(2)现在让第二个皇后放在第二行第四列的位置，那么第三行的皇后就可以放在第三行第二列位置。
(3)第三行皇后放置后，第四行皇后又没位置了。

因此需要不断地去尝试，选择路径去放置

具体实现：

public class BaHuangHou{	
		public static void main(String[] args) {
			 int a[]=new int[4];
		     int number=4,count=0;
			operate(0);
			System.out.println(count);
		}

		public static boolean panduan(int n) {
			for(int i=0;i<n;i++)
			if((a[i]==a[n])||(Math.abs(n-i)==Math.abs(a[i]-a[n])))  //判断下一个皇后是否和上一个皇后在同一行或者是对角线
				return false;

			return true;
		}
		
		public static void operate(int n) {  //放置一个皇后
			if(n==number)
			{
				count++;
			}
			else if(n<number)
			{
				for(int i=0;i<number;i++)
				{
					a[n]=i;
					if(panduan(n))  //判断是否可以放置
					operate(n+1);
				}
			}
		}


}