第k短路和A*-白红宇

第k短路和A*

阅读量：6816 次

发布时间：2019-06-26

本文共 2809 字，大约阅读时间需要 9 分钟。

　　第一次接触A*，感觉好神奇。。

启发函数：f(x) = g(x) + h(x);

比如初始状态为s，目标状态为t

g(x)表示从s到达状态x所消耗的代价

h(x)表示从x到达t所估算的代价

g'(x)表示s -> x可能出现的最小代价

h'(x)表示x -> t可能出现的最小代价

g(x) >= g'(x)；h(x) <= h'(x)；

好吧，上面全是概念。。。

当g(x) 为0时，A*就成了bfs，当h(x)为0时，A*就成了dfs。所以。。。启发函数的选择直接影响到A*算法的性能。

大概的说说我对A*算法运算过程的理解吧：

基本就是bfs形式，不过要用到优先队列。

如在求第k短路问题上：f(x)越小优先级越高。dis[x]表示x到t的最短路，这里可以用spfa预处理出来（把图逆向，求t到每个点的距离就ok了）。bfs过程中每次更新f(x)和g(x)

f(x) = [pre]g(x) + curent.value + dis[curnet.node];

[new]g*(x) = [pre]g(x) + curent.value.

比如：

模板如下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #define CL(arr, val) memset(arr, val, sizeof(arr))#define REP(i, n) for((i) = 0; (i) < (n); ++(i))#define FOR(i, l, h) for((i) = (l); (i) <= (h); ++(i))#define FORD(i, h, l) for((i) = (h); (i) >= (l); --(i))#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) x < y ? x : y#define Max(x, y) x < y ? y : x#define E(x) (1 << (x))const double eps = 1e-4;typedef long long LL;using namespace std;const int N = 1024;const int M = 100010;const int inf = ~0u>>2;struct edg { int to; int val; int next; edg() {} edg(int a, int b, int c): to(a), val(b), next(c) {}} g[M<<1], rg[M<<1];struct node { int f, g, v; node() {} node(int a, int b, int c) : f(a), g(b), v(c) {} bool operator < (const node& x) const { return x.f < f; }};int inq[N];int head[N];int rhead[N];int dis[N];int t, k;void init() { CL(head, -1); CL(rhead, -1); CL(inq, 0); t = 0; for(int i = 0; i < N; ++i) dis[i] = inf;}void add(int u, int v, int w) { g[t] = edg(v, w, head[u]); rg[t] = edg(u, w, rhead[v]); head[u] = t; rhead[v] = t++;}void spfa(int ed) { int i, u, v, w; queue
                 
                   q; q.push(ed); inq[ed] = 1; dis[ed] = 0; while(!q.empty()) { u = q.front(); for(i = rhead[u]; i != -1; i = rg[i].next) { v = rg[i].to; w = rg[i].val; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if(!inq[v]) { inq[v] = 1; q.push(v);} } } inq[u] = 0; q.pop(); }}int A_star(int st, int ed) { priority_queue
                  
                    Q; if(dis[st] == inf) return -1; int v, w; CL(inq, 0); Q.push(node(dis[st], 0, st)); while(!Q.empty()) { node cur = Q.top(); Q.pop(); inq[cur.v] ++; if(inq[ed] == k) return cur.f; if(inq[cur.v] > k) continue; for(int i = head[cur.v]; i != -1; i = g[i].next) { v = g[i].to; w = g[i].val; node New(dis[v] + cur.g + w, cur.g + w, v); Q.push(New); } } return -1;}int main() { //freopen("data.in", "r", stdin); int n, m, i; int u, v, w; int st, ed; init(); scanf("%d%d", &n, &m); for(i = 0; i < m; ++i) { scanf("%d%d%d", &u, &v, &w); add(u, v, w); } scanf("%d%d%d", &st, &ed, &k); spfa(ed); if(st == ed) k++; printf("%d\n", A_star(st, ed)); return 0;}