A*算法： A*，啟發式搜索，是一種較為有效的搜索方法。 我們在搜索的時候，很多時候在當前狀態，已經不是最優解了，但是我們卻繼續求解；這個就是暴力搜索浪費時間的原因。 我們在有些時候，往往可以根據一些信息推斷出繼續搜索是一種劣解。 所以如果能夠判斷出來的話，就可以不繼續了，以達到節省運行時間的目的。 估價函數： 為了提高搜索效率，我們可以對未來可能產生的代價進行預估。我們設計一個估價函數，以任意狀態輸入，計算出從該狀態到目標狀態所需代價的估計值。 在搜索時，我們總沿著當前代價+未來估價最小的狀態進行搜索。估價函數需要滿足：設當前狀態state到目標函數所需代價的估計值為f(state)設在未來的搜索中，實際求出的從當前狀態state到目標狀態的最小代價為g(state)對于任意的state，應該有f(state)<=g(state) 也就是說，估價函數的估值不能大于未來實際代價，估價比實際代價更優。第K短路： 根據估價函數的設計準則，在第K短路中從x到T的估計距離f(x)應該不大于第K短路中從x到T的實際距離g(x)，于是，我們可以把估價函數f(x)定為從x到T的最短路徑長度，這樣不但能保證f(x)<=g(x)，還能順應g(x)的實際變化趨勢。 實現過程： 1.預處理f(x)，在反向圖上以T為起點求到每個點的最短路 2.定義堆，維護{p,g,h}，p是某一個點，g是估價，h是實際，那么g+h更小的點p會優先訪問 3.取出堆頂元素u擴展，如果節點v被取出的次數尚未達到k，就把新的{v,g,h+length(u,v)}插入堆中 4.重復第2-3步，直到第K次取出終點T，此時走過的路徑長度就是第K短路因為估價函數的作用，圖中很多節點訪問次數遠小于K

我們定義一個評估值f(x)=g(x)+h(x)（例如求k短路中g(x)表示已經走了多遠，h(x)表示從這個點到終點的最短路）f(x)越小就意味著越好咯，我們每次都去尋找最小的f(x)來進行操作，那不就很妙了

那k短路怎么求呢?
我們就先求出每個點到終點的最短路——把圖反過來..從t做最短路【捂臉】 這樣就求出來了h(x)?
然后就..每次做一個點，然后…求一個f(x)，扔進優先隊列里..?
最后t出現k次也就可以了

模板：

#include<bits/stdc++.h> using namespace std;#define ee exp(1) #define pi acos(-1) #define mod 1000000007 #define inf 0x3f3f3f3f #define ll long long #define ull unsigned long long #define mem(a,b) memset(a,b,sizeof(a)) int gcd(int a,int b){return b?gcd(b,a%b):a;}const int maxn=1e6+5; int n,m,s,t,k,r,cnt,p1,p2,head1[maxn],head2[maxn],vis[maxn]; ll d[maxn]; struct node{int to,w,next; }e1[maxn],e2[maxn]; struct qnode{int v;ll w;qnode(int v,ll w):v(v),w(w) {}friend bool operator < (qnode x,qnode y){return x.w+d[x.v]>y.w+d[y.v];} }; void add1(int u,int v,int w) {e1[++p1].to=v;e1[p1].w=w;e1[p1].next=head1[u];head1[u]=p1; } void add2(int u,int v,int w) {e2[++p2].to=v;e2[p2].w=w;e2[p2].next=head2[u];head2[u]=p2; } void spfa()//反向圖，t到其他點的距離 {queue<int> q;q.push(t);for(int i=1; i<=n; i++)d[i]=inf;mem(vis,0);d[t]=0;vis[t]=1;while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=head1[u]; i; i=e1[i].next){int v=e1[i].to;int w=e1[i].w;if(d[v]>d[u]+w){d[v]=d[u]+w;if(!vis[v]){vis[v]=1;q.push(v);}}}} }ll astar()//A*算法 {if(d[s]==inf)return -1;priority_queue<qnode> pe;pe.push(qnode(s,0));cnt=0;while(!pe.empty()){qnode u=pe.top();pe.pop();if(u.v==t){cnt++;if(cnt==k)return u.w;}for(int i=head2[u.v]; i; i=e2[i].next){int v=e2[i].to;pe.push(qnode(v,u.w+e2[i].w));}}return -1; }int main() {while(~scanf("%d%d",&n,&m)){mem(head1,0);p1=0;mem(head2,0);p2=0;scanf("%d%d%d%d",&s,&t,&k,&r);while(m--){int u,v,w;scanf("%d%d%d",&u,&v,&w);add1(v,u,w);//反向圖 add2(u,v,w);}spfa();ll ans=astar();if(ans==-1||ans>r)puts("Whitesnake!");else puts("yareyaredawa");}return 0; }

?

總結

以上是生活随笔為你收集整理的第k短路 (A*算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

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