lyd读书笔记 宽搜(3)Astar

A*

A*的含义

Aster是个好游戏

考虑带有优先队列的宽搜。如果只给定目标状态,那么就意味着我们必须枚举大多数的分支。但是这样的问题是,如果某一个分支的未来优势很大但现在优势不明显,我们会优先搜索现在优势很大但未来不一定有优势的分支。这样搜索量就变大了。

但是如果我们能找到一种做法使得预估出来一个代价,然后从堆中取出预估代价+当前代价最小的,那么这样的搜索量会少很多。

显然,我们的原则是对于状态$s$,预估代价$f(s)\leq$实际代价$g(s)$恒成立。否则搜索量就会变大甚至出现结果错误。

当$f(s)$越接近$g(s)$,效率就越高。而A*的关键就在于估价函数的设置。

K短路

我们首先考虑一下,如果不加入估价函数而进行普通的BFS应该怎么做。我们维护一个二元组$(x, dis)$,表示第$x$个点的距离,然后我们进行扩展,扔进去$(x, dis + d_{x, nxt})$,这样的话当终点被取出k次时得到的就是k短路。

考虑A*。我们可以首先求解各个节点到终点的最短距离dis,记为f(x),显然有$f(x) \leq g(x)$恒成立。然后我们就可以愉快的重复上面的操作啦!

实现上的话,首先我们以终点为起点跑一遍反向最短路,求出dis。之后开一个小根堆瞎jb搞一波…然后就过了。

不过问题还是有的,如果一个顶点出现K次以上那么该顶点就可以不进入堆中了。原因我们可以考虑反证法,不妨设前K短路都经过该点,那么如果该点进入第k + 1次路一定是某个环的又一次重复,因而这种情况一定不是作为K短路而做出贡献的。

POJ2449

模板题。

注意一件事,因为是有向图,所以我们应该先建一波反向边求dis。

另外对于起点和终点重合的情况要++K。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

/*Part of storage edges*/
struct line{
int to, va;
line(){};
line(int a, int b) {
to = a, va = b;
}
};

vector<line> road[1003];
vector<line> reverse_road[1003];

inline void add_edge(int fr, int to, int va) {
road[fr].push_back(line(to, va));
reverse_road[to].push_back(line(fr, va));
}

/*Get the shortest path with SPFA algorithm*/

int dis[1003];

void SPFA1(int st, int ed) {
memset(dis, 0x3f, sizeof dis);
dis[st] = 0;
queue<int> q;
q.push(st);
while(!q.empty()) {
int now = q.front();
q.pop();
for(int i = 0; i < reverse_road[now].size(); ++i) {
int nxt = reverse_road[now][i].to, cost = reverse_road[now][i].va;
if(dis[nxt] > dis[now] + cost) {
dis[nxt] = dis[now] + cost;
q.push(nxt);
}
}
}
}

/*A* technique*/

struct node{
int id, va;
node(){};
node(int a, int b) {
id = a, va = b;
}
bool operator < (const node& b) const {
return va + dis[id] > b.va + dis[b.id];
}
};

int cnt[1003]; //某个点被取出的次数
int K;

int SPFA2(int st, int ed) {
if(st == ed) ++K;
priority_queue<node> pq;
pq.push(node(st, 0));
while(!pq.empty()) {
node tmp = pq.top();
pq.pop();
int w = tmp.id, c = tmp.va;
++cnt[w];
if(w == ed && cnt[w] == K)
return c;
if(cnt[w] > K) continue;
for(int i = 0; i < road[w].size(); ++i) {
pq.push(node(road[w][i].to, road[w][i].va + c));
}
}
return -1;
}

/*solve*/

int main() {
int n, m;
while(cin>>n>>m) {
int ta, tb, tv;
for(int i = 1; i <= m; ++i) {
scanf("%d%d%d", &ta, &tb, &tv);
add_edge(ta, tb, tv);
}
int s, t;
scanf("%d%d%d", &s, &t, &K);
SPFA1(t, s);
cout<<SPFA2(s, t)<<endl;
}
}

luogu2483 魔法猪学院

基本上没什么变化,注意$K = E / dist[1]$,因为最多也只有这么多条。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

/*Part of storage edges*/
struct line{
int to;
double va;
line(){};
line(int a, double b) {
to = a, va = b;
}
};

vector<line> road[5003];
vector<line> reverse_road[5003];

inline void add_edge(int fr, int to, double va) {
road[fr].push_back(line(to, va));
reverse_road[to].push_back(line(fr, va));
}

/*Get the shortest path with SPFA algorithm*/

double dis[5003];

void SPFA1(int st, int ed) {
for(int i = 1; i <= st; ++i) dis[i] = 0x3fffff;
dis[st] = 0;
queue<int> q;
q.push(st);
while(!q.empty()) {
int now = q.front();
q.pop();
for(int i = 0; i < reverse_road[now].size(); ++i) {
int nxt = reverse_road[now][i].to;
double cost = reverse_road[now][i].va;
if(dis[nxt] > dis[now] + cost) {
dis[nxt] = dis[now] + cost;
q.push(nxt);
}
}
}
}

/*A* technique*/

struct node{
int id;double va;
node(){};
node(int a, double b) {
id = a, va = b;
}
bool operator < (const node& b) const {
return va + dis[id] > b.va + dis[b.id];
}
};

int cnt[5003]; //某个点被取出的次数
int K;
double E;

int SPFA2(int st, int ed) {
priority_queue<node> pq;
int ti = 0; double ans = 0;
pq.push(node(st, 0));
while(!pq.empty()) {
node tmp = pq.top();
pq.pop();
int w = tmp.id; double c = tmp.va;
if(c > E) continue;
++cnt[w];
if(w == ed) {
if(ans + c <= E) ans += c, ti += 1;
else return ti;
}
for(int i = 0; i < road[w].size(); ++i) {
//if(road[w][i].va + c <= E)
pq.push(node(road[w][i].to, road[w][i].va + c));
}
}
return ti;
}

int main() {
int n, m;
cin>>n>>m>>E;
int ta, tb; double tv;
for(int i = 1; i <= m; ++i) {
scanf("%d%d%lf", &ta, &tb, &tv);
add_edge(ta, tb, tv);
}
SPFA1(n, 1);
K = (int)(E / dis[1]);
cout<<SPFA2(1, n)<<endl;
}
Author

LittleRewriter

Posted on

2018-02-27

Updated on

2021-07-28

Licensed under

Comments