两种算法解决从起点到终点状态过多的问题（BFS剪枝）
双向广搜
双向广搜实际是 B F S BFS BFS的一种剪枝形式 实现方式是 <mark>同时从起点和终点搜索到相遇为止</mark>
AcWing190. 字串变换
已知有两个字串 A A A, B B B 及一组字串变换的规则（至多6个规则）:
A 1 − > B 1 A_{1} -> B_{1} A1−>B1
A 2 − > B 2 A_{2} -> B_{2} A2−>B2
…
规则的含义为：在 A A A 中的子串 A 1 A_{1} A1 可以变换为 B 1 B_{1} B1、 A 2 A_{2} A2 可以变换为 B 2 B_{2} B2 …。
例如： A A A＝’ a b c d abcd abcd’ B B B＝’ x y z xyz xyz’
变换规则为：
$‘abc’->‘xu’ $
$ ‘ud’->‘y’$
$ ‘y’->‘yz’$
则此时， A A A 可以经过一系列的变换变为 B B B，其变换的过程为：
‘ a b c d ’ − > ‘ x u d ’ − > ‘ x y ’ − > ‘ x y z ’ ‘abcd’->‘xud’->‘xy’->‘xyz’ ‘abcd’−>‘xud’−>‘xy’−>‘xyz’
共进行了三次变换，使得 AA 变换为BB。
输入格式
输入格式如下：
A B A B AB
A 1 B 1 A_{1} B_{1} A1B1
A 2 B 2 A_{2} B_{2} A2B2
… …
所有字符串长度的上限为 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 算法结束
终点第一次被弹出时 一定是最小的 但是其他点第一次被弹出时不一定是最小值
<mark>保证有解才可以用A-star</mark>
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 1≤S,T≤N≤1000 1≤S,T≤N≤1000
0 ≤ M ≤ 105 0≤M≤105 0≤M≤105
1 ≤ K ≤ 1000 1≤K≤1000 1≤K≤1000
1 ≤ L ≤ 100 1≤L≤100 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;
}
京公网安备 11010502036488号