双向A搜索（Bidirectional A Search）是传统A算法的改进版本，同时从起点和终点进行搜索，直到两个搜索前沿相遇。理论上可以将搜索空间从 O(b^d) 降低到 O(b^(d/2))，在实际路径规划中效果显著。本文用Java实现双向A算法，讲解一致性启发式、相遇判定与路径重建策略。
算法核心思想
标准A搜索从起点向终点单向扩展。双向A同时维护两个搜索过程：
- 前向搜索：从起点出发，使用启发式函数
h_f(v) = dist(v, goal) - 后向搜索：从终点出发，使用启发式函数
h_b(v) = dist(v, start) - 终止条件：当某个节点被两个方向的搜索都访问过时，可以找到最优路径
为什么双向搜索更快
若分支因子为 b，最优解深度为 d：
– 单向A访问节点数：O(b^d)
– 双向A访问节点数：O(2 · b^(d/2)) = O(b^(d/2))
搜索空间呈指数级减少。
关键挑战与解决方案
1. 启发式函数的一致性
为保证双向A找到最优解，启发式函数必须满足一致性*（Consistent/Monotonic）：
h(u) <= cost(u, v) + h(v) 对所有边(u,v)成立
常用的曼哈顿距离、欧几里得距离都满足一致性。
2. 相遇判定
双向搜索的终止条件比单向复杂。当从优先队列中取出的节点已被另一方向访问过时，可以停止搜索。
3. 路径重建
需要记录两个方向的前驱节点，在相遇后拼接路径。
Java完整实现
import java.util.*;
/**
* 双向A*搜索（Bidirectional A* Search）
* 同时从起点和终点搜索，直到搜索前沿相遇
*/
public class BidirectionalAStar {
/**
* 图节点，用于网格地图
*/
static class Node {
int x, y;
Node(int x, int y) { this.x = x; this.y = y; }
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Node)) return false;
Node other = (Node) o;
return x == other.x && y == other.y;
}
@Override
public int hashCode() {
return x * 131 + y;
}
@Override
public String toString() {
return String.format("(%d,%d)", x, y);
}
}
/**
* 搜索状态，存储在优先队列中
*/
static class State implements Comparable<State> {
Node node; // 当前节点
double g; // 从起点/终点到当前节点的实际代价
double f; // f = g + h
State parent; // 前驱状态（用于路径重建）
State(Node node, double g, double h, State parent) {
this.node = node;
this.g = g;
this.f = g + h;
this.parent = parent;
}
@Override
public int compareTo(State other) {
return Double.compare(this.f, other.f);
}
}
// 网格地图：0表示可通行，1表示障碍物
private int[][] grid;
private int rows, cols;
// 四个方向 + 四个对角线方向（8连通）
private int[][] directions = {
{-1, 0}, {1, 0}, {0, -1}, {0, 1}, // 上下左右
{-1, -1}, {-1, 1}, {1, -1}, {1, 1} // 对角线
};
public BidirectionalAStar(int[][] grid) {
this.grid = grid;
this.rows = grid.length;
this.cols = grid[0].length;
}
/**
* 启发式函数：欧几里得距离（满足一致性）
*/
private double heuristic(Node a, Node b) {
double dx = a.x - b.x;
double dy = a.y - b.y;
return Math.sqrt(dx * dx + dy * dy);
}
/**
* 获取邻居节点及其移动代价
*/
private List<Map.Entry<Node, Double>> getNeighbors(Node node) {
List<Map.Entry<Node, Double>> neighbors = new ArrayList<>();
for (int i = 0; i < directions.length; i++) {
int nx = node.x + directions[i][0];
int ny = node.y + directions[i][1];
if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == 0) {
double cost = (i < 4) ? 1.0 : 1.414; // 正交1，对角线√2
neighbors.add(new AbstractMap.SimpleEntry<>(new Node(nx, ny), cost));
}
}
return neighbors;
}
/**
* 双向A*搜索主算法
* @return 路径节点列表（包含起点和终点），无解返回null
*/
public List<Node> search(Node start, Node goal) {
if (grid[start.x][start.y] == 1 || grid[goal.x][goal.y] == 1) {
return null; // 起点或终点是障碍物
}
if (start.equals(goal)) {
return Collections.singletonList(start);
}
// 两个方向的优先队列
PriorityQueue<State> openForward = new PriorityQueue<>();
PriorityQueue<State> openBackward = new PriorityQueue<>();
// 两个方向的已访问集合：Node -> State
Map<Node, State> visitedForward = new HashMap<>();
Map<Node, State> visitedBackward = new HashMap<>();
// 初始化
State startState = new State(start, 0, heuristic(start, goal), null);
State goalState = new State(goal, 0, heuristic(goal, start), null);
openForward.offer(startState);
openBackward.offer(goalState);
visitedForward.put(start, startState);
visitedBackward.put(goal, goalState);
// 最优路径记录
double bestPathLength = Double.MAX_VALUE;
State meetingForward = null; // 前向搜索到达相遇点的状态
State meetingBackward = null; // 后向搜索到达相遇点的状态
int nodesExpanded = 0;
while (!openForward.isEmpty() && !openBackward.isEmpty()) {
// 选择f值较小的一方进行扩展（平衡搜索）
boolean expandForward = openForward.peek().f <= openBackward.peek().f;
if (expandForward) {
State current = openForward.poll();
nodesExpanded++;
// 检查是否被后向搜索访问过
if (visitedBackward.containsKey(current.node)) {
State backwardState = visitedBackward.get(current.node);
double totalLen = current.g + backwardState.g;
if (totalLen < bestPathLength) {
bestPathLength = totalLen;
meetingForward = current;
meetingBackward = backwardState;
}
}
// 如果当前f值已超过最优路径长度，可以停止
if (current.f >= bestPathLength) {
break;
}
// 扩展邻居
for (Map.Entry<Node, Double> neighbor : getNeighbors(current.node)) {
Node next = neighbor.getKey();
double newG = current.g + neighbor.getValue();
if (!visitedForward.containsKey(next) || newG < visitedForward.get(next).g) {
State nextState = new State(next, newG, heuristic(next, goal), current);
visitedForward.put(next, nextState);
openForward.offer(nextState);
}
}
} else {
State current = openBackward.poll();
nodesExpanded++;
// 检查是否被前向搜索访问过
if (visitedForward.containsKey(current.node)) {
State forwardState = visitedForward.get(current.node);
double totalLen = current.g + forwardState.g;
if (totalLen < bestPathLength) {
bestPathLength = totalLen;
meetingForward = forwardState;
meetingBackward = current;
}
}
if (current.f >= bestPathLength) {
break;
}
// 扩展邻居（后向搜索的邻居就是原图的反向边）
for (Map.Entry<Node, Double> neighbor : getNeighbors(current.node)) {
Node next = neighbor.getKey();
double newG = current.g + neighbor.getValue();
if (!visitedBackward.containsKey(next) || newG < visitedBackward.get(next).g) {
State nextState = new State(next, newG, heuristic(next, start), current);
visitedBackward.put(next, nextState);
openBackward.offer(nextState);
}
}
}
}
System.out.println("扩展节点数: " + nodesExpanded);
if (meetingForward == null) {
return null; // 无解
}
return reconstructPath(meetingForward, meetingBackward);
}
/**
* 重建路径：拼接前向路径和后向路径
*/
private List<Node> reconstructPath(State forward, State backward) {
List<Node> path = new ArrayList<>();
// 前向路径（从起点到相遇点）
LinkedList<Node> forwardPath = new LinkedList<>();
State cur = forward;
while (cur != null) {
forwardPath.addFirst(cur.node);
cur = cur.parent;
}
// 后向路径（从相遇点到终点，需要反转）
LinkedList<Node> backwardPath = new LinkedList<>();
cur = backward.parent; // 跳过相遇点（已在前向路径中）
while (cur != null) {
backwardPath.addLast(cur.node);
cur = cur.parent;
}
path.addAll(forwardPath);
path.addAll(backwardPath);
return path;
}
/**
* 可视化路径
*/
public void printPath(List<Node> path, Node start, Node goal) {
if (path == null) {
System.out.println("无解！");
return;
}
char[][] display = new char[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
display[i][j] = grid[i][j] == 1 ? '#' : '.';
}
}
for (Node node : path) {
display[node.x][node.y] = '*';
}
display[start.x][start.y] = 'S';
display[goal.x][goal.y] = 'G';
System.out.println("路径地图 (*=路径, S=起点, G=终点, #=障碍):");
for (char[] row : display) {
System.out.println(new String(row));
}
System.out.println("\n路径长度: " + path.size() + " 步");
System.out.println("路径: " + path);
}
/**
* 单向A*搜索（用于对比）
*/
public List<Node> astar(Node start, Node goal) {
PriorityQueue<State> open = new PriorityQueue<>();
Map<Node, State> visited = new HashMap<>();
State startState = new State(start, 0, heuristic(start, goal), null);
open.offer(startState);
visited.put(start, startState);
int nodesExpanded = 0;
while (!open.isEmpty()) {
State current = open.poll();
nodesExpanded++;
if (current.node.equals(goal)) {
System.out.println("单向A*扩展节点数: " + nodesExpanded);
return reconstructSinglePath(current);
}
for (Map.Entry<Node, Double> neighbor : getNeighbors(current.node)) {
Node next = neighbor.getKey();
double newG = current.g + neighbor.getValue();
if (!visited.containsKey(next) || newG < visited.get(next).g) {
State nextState = new State(next, newG, heuristic(next, goal), current);
visited.put(next, nextState);
open.offer(nextState);
}
}
}
return null;
}
private List<Node> reconstructSinglePath(State goalState) {
LinkedList<Node> path = new LinkedList<>();
State cur = goalState;
while (cur != null) {
path.addFirst(cur.node);
cur = cur.parent;
}
return path;
}
public static void main(String[] args) {
// 创建测试地图（0=可通行, 1=障碍）
int[][] grid = {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
{0, 1, 1, 1, 1, 1, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 1, 0, 1, 0},
{0, 1, 1, 1, 1, 0, 1, 0, 1, 0},
{0, 0, 0, 0, 1, 0, 0, 0, 1, 0},
{0, 1, 1, 0, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};
Node start = new Node(0, 0);
Node goal = new Node(9, 9);
BidirectionalAStar solver = new BidirectionalAStar(grid);
System.out.println("=== 双向A*搜索 ===");
List<Node> biPath = solver.search(start, goal);
solver.printPath(biPath, start, goal);
System.out.println("\n=== 单向A*搜索（对比） ===");
List<Node> singlePath = solver.astar(start, goal);
if (singlePath != null) {
System.out.println("路径长度: " + singlePath.size() + " 步");
}
// 大规模地图性能测试
System.out.println("\n=== 大规模地图性能测试 (50x50) ===");
int[][] largeGrid = new int[50][50];
// 随机添加一些障碍
Random rand = new Random(42);
for (int i = 0; i < 200; i++) {
largeGrid[rand.nextInt(50)][rand.nextInt(50)] = 1;
}
largeGrid[0][0] = 0;
largeGrid[49][49] = 0;
BidirectionalAStar largeSolver = new BidirectionalAStar(largeGrid);
Node largeStart = new Node(0, 0);
Node largeGoal = new Node(49, 49);
long t1 = System.currentTimeMillis();
List<Node> largeBi = largeSolver.search(largeStart, largeGoal);
long t2 = System.currentTimeMillis();
long t3 = System.currentTimeMillis();
List<Node> largeSingle = largeSolver.astar(largeStart, largeGoal);
long t4 = System.currentTimeMillis();
System.out.println("双向A*耗时: " + (t2 - t1) + " ms, 路径长度: " +
(largeBi != null ? largeBi.size() : "无解"));
System.out.println("单向A*耗时: " + (t4 - t3) + " ms, 路径长度: " +
(largeSingle != null ? largeSingle.size() : "无解"));
}
}
算法优化策略
1. 交替扩展策略
本实现采用”选择f值较小的一方进行扩展”的策略，保证两个方向的搜索前沿以相似速度推进。也可采用严格的交替策略（一轮前向、一轮后向）。
2. 提前终止条件
当从优先队列中取出的状态的f值已超过当前找到的最优路径长度时，可以安全终止搜索。这是因为A*的f值是下界估计，任何后续找到的路径都不可能更短。
3. 双向搜索的启发式一致性要求
单向A只需启发式函数可采纳（Admissible，不高估实际代价）即可保证最优性。但双向A要求更强的一致性条件，否则可能出现两个方向找到的路径不是全局最优的情况。
复杂度分析
| 指标 | 单向A* | 双向A* |
|---|---|---|
| 时间复杂度（最坏） | O(b^d) | O(b^(d/2)) |
| 空间复杂度（最坏） | O(b^d) | O(b^(d/2)) |
| 实际扩展节点数 | 较多 | 显著减少（通常2-4倍） |
其中 b 是分支因子，d 是最优解深度。双向搜索的理论优势在大规模问题中最为明显。
适用场景与注意事项
双向A*特别适合：
- 大规模地图路径规划：如游戏寻路、机器人导航
- 图搜索问题：起点和终点都已知的最短路径问题
- 状态空间搜索：如拼图、魔方等状态转换问题
注意事项：
- 启发式必须一致：不一致的启发式可能导致非最优解
- 图必须是无向或双向可达的：若边有方向，后向搜索需要在反向图上进行
- 内存开销：需要维护两个方向的已访问集合，内存使用约为单向的两倍
- 实现复杂度：相遇判定和路径重建比单向A*复杂
双向A是A算法的强力扩展，在保持最优性的同时大幅提升搜索效率，是游戏开发和路径规划中的常用技术。
