人工智能基础-搜索树的扩展和n皇后问题

前往我的主页以获得更好的阅读体验人工智能基础-搜索树的扩展与n皇后问题 - DearXuan的主页https://blog.dearxuan.com/2021/10/27/人工智能基础-搜索树的扩展与n皇后问题/

贪心算法

算法原理

贪心算法也属于启发式算法的一种。贪心算法从来不关注整体，而总是选择基于当前状态下的最优解，贪心可以看成A*的一种特殊情况

迷宫问题

 贪心算法从不关注g(N)，因此只需要每次都比较相邻节点里的h(N)即可

贪心算法得到的路径为: A-C-H-I-J-P

回溯算法

算法原理

回溯算法是DFS的扩展，在DFS的基础上多了剪枝函数，剪枝函数包括约束函数和限界函数，用于判断当前节点是否符合题意，如果不符合，则原路返回。由于多了判断，因此遍历的节点比DFS更少，速度也更快

通常情况下，可以把问题的解转化成多叉树，当一个节点满足题意时，才会继续遍历它的子树，否则直接跳过当前节点

约束函数

约束函数用来排除不可能存在解的情况。例如四皇后问题中，分别在(0,0)和(2,1)位置放上皇后，此时整个棋盘只剩下(1,3)位置

显然这种情况不满足题意，因此跳过该情况对应的节点

限界函数

限界函数用来排除非最优解的情况。例如在路径规划，已经找到了一条长度为10的通路，而当前节点的g(N)已经大于10，那么当前节点的子树中不可能存在比10更短的通路，因此跳过该节点 

n皇后问题

问题描述

将n个皇后放在n×n的方格纸上，使n个皇后彼此之间不在同一行，同一列，统一对角线上。给出所有摆法

状态定义

定义一维数组queen[n]来表示皇后位置，queen[i]=j表示第i行的皇后在j列，若j=-1则表示第i行没有皇后(目前没有，但是最终一定会有)

例如

queen[] = {2,0,3,1}表示皇后位置如下

冲突检测

显然用一维数组表示法，不可能出现皇后在同一行的情况，因此只需要比较列和对角线

1.  
   //检查当前状态下是否有冲突
2.  
   bool CheckConflict() {
3.  
   for (int i = 0; i < N; i ) {
4.  
   //queen[i] == -1表示还没有放上皇后
5.  
   if(queen[i] == -1) continue;
6.  
   for (int j = i 1; j < N; j ) {
7.  
   //queen[j] == -1表示还没有放上皇后
8.  
   if(queen[j] == -1) continue;
9.  
   //第i行和第j行的皇后在同一列
10.  
    if (queen[i] == queen[j]) return false;
11.  
    //对角线冲突
12.  
    if (abs(i - j) == abs(queen[i] - queen[j])) return false;
13.  
    }
14.  
    }
15.  
    return true;
16.  
    }

约束函数

约束函数CheckEnable(int i,int j)用于判断能否在(i,j)处放置皇后，如果不能，则不需要继续遍历

1.  
   //约束函数，检查当前状态下，能否在(i,j)放置皇后
2.  
   bool CheckEnable(int i, int j) {
3.  
   queen[i] = j;//假设(i,j)上有皇后
4.  
   bool flag = CheckConflict();//判断是否有冲突
5.  
   queen[i] = -1;//恢复原状
6.  
   return flag;
7.  
   }

回溯

1.  
   //查找第i行的皇后位置
2.  
   void Search(int i) {
3.  
   if(i >= N){
4.  
   num ;
5.  
   Print();
6.  
   return;
7.  
   }
8.  
   //遍历(i,j)的所有情况
9.  
   for(int j=0;j<N;j ){
10.  
    //判断(i,j)能否放置皇后
11.  
    if(CheckEnable(i,j)){
12.  
    //可以放置,尝试将皇后放入(i,j)
13.  
    queen[i] = j;
14.  
    //查找第i 1行的放法
15.  
    Search(i 1);
16.  
    //拿走皇后
17.  
    queen[i] = -1;
18.  
    }
19.  
    }
20.  
    }

完整代码

1.  
   #include <iostream>
2.  
   #include <queue>
3.  
    
4.  
   using namespace std;
5.  
    
6.  
   #define N 4
7.  
    
8.  
   //数组表示皇后未知，queen[i]表示第i行的皇后在第几列，-1表示未放置
9.  
   int queen[N];
10.  
    //解的总数
11.  
    int num = 0;
12.  
     
13.  
    void Print();
14.  
    void Search(int i);
15.  
     
16.  
    int main() {
17.  
    for (int &i: queen) {
18.  
    i = -1;
19.  
    }
20.  
    Search(0);
21.  
    printf("Total Answer: %d",num);
22.  
    return 0;
23.  
    }
24.  
     
25.  
    //检查当前状态下是否有冲突
26.  
    bool CheckConflict() {
27.  
    for (int i = 0; i < N; i ) {
28.  
    //queen[i] == -1表示还没有放上皇后
29.  
    if(queen[i] == -1) continue;
30.  
    for (int j = i 1; j < N; j ) {
31.  
    //queen[j] == -1表示还没有放上皇后
32.  
    if(queen[j] == -1) continue;
33.  
    //第i行和第j行的皇后在同一列
34.  
    if (queen[i] == queen[j]) return false;
35.  
    //对角线冲突
36.  
    if (abs(i - j) == abs(queen[i] - queen[j])) return false;
37.  
    }
38.  
    }
39.  
    return true;
40.  
    }
41.  
     
42.  
    //约束函数，检查当前状态下，能否在(i,j)放置皇后
43.  
    bool CheckEnable(int i, int j) {
44.  
    queen[i] = j;//假设(i,j)上有皇后
45.  
    bool flag = CheckConflict();//判断是否有冲突
46.  
    queen[i] = -1;//恢复原状
47.  
    return flag;
48.  
    }
49.  
     
50.  
    //遍历第i行的皇后位置
51.  
    void Search(int i) {
52.  
    if(i >= N){
53.  
    num ;
54.  
    Print();
55.  
    return;
56.  
    }
57.  
    //遍历(i,j)的所有情况
58.  
    for(int j=0;j<N;j ){
59.  
    //判断(i,j)能否放置皇后
60.  
    if(CheckEnable(i,j)){
61.  
    //可以放置,尝试将皇后放入(i,j)
62.  
    queen[i] = j;
63.  
    //查找第i 1行的放法
64.  
    Search(i 1);
65.  
    //拿走皇后
66.  
    queen[i] = -1;
67.  
    }
68.  
    }
69.  
    }
70.  
     
71.  
    void Print(){
72.  
    for(int i : queen){
73.  
    for(int j=0;j<N;j ){
74.  
    if(i == j){
75.  
    printf("1 ");
76.  
    } else{
77.  
    printf("0 ");
78.  
    }
79.  
    }
80.  
    printf("\n");
81.  
    }
82.  
    printf("\n");
83.  
    }
84.  
     

当n = 4时 

当n = 8时

这篇好文章是转载于：学新通技术网