poj2249
A*算法
來自百度百科
A* 算法，A* （A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法，也是解決許多搜索問題的有效算法。算法中的距離估算值與實(shí)際值越接近，最終搜索速度越快。
公式表示為： ,
其中， 是從初始狀態(tài)經(jīng)由狀態(tài)
到目標(biāo)狀態(tài)的代價(jià)估計(jì)，
是在狀態(tài)空間中從初始狀態(tài)到狀態(tài)
的實(shí)際代價(jià)，
是從狀態(tài)
到目標(biāo)狀態(tài)的最佳路徑的估計(jì)代價(jià)。
（對(duì)于路徑搜索問題，狀態(tài)就是圖中的節(jié)點(diǎn)，代價(jià)就是距離）
的選取:
保證找到最短路徑（最優(yōu)解的）條件，關(guān)鍵在于估價(jià)函數(shù)的選取（或者說
的選?。?/p>
我們以表達(dá)狀態(tài)
到目標(biāo)狀態(tài)的距離，那么
的選取大致有如下三種情況：
- 如果
到目標(biāo)狀態(tài)的實(shí)際距離，這種情況下，搜索的點(diǎn)數(shù)多，搜索范圍大，效率低。但能得到最優(yōu)解。
- 如果
，即距離估計(jì)
等于最短距離，那么搜索將嚴(yán)格沿著最短路徑進(jìn)行， 此時(shí)的搜索效率是最高的。
- 如果
，搜索的點(diǎn)數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解。
所以取
模板
求一個(gè)圖中從源點(diǎn) 到終點(diǎn)
的第
短路
定義數(shù)組d[n],表示從 到
的距離，以
為源點(diǎn)做一次最短路可以得到每個(gè)點(diǎn)到
的距離，所以要存一個(gè)反向圖，用來預(yù)處理
d[n]，直接以d[n]當(dāng)作
有了d[n]之后，維護(hù)一個(gè)優(yōu)先隊(duì)列，隊(duì)列中的每個(gè)節(jié)點(diǎn)都存放{v,sum},v表示當(dāng)前點(diǎn)，sum表示到達(dá)點(diǎn)v一共走了多少距離。優(yōu)先隊(duì)列按照公式確定優(yōu)先級(jí)，其中
對(duì)應(yīng)
sum,對(duì)應(yīng)
d[v]，通過優(yōu)先隊(duì)列一次次的擴(kuò)展，如果第此取到
，那么此時(shí)的
sum就是到
的
短路。
其實(shí)就是s-v的距離加上v-t的距離，這就是一條路，我們可以知道每條路長(zhǎng)度 ，所以可以找到第k短的那一條，每次取到t，就是找到了一個(gè)比上次 次短 的路.
例題 POJ2249
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
#define MAXN 100009
int n,m,s,t,k;
int d[MAXN];// 每個(gè)點(diǎn)到t的距離
const int inf = 0x3f3f3f3f;
struct edge{
int to,len,next;
}e1[MAXN], e2[MAXN];
struct node{//優(yōu)先隊(duì)列中的節(jié)點(diǎn)
int v,sum;
node(int v,int w):v(v),sum(w){}
bool operator < (const node & o)const{
return this->sum+d[this->v] > o.sum+d[o.v]; // 這里就是估值小的放前面，f(v) = g(v) + h(v)，sum就是g(v),d[]做h(v)
}
};
int head1[MAXN], head2[MAXN] , js1,js2; //分別存 原圖，反向圖
bool vst[MAXN];
void init(){
js1 = 0;js2 = 0;
memset(head1,-1,sizeof(head1));
memset(head2,-1,sizeof(head2));
}
void add1(int a, int b, int len){//建原圖
e1[js1].to = b;
e1[js1].len = len;
e1[js1].next = head1[a];
head1[a] = js1;
js1++;
}
void add2(int a, int b, int len){//建反向圖
e2[js2].to = b;
e2[js2].len = len;
e2[js2].next = head2[a];
head2[a] = js2;
js2++;
}
void spfa(){//用反向圖初始化d[]
queue<int> que;
que.push(t);
memset(vst,0,sizeof(vst));
memset(d,inf,sizeof(d));
d[t]=0;
vst[t]=1;
while(!que.empty()){
int u=que.front(); que.pop();
vst[u]=0;
for(int i=head2[u]; i!=-1; i=e2[i].next){
int v=e2[i].to;
int w=e2[i].len;
if(d[u]+w < d[v]){
d[v] = d[u]+w;
//cout<<d[v]<<endl;
if(!vst[v]){
vst[v]=1;
que.push(v);
}
}
}
}
}
int astar(){//A* 算法
if(d[s]==inf) return -1;//說明沒有s到t的通路
priority_queue<node> que;
que.push(node(s,0)); //從s出發(fā)
int cnt=0; //記錄到達(dá)了多少次
while(!que.empty()){
node u = que.top(); que.pop();
if(u.v == t){
cnt++;
if(cnt == k)return u.sum;
}
for(int i=head1[u.v]; i!=-1; i=e1[i].next){
int v=e1[i].to;
int w=e1[i].len;
que.push( node(v, u.sum+w) );
}
}
return -1; //不存在k短路
}
int main(){
scanf("%d %d",&n, &m);
init();
for(int i=0;i<m;i++){
int a,b,len;
scanf("%d %d %d",&a,&b,&len);
add1(a,b,len);
add2(b,a,len); //反向圖
}
scanf("%d %d %d",&s,&t,&k);
if(s==t)k++; //poj2449這道題中，如果st重合，那么第一短結(jié)果肯定是0，原地不動(dòng)不當(dāng)作一條路看
spfa();//初始化估計(jì)值 d[]
int ac = astar();
printf("%d\n",ac);
return 0;
}
