算法提高之搜索：BFS中的双向广搜和A-star

1、双向广搜

1.1、字串变换

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>using namespace std;//规则数 最多是6
const int N = 6;//记录有多少个规则
int n;
//起点和终点
string A, B;
//规则
string a[N], b[N];//扩展的时候扩展一层
int extend(queue<string>& q, unordered_map<string, int>&da, unordered_map<string, int>& db, string a[N], string b[N])
{
    //把和队首元素距离一样的元素全部扩展一遍int d = da[q.front()];while (q.size() && da[q.front()] == d){
    auto t = q.front();q.pop();//枚举所有规则for (int i = 0; i < n; i ++ )//枚举子串for (int j = 0; j < t.size(); j ++ )//当前子串中的一部分和规则是否匹配if (t.substr(j, a[i].size()) == a[i]){
    //能匹配->扩展 前边照搬，中间改变，后边照搬//t.substr（0，j）获得字符串t中从第0位开始的长度为j的字符串//t.substr(j + a[i].size()) 从j + a[i].size()位开始枚举，一直枚举到最后string r = t.substr(0, j) + b[i] + t.substr(j + a[i].size());//现在是在a中做广搜，如果找到的结果在b中有，说明找到最后的结果了。if (db.count(r)) return da[t] + db[r] + 1;//说明在a中r已经搜过了，不能重复搜索if (da.count(r)) continue;//如果在a中没搜过 则插入da[r] = da[t] + 1;q.push(r);}}//没有搜到 返回大于10的数 表示无解return 11;
}int bfs()
{
    if (A == B) return 0;//双向bfs 定义两个队列和两个距离queue<string> qa, qb;unordered_map<string, int> da, db;qa.push(A), qb.push(B);da[A] = db[B] = 0;int step = 0;//假如qa空，起点搜，全部搜完没有到终点->无解。while (qa.size() && qb.size()){
    //t表示答案中的距离int t;//先扩展较小的队列 且每次只扩展一层(1个step)//扩展qa 距离数组是da 规则是把a->bif (qa.size() < qb.size()) t = extend(qa, da, db, a, b);//扩展qb 距离数组是db 规则是把b->aelse t = extend(qb, db, da, b, a);if (t <= 10) return t;//扩展的步数不能超过10步if ( ++ step == 10) return -1;}return -1;
}int main()
{
    cin >> A >> B;while (cin >> a[n] >> b[n]) n ++ ;int t = bfs();if (t == -1) puts("NO ANSWER!");else cout << t << endl;return 0;
}

2、A-star

估计函数应该>=0

2.1、第k短路

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>#define x first
#define y secondusing namespace std;typedef pair<int, int> PII;
typedef pair<int, PII> PIII;const int N = 1010, M = 200010;int n, m, S, T, K;
int h[N], rh[N], e[M], w[M], ne[M], idx;
//cnt表示中间遍历几次
int dist[N], cnt[N];
bool st[N];void add(int h[], int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}void dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({
    0, T});memset(dist, 0x3f, sizeof dist);dist[T] = 0;while (heap.size()){
    auto t = heap.top();heap.pop();int ver = t.y;if (st[ver]) continue;st[ver] = true;for (int i = rh[ver]; ~i; i = ne[i]){
    int j = e[i];if (dist[j] > dist[ver] + w[i]){
    dist[j] = dist[ver] + w[i];heap.push({
    dist[j], j});}}}
}int astar()
{
    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.y.y, distance = t.y.x;cnt[ver] ++ ;if (cnt[T] == K) return distance;for (int i = h[ver]; ~i; i = ne[i]){
    int j = e[i];/* 如果走到一个中间点都cnt[j]>=K，则说明j已经出队k次了，且astar()并没有return distance,说明从j出发找不到第k短路(让终点出队k次)，即继续让j入队的话依然无解，那么就没必要让j继续入队了*/if (cnt[j] < K)//想找到第k短路，不论大小，全部加进来，让小根堆去处理heap.push({
    distance + w[i] + dist[j], {
    distance + w[i], j}});}}return -1;
}int main()
{
    scanf("%d%d", &n, &m);memset(h, -1, sizeof h);memset(rh, -1, sizeof rh);for (int i = 0; i < m; i ++ ){
    int a, b, c;scanf("%d%d%d", &a, &b, &c);add(h, a, b, c);add(rh, b, a, c);}scanf("%d%d%d", &S, &T, &K);//至少包含一条边if (S == T) K ++ ;dijkstra();printf("%d\n", astar());return 0;
}

2.2、八数码

估价函数的取法：是保证当前状态的估计距离小于等于当前状态到终点的真实距离。原因是每个点不可能直接按照曼哈顿距离移动到他想去的位置。需要迂回一下才能到。因此估价函数取曼哈顿距离一定小于真实距离。

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>using namespace std;int f(string state)
{
    int res = 0;for (int i = 0; i < state.size(); i ++ )if (state[i] != 'x'){
    int t = state[i] - '1';res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);}return res;
}string bfs(string start)
{
    int dx[4] = {
    -1, 0, 1, 0}, dy[4] = {
    0, 1, 0, -1};char op[4] = {
    'u', 'r', 'd', 'l'};string end = "12345678x";unordered_map<string, int> dist;unordered_map<string, pair<string, char>> prev;//第一维是实际距离+估计距离，第二维是状态priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> heap;heap.push({
    f(start), start});dist[start] = 0;while (heap.size()){
    auto t = heap.top();heap.pop();string state = t.second;if (state == end) break;int step = dist[state];int x, y;for (int i = 0; i < state.size(); i ++ )if (state[i] == 'x'){
    x = i / 3, y = i % 3;break;}string source = state;for (int i = 0; i < 4; i ++ ){
     int a = x + dx[i], b = y + dy[i];if (a >= 0 && a < 3 && b >= 0 && b < 3){
    swap(state[x * 3 + y], state[a * 3 + b]);if (!dist.count(state) || dist[state] > step + 1){
    dist[state] = step + 1;prev[state] = {
    source, op[i]};heap.push({
    dist[state] + f(state), state}); }swap(state[x * 3 + y], state[a * 3 + b]);}}}string res;while (end != start){
    res += prev[end].second;end = prev[end].first;}reverse(res.begin(), res.end());return res;
}int main()
{
    //g是包含x的序列//seq不包含x的序列 用来计算逆序对string g, c, seq;while (cin >> c){
    g += c;if (c != "x") seq += c; }//计算逆序对的数量int t = 0;for (int i = 0; i < seq.size(); i ++ )for (int j = i + 1; j < seq.size(); j ++ )if (seq[i] > seq[j])t ++ ;if (t % 2) puts("unsolvable");else cout << bfs(g) << endl;return 0;
}