A*算法

基本介绍

把Dijkstra算法（靠近初始点的结点）和BFS算法（靠近目标点的结点）的信息块结合起来。在讨论A*的标准术语中，g(n)表示从初始结点到任意结点n的代价，h(n)表示从结点n到目标点的启发式评估代价（heuristic estimated cost）。

当从初始点向目标点移动时，A*权衡这两者。每次进行主循环时，它检查f(n)最小的结点n，其中$f(n) = g(n) + h(n)$。

A*主要作为寻路算法作用在游戏上。

实现方式

到这里，学长给我们上的课就到此结束了。

说实话，还是挺感谢学长们的，讲了好多东西啊。

还需要继续去掌握和巩固。

但是这个A*是真的难懂。

用我的理解来说，就是正向的一个Dijkstra与反向的BFS（最佳优先搜索）结合，用f(n)作为优先级来判断。

这个BFS存在一个启发式函数，这个启发式函数就是从节点n开始到目标节点的最小值。

这个算法网上没啥题，也没啥教程，听学长讲了一遍。

说实话，还是相当懵。

这里就贴一个详解吧。

A*。

典型例题

POJ-2449 Remmarguts’ Date

题目大意

给你一个n个节点，m条边的图，给你起点s，和终点t，求第k短路。

解题思路

网上说貌似可以用spfa，我用的A*。

先反向跑一遍Dijkstra，得出距离，也就是$h(n)$。

然后以$f(n)$为优先级跑一遍Dijkstra。

应该算是典型A*模板题。

完整代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

const int N = 1010, M = 1e5 + 5, INF = 1e9;
int cnt1, cnt2, head1[N], head2[N], vis[N], dis[N], n, k;
struct {
	int to, val, next;
}Map1[M],Map2[M];
struct node{
	int u, c;
	node(int a = 0,int b = 0):u(a),c(b){}
	bool operator <(const node& a) const{
		return c > a.c;
	}
};
struct heap{
	int g, h, num;
	heap(int a = 0,int b = 0,int c = 0):g(a),h(b),num(c){}
	bool operator <(const heap& a) const{
		return (g + h) > (a.g + a.h);
	}
};

void build1(int u,int v,int val) {
	Map1[++cnt1].to = v, Map1[cnt1].val = val;
	Map1[cnt1].next = head1[u], head1[u] = cnt1;
}

void build2(int u, int v, int val) {
	Map2[++cnt2].to = v, Map2[cnt2].val = val;
	Map2[cnt2].next = head2[u], head2[u] = cnt2;
}

void Dijkstra(int s) {
	memset(vis, 0, sizeof(vis));
	for (int i = 1; i <= n; i++) dis[i] = INF;
	dis[s] = 0;
	priority_queue<node>q2;
	q2.push(node(s, 0));
	node t;
	while (!q2.empty()) {
		t = q2.top();
		q2.pop();
		int u = t.u;
		if (vis[u])	continue;
		vis[u] = 1;
		for (int i = head2[u]; ~i; i = Map2[i].next) {
			int x = Map2[i].to;
			int c = Map2[i].val;
			if (!vis[x]&&dis[x] > dis[u] + c)
				dis[x] = dis[u] + c, q2.push(node(x, dis[x]));
		}
	}
}

void Astar(int s,int e) {
	Dijkstra(e);
	priority_queue<heap>q1;
	q1.push(heap(0, dis[s], s));
	heap t;
	int c = 0;
	while (!q1.empty()) {
		t = q1.top();
		q1.pop();
		if (t.num == e) {
			c++;
			if (c >= k) {
				cout << t.g << endl;
				return;
			}
		}
		for (int i = head1[t.num]; ~i; i = Map1[i].next) {
			int x = Map1[i].to;
			int c = Map1[i].val;
			q1.push(heap(t.g + c, dis[x], x));
		}
	}
	cout << -1 << endl;
}

int main() {
	int m;
	cin >> n >> m;
	memset(head1, -1, sizeof(head1));
	memset(head2, -1, sizeof(head2));
	cnt1 = cnt2 = 0;
	for (int i = 1; i <= m; i++) {
		int l, r, c;
		cin >> l >> r >> c;
		build1(l, r, c),build2(r, l, c);
	}
	int s, t;
	cin >> s >> t >> k;
	if (s == t)	k++;
	Astar(s, t);
}