A*

A*搜索

A * 搜索算法（英文：A*search algorithm，A * 读作 A-star），简称 A * 算法，是一种在图形平面上，对于有多个节点的路径求出最低通过成本的算法。它属于图遍历（英文：Graph traversal）和最佳优先搜索算法（英文：Best-first search），亦是 BFS 的改进。

八数码难题

题目描述

在 的棋盘上，摆有八个棋子，每个棋子上标有 至 的某一数字。棋盘中留有一个空格，空格用 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 ），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入格式

输入初始状态，一行九个数字，空格用 表示。

输出格式

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。

样例 #1

样例输入 #1

1
283104765

样例输出 #1

1
4

提示

样例解释

图中标有 的是空格。绿色格子是空格所在位置，橙色格子是下一步可以移动到空格的位置。如图所示，用四步可以达到目标状态。

并且可以证明，不存在更优的策略。

题解

  • 定义起点 ，终点 ，从起点（初始状态）开始的距离函数 ，到终点（最终状态）的距离函数 ，，以及每个点的估价函数 。
  • A * 算法每次从优先队列中取出一个 最小的元素，然后更新相邻的状态。
  • 如果 ，则 A * 算法能找到最优解。
  • 上述条件下，如果 满足三角形不等式，则 A * 算法不会将重复结点加入队列。
  • 当 时，A * 算法变为 Dijkstra；当 并且边权为 1 时变为 BFS。
  • 因为 priority_queue 是最大堆，而我们希望 值小的节点优先被处理，所以重载 < 运算符为“较大”的 f(n) 值被视为“较小”。这样，队列的堆顶总是保持 f(n) 值最小的节点，这样出队列的顺序是 f(n) 从小到大。
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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
using namespace std;
const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
int fx, fy;
char ch;

struct matrix {
  int a[5][5];

  bool operator<(matrix x) const {
    for (int i = 1; i <= 3; i++)
      for (int j = 1; j <= 3; j++)
        if (a[i][j] != x.a[i][j]) return a[i][j] < x.a[i][j];
    return false;
  }
} f, st;

int h(matrix a) {
  int ret = 0;
  for (int i = 1; i <= 3; i++)
    for (int j = 1; j <= 3; j++)
      if (a.a[i][j] != st.a[i][j]) ret++;
  return ret;
}

struct node {
  matrix a;
  int t;

  bool operator<(node x) const { return t + h(a) > x.t + h(x.a); }
} x;

priority_queue<node> q;  // 搜索队列
set<matrix> s;           // 防止搜索队列重复

int main() {
  st.a[1][1] = 1;  // 定义标准表
  st.a[1][2] = 2;
  st.a[1][3] = 3;
  st.a[2][1] = 8;
  st.a[2][2] = 0;
  st.a[2][3] = 4;
  st.a[3][1] = 7;
  st.a[3][2] = 6;
  st.a[3][3] = 5;
  for (int i = 1; i <= 3; i++)  // 输入
    for (int j = 1; j <= 3; j++) {
      scanf(" %c", &ch);
      f.a[i][j] = ch - '0';
    }
  q.push({f, 0});
  while (!q.empty()) {
    x = q.top();
    q.pop();
    if (!h(x.a)) {  // 判断是否与标准矩阵一致
      printf("%d\n", x.t);
      return 0;
    }
    for (int i = 1; i <= 3; i++)
      for (int j = 1; j <= 3; j++)
        if (!x.a.a[i][j]) fx = i, fy = j;  // 查找空格子（0号点）的位置
    for (int i = 0; i < 4; i++) {  // 对四种移动方式分别进行搜索
      int xx = fx + dx[i], yy = fy + dy[i];
      if (1 <= xx && xx <= 3 && 1 <= yy && yy <= 3) {
        swap(x.a.a[fx][fy], x.a.a[xx][yy]);
        if (!s.count(x.a))
          s.insert(x.a),
              q.push({x.a, x.t + 1});  // 这样移动后，将新的情况放入搜索队列中
        swap(x.a.a[fx][fy], x.a.a[xx][yy]);  // 如果不这样移动的情况
      }
    }
  }
  return 0;
}

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

注：对于 短路问题，A* 算法的最坏时间复杂度是 的。虽然 A* 算法可以通过本题原版数据，但可以构造数据，使得 A* 算法在原题的数据范围内无法通过。事实上，存在使用可持久化可并堆的算法可以做到在 的时间复杂度解决 短路问题。详情见 OI-Wiki。

题目描述

iPig 在假期来到了传说中的魔法猪学院，开始为期两个月的魔法猪训练。经过了一周理论知识和一周基本魔法的学习之后，iPig 对猪世界的世界本原有了很多的了解：众所周知，世界是由元素构成的；元素与元素之间可以互相转换；能量守恒。

iPig 今天就在进行一个麻烦的测验。iPig 在之前的学习中已经知道了很多种元素，并学会了可以转化这些元素的魔法，每种魔法需要消耗 iPig 一定的能量。作为 PKU 的顶尖学猪，让 iPig 用最少的能量完成从一种元素转换到另一种元素等等，iPig 的魔法导猪可没这么笨！这一次，他给 iPig 带来了很多 号元素的样本，要求 iPig 使用学习过的魔法将它们一个个转化为 号元素，为了增加难度，要求每份样本的转换过程都不相同。这个看似困难的任务实际上对 iPig 并没有挑战性，因为，他有坚实的后盾现在的你呀！

注意，两个元素之间的转化可能有多种魔法，转化是单向的。转化的过程中，可以转化到一个元素（包括开始元素）多次，但是一但转化到目标元素，则一份样本的转化过程结束。iPig 的总能量是有限的，所以最多能够转换的样本数一定是一个有限数。具体请参看样例。

输入格式

第一行三个数 ，表示 iPig 知道的元素个数（元素从 到 编号），iPig 已经学会的魔法个数和 iPig 的总能量。

后跟 行每行三个数 表示 iPig 知道一种魔法，消耗 的能量将元素 变换到元素 。

输出格式

一行一个数，表示最多可以完成的方式数。输入数据保证至少可以完成一种方式。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
4 6 14.9
1 2 1.5
2 1 1.5
1 3 3
2 3 1.5
3 4 1.5
1 4 1.5

样例输出 #1

1
3

提示

有意义的转换方式共 种：

，消耗能量 。

，消耗能量 。

，消耗能量 。

，消耗能量 。

显然最多只能完成其中的 种转换方式（选第一种方式，后三种方式任选两个），即最多可以转换 份样本。

如果将 改为 ，则可以完成以上全部方式，答案变为 。

数据规模

占总分不小于 的数据满足 。

占总分不小于 的数据满足 且 和所有的 均为整数（可以直接作为整型数字读入）。

所有数据满足 ，，，， 和所有的 为实数。

题解

  • 强化对 A* 算法的理解和思考。
  • 使用反向图和优先队列计算从终点 n 到其他所有节点的最短路径，并存储在数组 f[] 中。这部分相当于预处理，用于A*算法中的启发函数。
  • 启发式搜索：使用优先队列 q 来实现 A* 搜索。q 中的节点按估计的代价 v + f[x] 排列，其中 v 是当前路径的实际权重，f[x] 是从节点 x 到终点的最短路径权重（启发函数）。
  • 路径扩展：从起点 1 开始扩展，每次从优先队列中取出估计代价最小的节点进行扩展，检查是否可以到达终点 n，并且记录满足条件的路径数量。
  • 条件判断：使用 cnt[] 控制节点的访问次数，防止过多扩展同一个节点。每当找到一条满足条件的路径时，减少能量 e，直到能量不足为止。
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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 5010;
const int maxm = 400010;
const double inf = 2e9;

//  h[]、nxt[]、p[] 和 w[]：存储正向图的邻接表
// 分别表示某个节点的第一条边、下一条边、终点节点、边的权重。
//  h1[]、nxt1[]、p1[] 和 w1[]：存储反向图的邻接表。
int n, m, k, u, v, cur, h[maxn], nxt[maxm], p[maxm], cnt[maxn], ans;
int cur1, h1[maxn], nxt1[maxm], p1[maxm];
double e, ww, w[maxm], f[maxn];
double w1[maxm];
bool tf[maxn];

// f[]：记录从终点 n 到各个节点的最短路径权重（反向最短路径）
// cnt[]：记录某个节点被访问的次数，用于控制搜索深度
// ans：最终输出的满足条件的路径数量
 
void add_edge(int x, int y, double z) {  // 正向建图函数
  cur++;
  nxt[cur] = h[x];
  h[x] = cur;
  p[cur] = y;
  w[cur] = z;
}

void add_edge1(int x, int y, double z) {  // 反向建图函数
  cur1++;
  nxt1[cur1] = h1[x];
  h1[x] = cur1;
  p1[cur1] = y;
  w1[cur1] = z;
}

struct node {  // 使用A*时所需的结构体
  int x;
  double v;

  bool operator<(node a) const { return v + f[x] > a.v + f[a.x]; }
};

priority_queue<node> q; // 用于A*算法的优先队列，存储节点和当前路径权重 

struct node2 {  // 计算t到所有结点最短路时所需的结构体
  int x;
  double v;

  bool operator<(node2 a) const { return v > a.v; }
} x;

priority_queue<node2> Q; //  用于计算从终点 n 到所有节点的最短路径的优先队列

int main() {
  scanf("%d%d%lf", &n, &m, &e);
  while (m--) {
    scanf("%d%d%lf", &u, &v, &ww);
    add_edge(u, v, ww);   // 正向建图
    add_edge1(v, u, ww);  // 反向建图
  }
  // 计算终点到所有节点的最短路径，存储在数组 f[] 中相当于预处理
  for (int i = 1; i < n; i++) f[i] = inf;
  Q.push({n, 0});
  while (!Q.empty()) {  // 计算t到所有结点的最短路
    x = Q.top();
    Q.pop();
    if (tf[x.x]) continue;
    tf[x.x] = true;
    f[x.x] = x.v;
    for (int j = h1[x.x]; j; j = nxt1[j]) Q.push({p1[j], x.v + w1[j]});
  }
  
  // 使用A*算法搜索所有路径
  k = (int)e / f[1]; // 估算能够尝试从起点到终点的最大往返次数 
  q.push({1, 0});
  while (!q.empty()) {  // 使用A*算法
    node x = q.top();
    q.pop();
    cnt[x.x]++;
    if (x.x == n) {
      e -= x.v;
      if (e < 0) {
        printf("%d\n", ans);
        return 0;
      }
      ans++;
    }
    for (int j = h[x.x]; j; j = nxt[j])
      if (cnt[p[j]] <= k && x.v + w[j] <= e) q.push({p[j], x.v + w[j]});
  }
  
  printf("%d\n", ans);
  return 0;
}

邻接表表示法：在这种表示法中，每个节点都会有一个链表，链表中存储的是与该节点相连的其他节点和边的权重。这个结构在稀疏图中（即节点很多，但每个节点的连接边较少）非常高效。

代码中的相关数据结构如下：

1
2
3
4
5
6
7
const int maxn = 5010;      // 最大节点数
const int maxm = 400010;    // 最大边数
int h[maxn], nxt[maxm], p[maxm];   // 正向图的邻接表
double w[maxm];             // 正向图中的边的权重

int h1[maxn], nxt1[maxm], p1[maxm];  // 反向图的邻接表
double w1[maxm];             // 反向图中的边的权重
  • h[] 和 h1[]：分别表示正向图和反向图中，每个节点的第一条出边的索引。初始时都设置为0。
  • nxt[] 和 nxt1[]：表示图中每条边的下一条边的索引，用于构成邻接表的链表结构。
  • p[] 和 p1[]：表示每条边的终点（即目标节点）。
  • w[] 和 w1[]：表示每条边的权重。

具体执行步骤：

  1. 增加当前边的编号 cur。
  2. 将当前边的下一条边设为节点 x 原来的第一条边（即 nxt[cur] = h[x]）。
  3. 更新节点 x 的第一条边为当前边（即 h[x] = cur）。
  4. 设置当前边的终点为 y，权重为 z。