神奇搜尋算法A*

A*

A*是一種啟發式搜尋算法，又叫最佳圖搜尋算法。

何謂啟發式搜尋？

衆所周知，計算機在執行搜尋算法時是沒開上帝視角的。是以，在搜尋時，往往顯得盲目，把所有可能的狀态全部周遊，這種搜尋我們統稱盲目搜尋。

啟發式搜尋，顧名思義，其實就是給了盲目的計算機一點啟發，一點智慧，利用這些來引導計算機減少搜尋範圍，大幅降低搜尋複雜度。試想在BFS的過程中，在某一階段某些狀态成為正解的機率明顯比别的狀态要大，那我們就優先選擇這些狀态繼續BFS，達到降低複雜度的目的。那麼怎麼計算這個機率呢？

我們需要給計算機一些啟發資訊。不同的啟發資訊有不同的強度，既不能太強也不能弱，太強會導緻得不到正解，而太弱又會導緻優化效果不明顯。都說了這麼多了，那就來點具體的。

如何進行啟發式搜尋？

在A*之前，首先要提一下A算法，A*是A的一種特殊情形。

這裡我們要引入一個函數——“估價函數”。

定義一個函數\(f(n)=g(n)+h(n)\)，利用啟發資訊計算出\(h\)，根據\(f\)函數的值找出目前搜尋狀态下的最有希望的節點進行擴充。其中\(n\)是一個狀态，\(f\)就是估價函數，\(g\)是\(n\)已經用掉的開銷（可以了解做裸的BFS用到的資訊），\(h\)是一個啟發函數。

啟發函數在不同的情況下是有不同的計算方法的，這要因情況而異。

為了更好定義A*算法，我們還要引入一些函數：\(f^ *(n),g^ *(n),h^ *(n)\)。

首先我們要明确，上面提到的估價函數，是對待擴充節點的一個“估計”，是從啟發資訊計算而來的，是以從初始狀态到正解對應的狀态的花費不是實際花費。

\(f^ *(n)=g^ *(n)+h^ *(n)\)表示的是從搜尋的起點經過\(n\)狀态到達搜尋目标的實際最小花費，是以，你可以把\(f(n),g(n),h(n)\)看作這些帶*的函數的估計值。

A*算法定義為保證\(h(n)<h^ *(n)\)的A算法，其保證能得到最優解。

我們通過例題入手

P1379 八數位難題

題目描述

在3×3的棋盤上，擺有八個棋子，每個棋子上标有1至8的某一數字。棋盤中留有一個空格，空格用0來表示。空格周圍的棋子可以移到空格中。要求解的問題是：給出一種初始布局（初始狀态）和目标布局（為了使題目簡單,設目标狀态為123804765），找到一種最少步驟的移動方法，實作從初始布局到目标布局的轉變。

顯然這題可以用雙向BFS做（起點狀态和中點狀态模式相同），而且實際上裸的BFS這題也能過。。。

不過既然是在講A*，就讨論A*怎麼解（哇，發現題解有一篇我校巨佬的IDA*QWQ）。

為了使得\(h\)函數一定比\(h^ *(n)\)小，我們考慮構造一個這樣的函數。在起始狀态，\(h ^*(n)\)顯然就是所有位置的數移動到目标狀态的位置的所需步數。我們可以假定\(h(n)\)為\(n\)狀态時不在目标位置的數的個數。因為顯然，這些不再目标位置的數至少要通過一次移動才能到達目标位置。這是一個可行方案。

貼代碼：

用了一個map來去除重複狀态，其實matrix結構體裡面随便咋重載都行，反正裝的進去map就行。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
using namespace std;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct matrix{
    int a[5][5];
    bool operator<(matrix x) const{
        for(int i=1;i<=3;++i)
            for(int j=1;j<=3;++j)
                if(x.a[i][j]!=a[i][j]) return x.a[i][j]<a[i][j];
        return 0;
    }
}st,f;
inline int h(matrix a)
{
    int tmp=0;
    for(int i=1;i<=3;++i)
        for(int j=1;j<=3;++j)
            if(a.a[i][j]!=st.a[i][j]) tmp++;
    return tmp;
}
struct node{
    matrix a;
    int step;
    bool operator<(node x) const{
        return x.step+h(x.a)<step+h(a);
    }
    node(){};
    node(matrix _a,int _step){a=_a,step=_step;}
};
priority_queue<node> q;
map<matrix,bool> mp;
int main()
{
    st.a[1][1]=1,st.a[1][2]=2,st.a[1][3]=3;
    st.a[2][1]=8,st.a[2][2]=0,st.a[2][3]=4;
    st.a[3][1]=7,st.a[3][2]=6,st.a[3][3]=5;
    char c;
    for(int i=1;i<=3;++i)
        for(int j=1;j<=3;++j){
            scanf("%c",&c);
            f.a[i][j]=c-'0';
        }
    q.push(node(f,0));
    while(q.size()){
        node x=q.top();q.pop();
        if(!h(x.a)){
            printf("%d\n",x.step);
            return 0;
        }
        if(mp[x.a]) continue;
        mp[x.a]=1;
        int nx,ny;
        for(int i=1;i<=3;++i)
            for(int j=1;j<=3;++j)
                if(!x.a.a[i][j]) nx=i,ny=j;
        for(int i=0;i<4;++i){
            int xx=nx+dir[i][0],yy=ny+dir[i][1];
            if(xx>=1&&xx<=3&&yy>=1&&yy<=3){
                swap(x.a.a[xx][yy],x.a.a[nx][ny]);
                q.push(node(x.a,x.step+1));
                swap(x.a.a[xx][yy],x.a.a[nx][ny]);
            }
        }
    }
    return 0;
}                

如果要加ID的話會更快，這裡不詳細講，具體做法跟一般IDBFS是一樣的。

P2324 [SCOI2005]騎士精神

跟上面這道題完全一樣，沒差別，稍微改一下代碼就好了。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define ll long long
using namespace std;
int dir[8][2]={{1,2},{-1,2},{2,1},{2,-1},{-2,1},{-2,-1},{1,-2},{-1,-2}};
struct matrix{
    int a[6][6];
    bool operator<(matrix x) const{
        for(int i=1;i<=5;++i)
            for(int j=1;j<=5;++j)
                if(x.a[i][j]!=a[i][j]) return x.a[i][j]<a[i][j];
        return 0;
    }
}st,f;
inline int h(matrix a)
{
    int tmp=0;
    for(int i=1;i<=5;++i)
        for(int j=1;j<=5;++j)
            if(a.a[i][j]!=st.a[i][j]) tmp++;
    return tmp;
}
struct node{
    matrix a;
    int step;
    bool operator<(node x) const{
        return x.step+h(x.a)<step+h(a);
    }
    node(){};
    node(matrix _a,int _step){a=_a,step=_step;}
};
priority_queue<node> q;
map<matrix,bool> mp;
int main()
{
    st.a[1][1]=1,st.a[1][2]=1,st.a[1][3]=1,st.a[1][4]=1,st.a[1][5]=1;
    st.a[2][1]=0,st.a[2][2]=1,st.a[2][3]=1,st.a[2][4]=1,st.a[2][5]=1;
    st.a[3][1]=0,st.a[3][2]=0,st.a[3][3]=-1,st.a[3][4]=1,st.a[3][5]=1;
    st.a[4][1]=0,st.a[4][2]=0,st.a[4][3]=0,st.a[4][4]=0,st.a[4][5]=1;
    st.a[5][1]=0,st.a[5][2]=0,st.a[5][3]=0,st.a[5][4]=0,st.a[5][5]=0;
    int T;
    scanf("%d",&T);
    while(T--){
        mp.clear();
        while(q.size()) q.pop();
        char c;
        for(int i=1;i<=5;++i)
            for(int j=1;j<=5;++j){
                scanf(" %c",&c);
                if(c=='*') f.a[i][j]=-1;
                else f.a[i][j]=c-'0';
            }
        bool flag=0;
        q.push(node(f,0));
        while(q.size()){
            node x=q.top();q.pop();
            if(flag) continue;
            if(x.step>15){
                printf("-1\n");
                flag=1;
            }
            if(!h(x.a)&&!flag){
                printf("%d\n",x.step);
                flag=1;
            }
            if(mp[x.a]) continue;
            mp[x.a]=1;
            int nx,ny;
            for(int i=1;i<=5;++i)
                for(int j=1;j<=5;++j)
                    if(x.a.a[i][j]==-1) nx=i,ny=j;
            for(int i=0;i<8;++i){
                int xx=nx+dir[i][0],yy=ny+dir[i][1];
                if(xx>=1&&xx<=5&&yy>=1&&yy<=5){
                    swap(x.a.a[xx][yy],x.a.a[nx][ny]);
                    q.push(node(x.a,x.step+1));
                    swap(x.a.a[xx][yy],x.a.a[nx][ny]);
                }
            }
        }
    }
    return 0;
}                

就是跑的比較慢啦。

轉載于:https://www.cnblogs.com/DarkValkyrie/p/11298282.html