双向广搜和A-star-阿里云开发者社区

两种算法解决从起点到终点状态过多的问题（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。

输入格式

输入格式如下：

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;
}

双向广搜和A-star

双向广搜

AcWing190. 字串变换

输入格式

代码

A-star

AcWing179 八数码

代码

AcWing178 第K短路

输入格式

输出格式

数据范围

代码

热门文章

最新文章

相关电子书