【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;
}