两种算法解决从起点到终点状态过多的问题（BFS剪枝）
双向广搜
双向广搜实际是B F S BFSBFS的一种剪枝形式 实现方式是 同时从起点和终点搜索到相遇为止
AcWing190. 字串变换
已知有两个字串 A AA, B BB 及一组字串变换的规则（至多6个规则）:
A 1 − > B 1
A 2 − > B 2
…
规则的含义为：在 A 中的子串 A 1 可以变换为 B 1、A 2 可以变换为 B 2 …。
例如：A＝‘abcd’ B BB＝’xyz’
变换规则为：
$‘abc’->‘xu’ $
$ ‘ud’->‘y’$
$ ‘y’->‘yz’$
则此时，A 可以经过一系列的变换变为 B BB，其变换的过程为：
‘ a b c d ’ − > ‘ x u d ’ − > ‘ x y ’ − > ‘ x y z ’
共进行了三次变换，使得 AA 变换为BB。
输入格式
输入格式如下：
AB
A 1 B 1
A 2 B 2
… …
所有字符串长度的上限为 20。
输出格式
若在 10 步（包含 10步）以内能将 A 变换为 B ，则输出最少的变换步数；否则输出”NO ANSWER!”
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<algorithm> #include<vector> #include<utility> #include<deque> #include<unordered_map> #define INF 0x3f3f3f3f #define mod 1000000007 #define endl '\n' #define eps 1e-6 inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; const int N = 1000; unordered_map<string, int>da, db; //两端扩展出的状态与最初状态的距离 string a[N], b[N]; int n; int extend(queue<string>& q, unordered_map<string, int>& da, unordered_map<string, int>& db, string a[], string b[]) { string t = q.front(); q.pop(); for (int i = 0; i < t.size(); ++i) { for (int j = 0; j < n; ++j) { if (t.substr(i, a[j].size()) == a[j]) { //如果从i开始之后的字符有与代替换字符相同的 string state = t.substr(0, i) + b[j] + t.substr(i + a[j].size()); //替换成state if (da.count(state))continue; if (db.count(state))return da[t] + 1 + db[state]; da[state] = da[t] + 1; q.push(state); } } } return 11; } int bfs(string A, string B) { queue<string>qa, qb; qa.push(A); qb.push(B); da[A] = 0; db[B] = 0; while (qa.size() && qb.size()) { //如果两个队列一个为空 一个不为空 说明起点和重点不连通 int t; if (qa.size() >= qb.size())t = extend(qa, da, db, a, b); //从队列小的开始扩展 因为每次一扩展队列就会变长 接下来该扩展较小的那个队列 else t = extend(qb, db, da, b, a); if (t <= 10)return t; } return 11; } int main() { string A, B; cin >> A >> B; while (cin >> a[n] >> b[n])++n; int t = bfs(A, B); if (t <= 10)cout << t << endl; else puts("NO ANSWER!"); return 0; }
A-star
利用启发函数 给每个点到终点一个估计距离 估计距离小于等于实际距离
优先队列 存起点到当前点的实际距离和当前点到终点的估计距离
每次选实际距离 + 估计距离最小的点扩展 终点第一次出队时 break 算法结束
终点第一次被弹出时 一定是最小的 但是其他点第一次被弹出时不一定是最小值
保证有解才可以用A-star
AcWing179 八数码
估价函数：当前状态中每个数的位置与它的目标位置的曼哈顿距离
八数码问题成立的充要条件: 初始状态逆序数为偶数
在一个3×3的网格中，1~8这8个数字和一个“X”恰好不重不漏地分布在这3×3的网格中。
例如：
1 2 3 X 4 6 7 5 8
在游戏过程中，可以把“X”与其上、下、左、右四个方向之一的数字交换（如果存在）。
我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
1 2 3 4 5 6 7 8 X
例如，示例中图形就可以通过让“X”先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下：
1 2 3 1 2 3 1 2 3 1 2 3 X 4 6 4 X 6 4 5 6 4 5 6 7 5 8 7 5 8 7 X 8 7 8 X
把“X”与上下左右方向数字交换的行动记录为“u”、“d”、“l”、“r”。
现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<cmath> #include<algorithm> #include<vector> #include<utility> #include<deque> #include<unordered_map> #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n' #define eps 1e-6 inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; typedef pair<int, string>PIS; typedef pair<int, PII>PIII; const int N = 5000; int f(string s) { int res = 0; for (int i = 0; i < s.size(); ++i) { if (s[i] != 'x') { int t = s[i] - '1'; res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3); } } return res; } string bfs(string start) { string end = "12345678x"; unordered_map<string, pair<char, string>>pre; unordered_map<string, int>dist; priority_queue<PIS, vector<PIS>, greater<PIS>>heap; dist[start] = 0; heap.push({ f(start),start }); char c[5] = "urdl"; int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 }; while (heap.size()) { auto t = heap.top(); heap.pop(); string state = t.second; if (state == end)break; int x, y; for (int i = 0; i < state.size(); ++i) { if (state[i] == 'x') { x = i / 3; y = i % 3; } } string src = state; for (int i = 0; i < 4; ++i) { int a = x + dx[i]; int b = y + dy[i]; if (a < 0 || a >= 3 || b < 0 || b >= 3)continue; state = src; swap(state[a * 3 + b], state[x * 3 + y]); if (dist.count(state) == 0 || dist[src] + 1 < dist[state]) { dist[state] = dist[src] + 1; pre[state] = { c[i],src }; heap.push({ f(state) + dist[state],state }); } } } string res; while (end != start) { res += pre[end].first; end = pre[end].second; } reverse(res.begin(), res.end()); return res; } int main() { string start, flag; char c; while (cin >> c) { start += c; if (c != 'x')flag += c; } int st = 0; for (int i = 0; i < flag.size(); ++i) { for (int j = i + 1; j < flag.size(); ++j) if (flag[i] > flag[j])++st; } if (st & 1)puts("unsolvable"); else cout << bfs(start); return 0; }
AcWing178 第K短路
建反图 以终点到每个点的最短距离为启发函数值
给定一张N个点（编号1,2…N），M条边的有向图，求从起点S到终点T的第K短路的长度，路径允许重复经过点或边。
注意： 每条最短路中至少要包含一条边。
输入格式
第一行包含两个整数N和M。
接下来M行，每行包含三个整数A,B和L，表示点A与点B之间存在有向边，且边长为L。
最后一行包含三个整数S,T和K，分别表示起点S，终点T和第K短路。
输出格式
输出占一行，包含一个整数，表示第K短路的长度，如果第K短路不存在，则输出“-1”。
数据范围
1≤S,T≤N≤1000
50≤M≤105
1≤K≤1000
1≤L≤100
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<cmath> #include<algorithm> #include<vector> #include<utility> #include<deque> #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n' #define eps 1e-6 inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; typedef pair<int, PII>PIII; const int N = 10100; vector<PII>v1[N], v2[N]; int n, m; int S, K, T; int dist[N]; bool vis[N]; void dijkstra() { memset(dist, 0x3f, sizeof dist); priority_queue<PII, vector<PII>, greater<PII>>heap; dist[T] = 0; heap.push({ 0,T }); while (heap.size()) { auto t = heap.top(); heap.pop(); int ver = t.second; if (vis[ver])continue; vis[ver] = true; for (int i = 0; i < v2[ver].size(); ++i) { int j = v2[ver][i].second; int dis = v2[ver][i].first; if (dist[j] > dist[ver] + dis) { dist[j] = dist[ver] + dis; heap.push({ dist[j],j }); } } } } int astar() { int cnt = 0; priority_queue<PIII, vector<PIII>, greater<PIII>>heap; heap.push({ dist[S],{0,S} }); while (heap.size()) { auto t = heap.top(); heap.pop(); int ver = t.second.second; int dis = t.second.first; if (ver == T)cnt++; if (cnt == K)return dis; for (int i = 0; i < v1[ver].size(); ++i) { int j = v1[ver][i].second; if(cnt < K) heap.push({ dist[j] + dis + v1[ver][i].first,{dis + v1[ver][i].first,j} }); } } return -1; } int main() { cin >> n >> m; for (int i = 0; i < m; ++i) { int a, b, c; scanf("%d%d%d", &a, &b, &c); v1[a].push_back({ c,b }); //正向图 v2[b].push_back({ c,a }); //反向图 } scanf("%d%d%d", &S, &T, &K); if (S == T) ++K; dijkstra(); if (dist[S] >= 0x3f) { puts("-1"); return 0; } printf("%d\n", astar()); return 0; }
