本文旨在帮助开发者理解和实现Java中的双向路径搜索算法。我们将深入探讨算法的核心思想，并针对常见的实现错误进行分析。通过改进代码逻辑，我们将展示如何构建完整的从起始点到终点的路径，确保算法的正确性和效率。
双向路径搜索的核心思想
双向路径搜索是一种优化搜索算法，它同时从起始节点和目标节点开始搜索，期望在中间相遇，从而减少搜索范围，提高搜索效率。其核心思想在于：
- 正向搜索： 从起始节点出发，沿着图的边进行搜索。
- 反向搜索： 从目标节点出发，沿着图的边进行反向搜索。
- 相遇检测： 在搜索过程中，检测两个搜索方向是否相遇，即是否存在一个节点同时被正向搜索和反向搜索访问到。
- 路径构建： 当两个搜索方向相遇时，将正向搜索和反向搜索的路径连接起来，形成完整的从起始节点到目标节点的路径。
代码分析与改进
原代码存在的主要问题在于：
- 单一搜索树： 使用同一个 searchTreeParentByChild 存储正向和反向搜索的父节点信息，导致方向混乱，无法正确构建完整路径。
- 反向搜索方向错误： 反向搜索时，应该记录子节点到父节点的关系，但原代码中 searchTreeParentByChild.put(curEnd, e.to()); 记录的是父节点到子节点的关系，方向错误。
- 路径构建不完整： 代码只检测到相遇点，但没有实际构建从起始点到终点的完整路径。
以下是改进后的代码示例，使用两个独立的搜索树分别记录正向和反向搜索的路径信息：
立即学习“Java免费学习笔记（深入）”；
import java.util.*;
public class BidirectionalSearch {
private final Graph graph;
private final Map forwardSearchTree = new HashMap<>();
private final Map backwardSearchTree = new HashMap<>();
public BidirectionalSearch(Graph graph) {
this.graph = graph;
}
public List findPath(Vertex start, Vertex end) {
if (!graph.vertices().containsAll(List.of(start, end))) {
throw new IllegalArgumentException("start or stop vertices not from this graph");
}
if (start.equals(end)) {
return List.of(start);
}
forwardSearchTree.clear();
backwardSearchTree.clear();
Queue forwardQueue = new ArrayDeque<>();
Queue backwardQueue = new ArrayDeque<>();
forwardQueue.add(start);
backwardQueue.add(end);
forwardSearchTree.put(start, null);
backwardSearchTree.put(end, null);
Vertex meetNode = null;
while (!forwardQueue.isEmpty() && !backwardQueue.isEmpty()) {
Vertex forwardNode = forwardQueue.poll();
if (expandForward(forwardNode, forwardQueue)) {
meetNode = findIntersection(forwardSearchTree.keySet(), backwardSearchTree.keySet());
if (meetNode != null) break;
}
Vertex backwardNode = backwardQueue.poll();
if (expandBackward(backwardNode, backwardQueue)) {
meetNode = findIntersection(forwardSearchTree.keySet(), backwardSearchTree.keySet());
if (meetNode != null) break;
}
}
if (meetNode == null) {
return null; // No path found
}
return constructPath(start, end, meetNode);
}
private boolean expandForward(Vertex node, Queue queue) {
for (Edge edge : node.edges()) {
Vertex neighbor = edge.to();
if (!forwardSearchTree.containsKey(neighbor)) {
forwardSearchTree.put(neighbor, node);
queue.add(neighbor);
return true;
}
}
return false;
}
private boolean expandBackward(Vertex node, Queue queue) {
for (Edge edge : graph.getIncomingEdges(node)) { // Assuming you have a method to get incoming edges
Vertex neighbor = edge.from();
if (!backwardSearchTree.containsKey(neighbor)) {
backwardSearchTree.put(neighbor, node);
queue.add(neighbor);
return true;
}
}
return false;
}
private Vertex findIntersection(Set forwardSet, Set backwardSet) {
for (Vertex vertex : forwardSet) {
if (backwardSet.contains(vertex)) {
return vertex;
}
}
return null;
}
private List constructPath(Vertex start, Vertex end, Vertex meetNode) {
List forwardPath = new ArrayList<>();
Vertex current = meetNode;
while (current != null) {
forwardPath.add(current);
current = forwardSearchTree.get(current);
}
Collections.reverse(forwardPath);
List backwardPath = new ArrayList<>();
current = meetNode;
while (current != null) {
backwardPath.add(current);
current = backwardSearchTree.get(current);
}
// Remove the meeting node from the backward path to avoid duplication
backwardPath.remove(0);
forwardPath.addAll(backwardPath);
return forwardPath;
}
// Assuming you have a Graph class, Vertex class, and Edge class defined
// and a method in Graph class to get incoming edges of a vertex.
interface Graph {
Set vertices();
List getIncomingEdges(Vertex vertex);
}
interface Vertex {
List edges();
}
interface Edge {
Vertex to();
Vertex from();
}
} 代码解释：
- forwardSearchTree 和 backwardSearchTree： 分别用于存储正向和反向搜索的父节点信息。
- expandForward 和 expandBackward： 分别进行正向和反向搜索，并将父子关系存储在对应的搜索树中。注意 expandBackward 函数需要获取节点的入边 (incoming edges) ，这需要 Graph 类提供相应的方法。
- findIntersection： 查找正向和反向搜索树的交集，即相遇节点。
- constructPath： 根据正向和反向搜索树，构建从起始点到终点的完整路径。 首先，分别从相遇节点回溯到起始节点和终点，构建两条路径。 然后，将两条路径连接起来，形成完整路径。注意，需要反转从起始节点到相遇节点的路径，并移除从相遇节点到终点路径中的相遇节点，避免重复。
注意事项：
- 确保 Graph 类提供获取节点入边的方法，以便进行反向搜索。
- Vertex 和 Edge 接口需要根据实际情况进行实现。
- 如果图中存在多个路径，该算法找到的是其中一条路径。
- 在实际应用中，可以根据具体需求对算法进行优化，例如使用启发式函数来指导搜索方向。
总结
双向路径搜索是一种有效的路径搜索算法，通过同时从起始点和终点进行搜索，可以显著提高搜索效率。 在实现双向路径搜索时，需要注意维护两个独立的搜索树，并正确构建从相遇点到起始点和终点的路径。 通过本文的讲解和代码示例，相信您能够更好地理解和应用双向路径搜索算法。
