題目鏈接：點擊查看

題目大意：給出一個有向圖，求第k短路

題目分析：偷學了一波A*，本來以為是多難的算法，其實就是bfs+優先隊列的升級版，之前看的那些博客寫的都太深奧了，以至于看了一半啥都沒看懂然后就被嚇跑了，這里放一波zx學長PPT上的描述，我感覺簡潔精煉，幾句話就把這個算法的核心描述清楚了：

• A * 算法的實現，A * =優先隊列BFS+估價函數。
• 回顧優先隊列bfs：優先隊列BFS算法維護了一個優先隊列，不斷從堆中取出當前代價最小的狀態進行擴展。每個狀態第一次從堆中取出時，就得到了從初態到該狀態的最小代價。
• 局限：如果給定一個目標狀態，需要求出從初態到目標狀態的最小代價，那么優先隊列BFS這個優先策略是不完善的。一個狀態當前代價小，只能說明從起始狀態到該狀態代價小，而在未來的搜索中從該狀態到目標狀態的花費可能會很大。導致有一部分很晚才能得到擴展。
• 為了提高搜索效率，我們很自然的想到，可以對未來可能產生的代價進行預估。
• 詳細的講：我們設計一個估價函數，以任意狀態為輸入，計算出從該狀態到目標狀態所需代價的估計值。在搜索中，仍然維護一個堆，不斷從堆中取出 當前代價+未來估價 最小的狀態進行擴展
• 為了保證第一次從堆中取出目標狀態時得到的就是最優解，我們設計的估價函數需要滿足一個基本準則：估價函數的估值不能大于未來實際代價，估價比實際代價更優。
• 這種帶有估價函數的優先隊列BFS就稱為A * 算法。只要保證對于任意狀態state，都有f（state）≤g（state），A * 算法就一定能在目標狀態第一次從堆中被取出時得到最優解，并且在搜索過程中每個狀態只需要被擴展一次（之后再被取出就可以直接忽略）。估價f（state）越準確，越接近g（state），A * 算法的效率就越高。如果估價始終為0，就等價于普通優先隊列BFS。
• A * 算法提高搜索效率的關鍵，就在于能否設計出一個優秀的估價函數。估價函數在滿足上述設計準則的前提下，含應該盡可能反映未來實際代價的變化趨勢和相對大小關系，這樣搜索才會較快的逼近最優解
• 估價函數的設計準則：
• 估值f（state）≤未來實際代價g（state）

那么再回到這個題目上面，我們只需要設計出估價函數即可，這個題目的權值是距離，當我們到達一個點后，利用bfs的狀態轉移可以很容易的知道從起點到當前點的距離，那怎么知道當前點到終點的距離呢？我們可以一開始從終點跑一遍迪杰斯特拉或者spfa，這樣就能輕松表達出估價函數了，有了估價函數后，我們在優先隊列+bfs的基礎上，更改排序函數的機制為估價函數，然后給我們的bfs函數改個名字，就變成A*算法了

有一個坑點需要注意一下，當終點和起點重合的時候，我們需要讓k++，以避免出現讓起點直接到達終點的現象發生

代碼，模板題：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e3+100;int d[N];bool vis[N];struct Node {int to,w;Node(int TO,int W){to=TO;w=W;}Node(){}bool operator<(const Node& a)const{return w+d[to]>a.w+d[a.to];} };vector<Node>node1[N],node2[N];//1:正向邊 2:反向邊 void spfa(int x) {memset(vis,false,sizeof(vis));memset(d,inf,sizeof(d));queue<int>q;q.push(x);d[x]=0;vis[x]=true;while(!q.empty()){int from=q.front();q.pop();vis[from]=false;for(int i=0;i<node2[from].size();i++){int to=node2[from][i].to;int w=node2[from][i].w;if(d[to]>d[from]+w){d[to]=d[from]+w;if(!vis[to]){vis[to]=true;q.push(to);}}}} }int A_star(int start,int end,int k) {priority_queue<Node>q;q.push(Node(start,0));while(!q.empty()){Node cur=q.top();q.pop();if(cur.to==end){k--;if(!k)return cur.w;}for(int i=0;i<node1[cur.to].size();i++){int to=node1[cur.to][i].to;int w=node1[cur.to][i].w;q.push(Node(to,cur.w+w));}}return -1; }int main() { // freopen("input.txt","r",stdin);int n,m;while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++){node1[i].clear();node2[i].clear();}while(m--){int u,v,w;scanf("%d%d%d",&u,&v,&w);node1[u].push_back(Node(v,w));node2[v].push_back(Node(u,w));}int s,e,k;scanf("%d%d%d",&s,&e,&k);spfa(e);if(d[s]==inf){printf("-1\n");continue;}if(s==e)//特判一下，坑 k++;printf("%d\n",A_star(s,e,k));}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 2449 Remmarguts' Date(第k短路:spfa+A*)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。