解空间树(回溯算法，分支界限法)
解空间树：是依据待解决问题的特性，用树结构表示问题的解结构、用叶子表示问题的解的一颗树。
一、回溯法：采取深度遍历策略搜索解空间树，若当前结点不满足问题的求解要求，则回溯到树的上一层继续搜索另一棵子树，这种解决问题的方法称为回溯法；
1、用回溯法求解问题，重点是设计问题的解空间树，解题过程就是搜索解空间树的过程；
2、构造解空间树，就是将求解的一系列判断决策过程及各种可能的结果用树形结构呈现；
N皇后问题，在给定的N×N的棋盘上放置N个皇后，要求给出各皇后彼此不受攻击（不在同一行，同一列，同一对角线）的所有可能的棋盘布局。
解题思路，可用一维数组表示N皇后问题的解，queen[k]表示第k行皇后所在的列号；
1 /* c语言代码 */
2 #include
3 /* 八皇后 */
4 const int N = 8;
5 int queens[N] = {0};
6 /* 打印 */
7 void print(int count){
8 printf("%-3d[",count);
9 for(int i=0; i 10 if(i) 11 printf(","); 12 printf("%d",queens[i]); 13 } 14 printf("]\n"); 15 } 16 /* 可以放 */ 17 int can_place(int k, int i){ 18 for(int j=0; j 19 if(queens[j] == i || queens[j] - i == j - k|| 20 queens[j] - i == k - j) return 0; 21 } 22 return 1; 23 } 24 /* 放 */ 25 void place(int k){ 26 if(k == N){ 27 static int count = 0; 28 count++; 29 print(count); 30 } 31 else{ 32 for(int i=0; i 33 { 34 if(can_place(k,i)) 35 { 36 queens[k] = i; 37 place(k+1); 38 } 39 } 40 } 41 } 42 int main() 43 { 44 place(0); 45 return 0; 46 } 1 #python 代码 2 N = 8 3 queens = [0] * N 4 count = 0 5 def can_place(k,i): 6 for j in range(k): 7 if queens[j] == i or queens[j]-i == j-k or queens[j]-i == k-j: 8 return False 9 return True 10 11 def place(k): 12 if k == N: 13 global count 14 count = count + 1 15 print(count,queens) 16 else: 17 for i in range(N): 18 if can_place(k,i): 19 queens[k] = i 20 place(k+1) 21 22 place(0) 二、分支界限法，通过遍历解空间树来求解问题，通过结点优先级的设计，采用广度优先，结合优先队列，的策略遍历解空间树，适用于求取问题的最优解或满足条件的一个解； 分支界限法搜索策略： 1、从根开始，首先生成当前结点所有可能的儿子，并计算儿子结点的优先级，将其放入优先队列中； 2、从优先队列中选择一个优先级最高(最有可能得到最优解)的结点出队，并作为当前结点继续生成其各儿子结点、计算优先级且入队； 3、重复2，直至到达叶子结点，找到满足要求的一个解，或搜索到最优解；