什么是A算法,A算法又叫启发式搜索,通过堆优化+估价函数对搜索进行优化的一种算法,运用于正权图(我只知道这个,负权图算法还没学QAQ).
通过启发函数可以让搜索复杂度大大降低.如下图:
图片说明
但是对于终点第一次出队并非一定是最小值,就比方说这个图,下面的第三个点,由于前面的估计函数都是0,所以我们肯定先出队的距离为4,而后才有2.
A算法的证明就类似dij算法,贪心想想就是了.
这就是A算法,是不是感觉也不是很难呢?
下面讲解两个题目吧~
题目描述&数据范围:
给定一张N个点（编号1,2…N），M条边的有向图，求从起点S到终点T的第K短路的长度，路径允许重复经过点或边。
注意： 每条最短路中至少要包含一条边。
输入格式
第一行包含两个整数N和M。
接下来M行，每行包含三个整数A,B和L，表示点A与点B之间存在有向边，且边长为L。
最后一行包含三个整数S,T和K，分别表示起点S，终点T和第K短路。
输出格式
输出占一行，包含一个整数，表示第K短路的长度，如果第K短路不存在，则输出“-1”。
数据范围
1≤S,T≤N≤1000,
0≤M≤105,
1≤K≤1000,
1≤L≤100
思路:建反图,跑个dij,再拿这些值当成每个点的估价值,从起点开始,跑出来的就是第一小

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
typedef pair<int,pi> pii;
#define x first
#define y second
const int N=1e3+5;
bool st[N];
int dis[N];
vector<pi>yu[N];
vector<pi>v[N];
void dij(int t)
{
    memset(dis,0x3f,sizeof dis);
    priority_queue<pi,vector<pi>,greater<pi>>q;
    dis[t]=0;
    q.push({0,t});
    while(q.size())
    {
        auto at=q.top();
        q.pop();
        if(st[at.y]) continue;
        st[at.y]=true;
        for(int i=0;i<yu[at.y].size();i++)
        {
            int j=yu[at.y][i].x;//下个点的坐标
            if(dis[j]>dis[at.y]+yu[at.y][i].y)
            {
                dis[j]=dis[at.y]+yu[at.y][i].y;
                q.push({dis[j],j});
            }
        }
    }
}

int A_s(int s,int t,int k)//只是一个优化而已
{
    //我们拿准确值当估价值.
    int cnt=0;
    priority_queue<pii,vector<pii>,greater<pii>>q;
    q.push({dis[s],{0,s}});
    while(q.size())
    {
        auto at=q.top();
        q.pop();
        if(at.y.y==t) 
        {
            cnt++;
            if(cnt==k) return at.y.x;
        }//出界条件
        for(int i=0;i<v[at.y.y].size();i++)
        {
            int j=v[at.y.y][i].x;
            int val=v[at.y.y][i].y;
            q.push({at.y.x+val+dis[j],{at.y.x+val,j}});
        }
    }
    return -1;
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        v[a].push_back({b,c});//正向存图
        yu[b].push_back({a,c});//反向跑dij
    }
    int s,t,k;
    scanf("%d%d%d",&s,&t,&k);
    if(s==t) k++;
    dij(t);
    cout<<A_s(s,t,k)<<endl;
    return 0;
}

八数码A解法
八数码的A是拿曼哈顿距离来当成估价函数的.首先判断下奇数码是否有解就是判断一下,假如逆序对%2==0,那么一定有解,否则就一定无解.
然后我们拿他们的曼哈顿距离当估价函数,进行扩展,用pre数组记录答案QAQ.一个bug找一天啊>.

#include <bits/stdc++.h>
using namespace std;

int f(string state)//计算曼哈顿距离作为辅助函数
{
    int res=0;
    for(int i=0;i<9;i++)
    {
        if(state[i]!='x')
        {
            int x=i/3,y=i%3;
            int ix=(state[i]-'1')/3,iy=(state[i]-'1')%3;
            res+=abs(x-ix)+abs(y-iy);   
        }
    }
    return res;
}

string A_star(string start)
{
    string end="12345678x";
    unordered_map<string,int>dis;//记录每个状态的最小移动步数.
    unordered_map<string,pair<string,char>>pre;//用于记录答案
    char op[]="uldr";
    int dx[4]={-1,0,1,0};int dy[4]={0,-1,0,1};//四个方向 上左下右
    priority_queue<pair<int,string>,vector<pair<int,string>>,greater<>>q;//优先曼哈顿距离,然后存图
    q.push({f(start),start});
    dis[start]=0;
    while(q.size())
    {
        auto t=q.top();
        q.pop();
        string state=t.second;
        int distance=dis[state];
        int x,y;
        if(state==end) break;
        for(int i=0;i<9;i++)
        {
             if(state[i]=='x') {x=i/3,y=i%3;break;}
        }//寻找x所在位子
        string source=state;
        for(int i=0;i<4;i++)
        {
            int a,b;
            a=x+dx[i],b=y+dy[i];
            if(a>=0&&a<3&&b>=0&&b<3)//判断是否越界
            {//假如没越界
                swap(state[3*x+y],state[3*a+b]);
                if(!dis.count(state)||dis[state]>distance+1)
                {
                    dis[state]=distance+1;
                    pre[state]={source,op[i]};
                    q.push({dis[state]+f(state),state});
                }
                swap(state[3*x+y],state[3*a+b]);
            }
        }
    }
    //记录答案
    string ans;
    while(end!=start)
    {
        ans=pre[end].second+ans;
        end=pre[end].first;
    }
    return ans;
}

int main()
{
    string s,c,b;
    while(cin>>c) 
    {
        s+=c;
        if(c!="x") b+=c;
    }
    int len=s.size();int cnt=0;
    for(int i=0;i<len;i++)
    {
        for(int j=i+1;j<len;j++)
        {
            if(b[i]>b[j]) cnt++;
        }
    }
    if(cnt&1) puts("unsolvable");
    else
    {
        cout<<A_star(s)<<endl;
    }
    return 0;
}