前往我的主頁以獲得更好的閱讀體驗

人工智能基礎-搜索樹的擴展與n皇后問題 - DearXuan的主頁https://www.dearxuan.top/2021/10/27/%E4%BA%BA%E5%B7%A5%E6%99%BA%E8%83%BD%E5%9F%BA%E7%A1%80-%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%89%A9%E5%B1%95%E4%B8%8En%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98/

貪心演算法

演算法原理

貪心演算法也屬于啟發式演算法的一種，貪心演算法從來不關注整體，而總是選擇基于當前狀態下的最優解，貪心可以看成A*的一種特殊情況

在上一篇博客中，已經知道A*演算法的綜合優先級為f(N)=g(N)+h(N)，這里的只需要令g(N)=0，f(N)便是當前狀態下的預計花費，只需要每次都選擇h(N)最小的路徑，便是當前狀態下的最優解

迷宮問題

貪心演算法從不關注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}表示皇后位置如下

沖突檢測

顯然用一維陣串列示法，不可能出現皇后在同一行的情況，因此只需要比較列和對角線

//檢查當前狀態下是否有沖突
bool CheckConflict() {
    for (int i = 0; i < N; i++) {
        //queen[i] == -1表示還沒有放上皇后
        if(queen[i] == -1) continue;
        for (int j = i + 1; j < N; j++) {
            //queen[j] == -1表示還沒有放上皇后
            if(queen[j] == -1) continue;
            //第i行和第j行的皇后在同一列
            if (queen[i] == queen[j]) return false;
            //對角線沖突
            if (abs(i - j) == abs(queen[i] - queen[j])) return false;
        }
    }
    return true;
}

約束函式

約束函式CheckEnable(int i,int j)用于判斷能否在(i,j)處放置皇后，如果不能，則不需要繼續遍歷

//約束函式，檢查當前狀態下，能否在(i,j)放置皇后
bool CheckEnable(int i, int j) {
    queen[i] = j;//假設(i,j)上有皇后
    bool flag = CheckConflict();//判斷是否有沖突
    queen[i] = -1;//恢復原狀
    return flag;
}

回溯

//查找第i行的皇后位置
void Search(int i) {
    if(i >= N){
        num++;
        Print();
        return;
    }
    //遍歷(i,j)的所有情況
    for(int j=0;j<N;j++){
        //判斷(i,j)能否放置皇后
        if(CheckEnable(i,j)){
            //可以放置,嘗試將皇后放入(i,j)
            queen[i] = j;
            //查找第i+1行的放法
            Search(i+1);
            //拿走皇后
            queen[i] = -1;
        }
    }
}

完整代碼

#include <iostream>
#include <queue>

using namespace std;

#define N 4

//陣串列示皇后未知，queen[i]表示第i行的皇后在第幾列，-1表示未放置
int queen[N];
//解的總數
int num = 0;

void Print();
void Search(int i);

int main() {
    for (int &i: queen) {
        i = -1;
    }
    Search(0);
    printf("Total Answer: %d",num);
    return 0;
}

//檢查當前狀態下是否有沖突
bool CheckConflict() {
    for (int i = 0; i < N; i++) {
        //queen[i] == -1表示還沒有放上皇后
        if(queen[i] == -1) continue;
        for (int j = i + 1; j < N; j++) {
            //queen[j] == -1表示還沒有放上皇后
            if(queen[j] == -1) continue;
            //第i行和第j行的皇后在同一列
            if (queen[i] == queen[j]) return false;
            //對角線沖突
            if (abs(i - j) == abs(queen[i] - queen[j])) return false;
        }
    }
    return true;
}

//約束函式，檢查當前狀態下，能否在(i,j)放置皇后
bool CheckEnable(int i, int j) {
    queen[i] = j;//假設(i,j)上有皇后
    bool flag = CheckConflict();//判斷是否有沖突
    queen[i] = -1;//恢復原狀
    return flag;
}

//遍歷第i行的皇后位置
void Search(int i) {
    if(i >= N){
        num++;
        Print();
        return;
    }
    //遍歷(i,j)的所有情況
    for(int j=0;j<N;j++){
        //判斷(i,j)能否放置皇后
        if(CheckEnable(i,j)){
            //可以放置,嘗試將皇后放入(i,j)
            queen[i] = j;
            //查找第i+1行的放法
            Search(i+1);
            //拿走皇后
            queen[i] = -1;
        }
    }
}

void Print(){
    for(int i : queen){
        for(int j=0;j<N;j++){
            if(i == j){
                printf("1 ");
            } else{
                printf("0 ");
            }
        }
        printf("\n");
    }
    printf("\n");
}

當n = 4時

當n = 8時