双向广搜
Flood Fill算法通常用于填充区域，通过递归或迭代的方式遍历所有相邻的同类元素。但在复杂的情况下，如找到从起点到终点的最短路径，Flood Fill暴力枚举可能效率低下。
双向广度优先搜索（Bi-directional BFS）
双向广度优先搜索是一种优化策略，通过同时从起点和终点进行广度优先搜索，两端的搜索在中间某个位置相遇，大幅减少搜索空间和时间。
原理
-
初始化：
- 两个队列：一个从起点开始（正向队列），一个从终点开始（反向队列）。
- 两个哈希表：分别记录正向和反向搜索的访问节点及其深度。
-
交替扩展：
- 每次选择较小的队列进行扩展，确保每一步都尽可能少地增加搜索节点。
-
相遇判定：
- 每次扩展时检查当前节点是否已被另一端搜索到，如果是，则说明两端相遇，路径找到。
-
终止条件：
- 如果两端搜索在有限步数内相遇，则返回总步数。
- 如果搜索超过预设的最大步数，或两端都无法继续扩展，则判定为无解。
优势
双向广度优先搜索通过减少搜索深度和节点数量，显著提高了复杂路径问题的求解效率。
Java
import java.util.*;
public class Main {
static final int N = 10; // 替换规则的最大数量
static int n; // 实际替换规则的数量
static String A, B; // 初始字符串和目标字符串
static String[] a = new String[N], b = new String[N]; // 存储替换规则
// 扩展搜索函数
static int extend(Queue<String> q, Map<String, Integer> da,
Map<String, Integer> db, String[] a, String[] b) {
int d = da.get(q.peek()); // 当前扩展的深度
while (!q.isEmpty() && da.get(q.peek()) == d) {
String t = q.poll(); // 取出队列中的字符串
// 遍历所有替换规则
for (int i = 0; i < n; i++) {
for (int j = 0; j <= t.length() - a[i].length(); j++) {
// 如果匹配替换规则a[i]
if (t.substring(j, j + a[i].length()).equals(a[i])) {
// 用b[i]替换a[i]
String r = t.substring(0, j) + b[i] + t.substring(j + a[i].length());
// 如果在反向搜索中找到，返回总步数
if (db.containsKey(r))
return da.get(t) + db.get(r) + 1;
// 如果已经访问过，跳过
if (da.containsKey(r))
continue;
// 记录新的深度
da.put(r, da.get(t) + 1);
q.offer(r); // 将新字符串加入队列
}
}
}
}
return 11; // 如果扩展深度超过10，返回11（表示不可行）
}
// 双向广度优先搜索
static int bfs() {
if (A.equals(B))
return 0; // 如果初始字符串和目标字符串相同，返回0步
Queue<String> qa = new LinkedList<>();
Queue<String> qb = new LinkedList<>();
Map<String, Integer> da = new HashMap<>();
Map<String, Integer> db = new HashMap<>();
qa.add(A);
qb.add(B);
da.put(A, 0);
db.put(B, 0);
int step = 0; // 记录扩展的步数
while (!qa.isEmpty() && !qb.isEmpty()) {
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; // 如果找到解，返回步数
if (++step == 10)
return -1; // 超过10步，返回-1表示无解
}
return -1; // 无解
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
A = sc.next(); // 输入初始字符串
B = sc.next(); // 输入目标字符串
while (sc.hasNext()) {
a[n] = sc.next(); // 输入替换规则的左侧
b[n] = sc.next(); // 输入替换规则的右侧
n++;
}
int t = bfs(); // 执行双向广度优先搜索
if (t == -1)
System.out.println("NO ANSWER!"); // 无解输出提示
else
System.out.println(t); // 输出步数
}
}
C++
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
const int N = 10;
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)
{
string t = q.front();
q.pop();
// 尝试每个替换规则
for (int i = 0; i < n; i ++)
{
for (int j = 0; j < t.size(); j ++)
{
// 如果匹配替换规则a[i]
if (t.substr(j, a[i].size()) == a[i])
{
// 替换成b[i]
string r = t.substr(0, j) + b[i] + t.substr(j + a[i].size());
if (db.count(r)) // 如果在反向搜索中找到，返回总步数
return da[t] + db[r] + 1;
if (da.count(r)) // 如果已经访问过，跳过
continue;
da[r] = da[t] + 1; // 记录新的深度
q.push(r); // 将新字符串加入队列
}
}
}
}
return 11; // 如果扩展深度超过10，返回11（表示不可行）
}
// 双向广度优先搜索
int bfs()
{
if (A == B) return 0; // 如果初始字符串和目标字符串相同，返回0步
queue<string> qa, qb;
unordered_map<string, int> da, db;
qa.push(A), qb.push(B); // 初始化正向和反向队列
da[A] = db[B] = 0; // 初始化深度
int step = 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; // 如果找到解，返回步数
if (++ step == 10) return -1; // 超过10步，返回-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;
}
代码解释：
-
输入和初始化：
- 输入初始字符串
A和目标字符串B。 - 输入替换规则对
a[i]和b[i]，并存储在数组a和b中。
- 输入初始字符串
-
双向广度优先搜索（BFS）：
- 通过两个队列
qa和qb分别从初始字符串A和目标字符串B进行扩展。 - 使用两个哈希表
da和db记录从两个方向扩展的深度。
- 通过两个队列
-
扩展搜索函数
extend：- 从队列中取出当前字符串进行扩展。
- 遍历所有替换规则，尝试在当前字符串中进行替换操作。
- 检查新生成的字符串是否在对方的扩展路径中，如果是则返回总步数。
- 如果没有找到解，继续扩展。
-
主搜索逻辑
bfs：- 如果初始字符串和目标字符串相同，直接返回0步。
- 每次选择较小的队列进行扩展，以保证搜索效率。
- 如果在10步以内找到解，返回步数；否则返回-1表示无解。
通过这些步骤，代码实现了从初始字符串到目标字符串的最小替换步数的计算。
A*
A*算法的原理
A*算法是一种用于图搜索的启发式算法，广泛应用于路径规划和导航等问题。它结合了广度优先搜索和贪心算法的优点，通过估计从起点到终点的最短路径，提高了搜索效率。
主要步骤
-
初始化：
- 开始节点放入开放列表（待检查节点）。
- 封闭列表（已检查节点）为空。
-
选择节点：
- 从开放列表中选择总估值最小的节点
n进行处理，总估值f(n) = g(n) + h(n)，其中g(n)是起点到n的实际代价，h(n)是n到终点的估计代价。
- 从开放列表中选择总估值最小的节点
-
生成后继节点：
- 对当前节点
n生成所有可达的相邻节点m，计算它们的估值f(m)。 - 如果相邻节点不在封闭列表中，或通过当前节点到达相邻节点的路径更短，则更新其代价，并将其加入开放列表。
- 对当前节点
-
重复迭代：
- 重复步骤2和3，直到找到终点或开放列表为空。
-
路径重建：
- 从终点回溯到起点，重建最短路径。
优势
A*算法通过启发式函数 h(n) 有效地引导搜索方向，避免不必要的遍历，提高了搜索效率，特别适合处理复杂路径问题。其性能依赖于启发式函数的准确性，理想情况下，h(n) 应该低估实际代价。
应用场景
A*算法广泛应用于游戏AI、机器人导航、地图导航等领域，需要在复杂环境中快速找到最优路径。
A*算法在起点和终点不联通时效率低的原因
A*算法的效率高度依赖于启发式函数 ( h(n) ) 的准确性。当起点和终点不联通时，A*算法的性能会显著下降，原因如下：
-
启发式函数失效：A*算法在选择下一个扩展节点时依赖于估计代价函数 ( f(n) = g(n) + h(n) )。如果起点和终点不联通，启发式函数 ( h(n) ) 无法有效引导搜索方向，导致大量无效扩展。
-
全图遍历：在不联通的情况下，A*算法可能需要遍历整个图来确认无解。这使得其性能接近于最坏情况下的BFS或Dijkstra算法。
-
高计算代价：A*算法每次扩展节点时需要计算 ( f(n) ) 值，增加了计算开销。如果搜索空间大且无解，计算量会非常大。
实际影响
在起点和终点不联通的情况下，A*算法的时间复杂度可能退化为与传统BFS或Dijkstra相似，但由于启发式函数的额外计算（将普通队列改为了优先队列），实际运行时间更长。因此，A*在这种场景下的效率非常低。
优化方法
双向BFS：通过同时从起点和终点进行搜索，可以有效减少搜索空间，即使在不联通的情况下，也能更快地判定无解，从而提高整体效率。
