【ALGO】A* algorithm Notes

Navigator

• A* Search
• Demo: 雙向BFS
• • 解析
  • Code
• Demo: A*
• • 思路
  • Code

A* Search

An extension to the

Dijkstra

algorithm

A*: f(n)=g(n)+h(n)
Dijkstra: f(n)=g(n)
           

g(n)

is the cost from start to current node

h(n)

is the established cost from current node to target:

Manhattan distance

(L1),

Euclidean distance

(L2)

h ( x ) < = d ( x , y ) + h ( y ) h(x)<=d(x, y)+h(y) h(x)<=d(x,y)+h(y)

Optimal if

h(n)

is admissible, Complete (always find the path if exists)

Time Complexity: O ( ∣ E ∣ log ⁡ ∣ V ∣ ) \mathcal{O}(|E|\log|V|) O(∣E∣log∣V∣)

Space Complexity: O ( ∣ V ∣ ) \mathcal{O}(|V|) O(∣V∣)

pq.push(s, f(s), g(s));
while pq:
	node, _, cost = pq.pop();
	if node==t: return cost
	for v in ne(node):
		pq.push((v, f(v), g(v)));
return NOT_FOUND;
           

Demo: 雙向BFS

ACW 190. 字元串變換

解析

将變換規則進行建圖, 将可行的變換規則之間連接配接一條邊，如果從一個點開始搜尋，那麼搜尋空間将會變得異常龐大，考慮進行雙向搜尋，當搜尋路徑相遇時，即得到可行解，可以降低搜尋空間. 雙向BFS一般應用于求解最少步數的問題.

建立兩個隊列

qa

和

qb

分别存儲從起點和終點開始搜尋的路徑, 隻有當

qa.size() && qb.size()

滿足的情況下才進行搜尋, 否則說明起點和重點之間不連通.

算法擴充時，每次優先選擇隊列深度較短的隊列進行擴充操作

Code

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<unordered_map>

using namespace std;
const int N=6;
string a[N], b[N];
string A, B;
int n=0;

int extend(queue<string> &q, unordered_map<string, int>& ma, unordered_map<string, int>& mb, string a[], string b[]){
    string t=q.front(); q.pop();
    for(int i=0; i<t.size(); ++i){
        for(int j=0; j<n; ++j){
            if(t.substr(i, a[j].size())==a[j]){
                string st=t.substr(0, i)+b[j]+t.substr(i+a[j].size());
                if(mb.count(st)) return ma[t]+1+mb[st];
                if(!ma.count(st)) {ma[st]=ma[t]+1; q.push(st);}
            }
        }
    }
    return -1;
}

int bfs(){
    if(A!=B){
        queue<string> qa, qb;
        qa.push(A), qb.push(B);
        unordered_map<string, int> ma, mb;
        ma[A]=mb[B]=0;
        while(qa.size() && qb.size()){
            int t;
            if(qa.size()<=qb.size()) t=extend(qa, ma, mb, a, b);
            else t=extend(qb, mb, ma, b, a);
            if(0<=t && t<=10) return t;
        }
        return -1;
    }
    return 0;
}


int main(){
    cin>>A>>B;
    while(cin>>a[n]>>b[n]) ++n;
    int ans=bfs();
    if(ans==-1) cout<<"NO ANSWER!";
    else cout<<ans<<endl;
    return 0;
}
           

Demo: A*

ACW 179. 八數位

思路

隊列采用雙關鍵字排序：從起點到目前點的

真實距離

以及從起點到目前點的

估計距離

.

A*

算法需要滿足的條件：

估價距離<=真實距離

，當

估價距離=真實距離

時，

A*

算法會退化為

Dijkstra

算法.

估價函數的設計：目前狀态中每個數與其目标位置的曼哈頓距離之和. 是否存在解的判定，展開後計算逆序對的數量需要為偶數（每次交換位置隻會消除偶數個逆序對）

Code

#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<queue>

#define fi first
#define se second

using namespace std;

typedef pair<int, string> PIS;

int dir[4][2]={{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int f(string state){
    int ans=0;
    for(int i=0; i<state.size(); ++i){
        if(state[i]!='x'){
            int t=state[i]-'1';
            ans+=abs(i/3-t/3)+abs(i%3-t%3);
        }
    }
    return ans;
}

string bfs(string start){
    string end="12345678x";
    char op[] = "urdl";
    unordered_map<string, int> dist;
    unordered_map<string, pair<char, string>> prev;
    priority_queue<PIS, vector<PIS>, greater<PIS>> heap;
    
    dist[start]=0;
    heap.push({f(start), start}); // 估價函數-狀态 pair
    while(heap.size()){
        auto t = heap.top(); heap.pop();
        string state = t.se;
        if(state==end) break;
        
        int x, y;
        for(int i=0; i<9; ++i){
            if(state[i]=='x'){x=i/3; y=i%3; break;}
        }
        
        string source = state; // 儲存擴充前的狀态
        for(int i=0; i<4; ++i){
            int nx=x+dir[i][0], ny=y+dir[i][1];
            if(0<=nx && nx<3 && 0<=ny && ny<3){
                state = source;
                swap(state[x*3+y], state[nx*3+ny]);
                if(!dist.count(state) || dist[state]>dist[source]+1){
                    dist[state]=dist[source]+1;
                    prev[state] = {op[i], source};
                    heap.push({dist[state]+f(state), state});
                }
            }
        }
    }
    
    string ans;
    while(end!=start){ans+=prev[end].fi; end=prev[end].se;}
    reverse(ans.begin(), ans.end());
    return ans;
}

int main(){
    string start, seq;
    char c;
    while(cin>>c){
        start+=c;
        if(c!='x') seq+=c;
    }
    int cnt=0;
    for(int i=0; i<8; ++i)
        for(int j=i; j<8; ++j)
            if(seq[i]>seq[j]) ++cnt;
            
    if(cnt & 0x01) puts("unsolvable");
    else cout<<bfs(start)<<endl;
    
    return 0;
}