$\text{A*}$

一种启发式搜索

和暴搜的差别是多了一个估价函数，每次取出一个估算最优的状态以期更高效完成任务

重点在于估价函数 $\text{h*(n)}$ 的设计，若实际代价为 $\text{h(n)}$，则

若 $\text{h*(n)=h(n)}$，设计得非常好

若 $\text{h*(n)<h(n)}$，跑得更快，只是可能搜不出来正确答案

若 $\text{h*(n)>h(n)}$，慢是慢些，但正确性还有保证

例如 $k$ 短路

暴搜的话就是找出所有路径，取第 $k$ 短

但实际上若精准预估当前状态到终止状态的代价，每次取出最小代价状态，

那么 $k$ 次到达终止状态后，前 $k$ 短路就已经被搜出来了

显然，估价函数就定为当前状态到终止状态的最短路

这个可以反向建图 $\text{dijkstra}$ 预处理

$\text{sample}$

P2483 【模板】k 短路 / [SDOI2010] 魔法猪学院

$\text{Code}$

#include <cstdio>

#include <queue>

#define RE register

#define IN inline

using namespace std;

const int N = 5005, M = 2e5 + 5, INF = 1e18;

int n, m, cnt[N];

double e;

struct node{

	int id; double f, v;

	bool operator < (const node &c) const{return f > c.f;}

};

priority_queue<node> Q;

struct graph{

	struct edge{int to, nxt; double w;}e[M];

	int tot, h[N], vis[N]; double dis[N];

	IN void add(int u, int v, double w){e[++tot] = edge{v, h[u], w}, h[u] = tot;}

	IN void getdis()

	{

		for(RE int i = 1; i < n; i++) dis[i] = INF, vis[i] = 0;

		vis[n] = 0, Q.push(node{n, 0});

		while (!Q.empty())

		{

			node x = Q.top(); Q.pop();

			if (vis[x.id]) continue;

			vis[x.id] = 1;

			for(RE int i = h[x.id]; i; i = e[i].nxt)

			{

				int v = e[i].to;

				if (dis[v] > dis[x.id] + e[i].w)

					Q.push(node{v, dis[v] = dis[x.id] + e[i].w});

			}

		}

	}

}e1, e2;

int main()

{

	scanf("%d%d%lf", &n, &m, &e);

	int u, v; double w;

	for(RE int i = 1; i <= m; i++) scanf("%d%d%lf", &u, &v, &w), e1.add(u, v, w), e2.add(v, u, w);

	e2.getdis(), Q.push(node{1, 0});

	int k = (int)e / e2.dis[1], ans = 0;

	while (!Q.empty())

	{

		node x = Q.top(); Q.pop();

		++cnt[x.id];

		if (x.id == n)

		{

			e -= x.v;

			if (e <= 0){printf("%d\n", ans); return 0;}

			++ans;

		}

		for(RE int i = e1.h[x.id]; i; i = e1.e[i].nxt)

		{

			int v = e1.e[i].to;

			if (cnt[v] < k && x.v + e1.e[i].w + e2.dis[v] <= e)

				Q.push(node{v, x.v + e1.e[i].w + e2.dis[v], x.v + e1.e[i].w});

		}

	}

	printf("%d\n", ans);

}

P2901 [USACO08MAR]Cow Jogging G

$\text{Code}$

#include <cstdio>

#include <queue>

#define RE register

#define IN inline

typedef long long LL;

using namespace std;

const int N = 1005, M = 2e5 + 5, INF = 1e9;

int n, m, k, cnt[N];

struct node{

	int id; LL f, v;

	bool operator < (const node &c) const{return f > c.f;}

};

priority_queue<node> Q;

struct graph{

	struct edge{int to, nxt, w;}e[M];

	int tot, h[N], vis[N]; LL dis[N];

	IN void add(int u, int v, int w){e[++tot] = edge{v, h[u], w}, h[u] = tot;}

	IN void getdis()

	{

		for(RE int i = 2; i <= n; i++) dis[i] = INF, vis[i] = 0;

		vis[1] = 0, Q.push(node{1, 0});

		while (!Q.empty())

		{

			node x = Q.top(); Q.pop();

			if (vis[x.id]) continue;

			vis[x.id] = 1;

			for(RE int i = h[x.id]; i; i = e[i].nxt)

			{

				int v = e[i].to;

				if (dis[v] > dis[x.id] + e[i].w)

					Q.push(node{v, dis[v] = dis[x.id] + e[i].w});

			}

		}

	}

}e1, e2;

int main()

{

	scanf("%d%d%d", &n, &m, &k);

	for(RE int i = 1, u, v, w; i <= m; i++) scanf("%d%d%d", &u, &v, &w), e1.add(u, v, w), e2.add(v, u, w);

	e2.getdis(), Q.push(node{n, 0});

	int sum = 0;

	while (!Q.empty())

	{

		node x = Q.top(); Q.pop();

		++cnt[x.id];

		if (x.id == 1)

		{

			printf("%d\n", x.v), ++sum;

			if (sum == k) return 0;

		}

		for(RE int i = e1.h[x.id]; i; i = e1.e[i].nxt)

		{

			int v = e1.e[i].to;

			if (cnt[v] < k)

				Q.push(node{v, x.v + e1.e[i].w + e2.dis[v], x.v + e1.e[i].w});

		}

	}

	for(RE int i = sum; i < k; i++) printf("-1\n");

}

巴特西

A*算法小记

\(\text{A*}\)

\(\text{sample}\)

最新文章

热门文章