A*

Acwing 算法提高课 A*

A*算法
利用估价函数来进行对搜索空间的优化
要求：答案保证有解(起点状态与目标状态需连通),否则会导致算法时间复杂度退化为O(mlogm),大于朴素bfs

算法思路：

 我们称起点到某一状态的距离为真实距离，称我们猜测的不一定正确的状态到终点的距离为估计距离
 该算法使用小根堆来维护每个状态的真实距离与估计距离之和
 并每次使用该属性最小的点来进行拓展，将拓展到的点入队，直到拓展到了终点，则此时得到的一定是最小距离
 注意：I.  我们设计的估计距离一定要小于等于实际的剩余距离
        II. 只有出队的终点是最小距离，其余出队的状态不一定
        III.由于某一状态可能被重复更新，所以A*不能进行判重

算法正确性证明:

我们令真实距离为g(),估计距离为f(),剩余路径总长为D(),当前我们得到路径为t,实际最优路径为u

$$假设我们得到的拓展到T时得到的距离(d_{t})不是最短路径(d_{u})$$ $$\therefore D_{t} = g_{t} + f_{t} > D_{u} = g_{u} + d_{剩余} \geqslant g_{u} + f_{u}$$ $$又\because 小根堆维护g() + f()$$ $$\therefore g(t) + f(t) \leqslant g(u) + f(u)$$ $$\therefore 矛盾,得证$$

原题:Acwing.179 八数码

回到本题,对于八数码问题使用A*算法需要解决两个问题
     I. 如何判断是否有解
         *对于奇数码问题有解的充要条件是把数码写成序列形态有逆序对的数量为偶数
     II.估价函数
         每次移动只令某个点向目标方向移动一格
         理想情况(点与点的路径不冲突)下,令每个点直接移向目标位置
         则有理想距离为所有点的(当前位置与目标位置的哈曼顿距离)之和
         这个距离即作为估价距离，易知其满足条件

#include <iostream>
#include <cstring>
#include <cstdio>
#include <unordered_map>
#include <queue>
#include <algorithm>
#define x first
#define y second

using namespace std;

const int N = 10;
typedef pair<int, string> PIS;

string st, ed = "12345678x", sq;
int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
string op = "ulrd";//option映射记录

int f(string state){// 求哈曼顿距离和
    int sum = 0;
    for(int i = 0; i < 8; i ++)
        if(state[i] != 'x'){
            int x = state[i] - '1';
            sum += abs(x / 3 - i / 3) + abs(x % 3 - i % 3);
        }
    return sum;    
}

string bfs(){
    if(ed == st) return "";
    
    priority_queue<PIS, vector<PIS>, greater<PIS>> q;
    unordered_map<string, int> dist;
    unordered_map<string, pair<char, string>> pre;
    
    q.push({f(st), st});
    dist[st] = 0;
    
    while(q.size())
    {
        string t = q.top().y;
        q.pop();
        
        if(t == ed) break;
        
        //找到x
        int x, y;
        for(int i = 0; i < 9; i ++)
            if(t[i] == 'x'){
                x = i / 3;
                y = i % 3;
            }
        //处理移动
        string source = t;
        for(int i = 0; i < 4; i ++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 0 || nx == 3 || ny < 0 || ny == 3) continue;
            t = source;
            swap(t[nx * 3 + ny], t[x * 3 + y]);
            if(dist.count(t) && dist[t] <= dist[source] + 1) continue;
            dist[t] = dist[source] + 1;
            pre[t] = {op[i], source};
            q.push({f(t) + dist[t], t});
        }
    }
    
    //这里也可以dfs
    string res = "";
    while(ed != st)
    {
        res += pre[ed].x;
        ed = pre[ed].y;
    }
    reverse(res.begin(), res.end());
    
    return res;
}

int main(){
    freopen("EightDigital.in", "r", stdin);
    freopen("EightDigital.out", "w", stdout);
    
   char c;
   for(int i = 0; i < 9; i ++){
       cin >> c;
       st += c;
       if(c != 'x')sq += c;
   }
   
   //求逆序对判解
   int cnt = 0;
   for(int i = 1; i < 9; i ++){
       for(int j = 0; j < i; j ++){
           if(sq[j] > sq[i]) cnt ++;
       }
   }
   
   if(cnt & 1) puts("unsolvable");
  else cout << bfs();
   
   return 0;
}

无解样例
1 2 3 4 5 6 8 7 x
即
1 2 3 
4 5 6
8 7 x