本文深入探讨了Java中双向路径搜索算法的实现，旨在通过两个方向同时搜索来提高效率。我们将分析一个常见的实现错误，即使用单个父子映射来记录双向路径，并提供一个修正后的策略，包括使用独立的父节点映射和正确的路径重构方法，以确保算法的正确性和完整性。
双向搜索算法概述
双向搜索（bidirectional search）是一种图搜索算法，旨在寻找两个节点（起点和终点）之间的最短路径。与传统的单向搜索（如bfs或dfs）不同，双向搜索同时从起点和终点开始进行搜索，当两个搜索前沿相遇时，算法终止。这种方法通常可以显著减少需要探索的节点数量，因为搜索空间以两个方向的“半球”形式扩展，其交点通常比单个“全球”的面积小得多，从而提高搜索效率。
其核心思想是：
- 从起点S开始一个前向搜索（Forward Search）。
- 从终点T开始一个后向搜索（Backward Search）。
- 当两个搜索过程在某个节点M相遇时，即M同时被前向搜索和后向搜索访问到，则找到了一条从S到T的路径。这条路径由S到M的前向路径段和M到T的后向路径段（反向）组成。
初始实现的问题分析
在提供的java实现中，尝试使用双向搜索来构建路径。代码片段如下：
public BidirectionalSearch buildSearchTree(Vertex start, Vertex end) { // ... 参数校验 ... searchTreeParentByChild.clear(); // 单个map Queue<Vertex> unvisitedVertexQueueFromStart = new ArrayDeque<>(); Queue<Vertex> unvisitedVertexQueueFromEnd = new ArrayDeque<>(); unvisitedVertexQueueFromStart.add(start); unvisitedVertexQueueFromEnd.add(end); searchTreeParentByChild.put(start, null); // 前向搜索的起点 while (!unvisitedVertexQueueFromStart.isEmpty() && !unvisitedVertexQueueFromEnd.isEmpty()) { // 前向搜索部分 var curStart = unvisitedVertexQueueFromStart.poll(); for (var e : curStart.edges()) { if (!searchTreeParentByChild.containsKey(e.to())) { searchTreeParentByChild.put(e.to(), curStart); // 记录前向路径：e.to()的父节点是curStart unvisitedVertexQueueFromStart.add(e.to()); } } var intersection = curStart.edges().stream() .map(Edge::to) .filter(unvisitedVertexQueueFromEnd::contains) // 检查交集 .findAny(); if (intersection.isPresent()) return this; // 后向搜索部分 var curEnd = unvisitedVertexQueueFromEnd.poll(); for (var e : curEnd.edges()) { if (!searchTreeParentByChild.containsValue(e.to())) { // 错误：这里应该是containsKey searchTreeParentByChild.put(curEnd, e.to()); // 错误：记录后向路径的方式 unvisitedVertexQueueFromEnd.add(e.to()); } } intersection = curEnd.edges().stream() .map(Edge::to) .filter(unvisitedVertexQueueFromStart::contains) // 检查交集 .findAny(); if (intersection.isPresent()) return this; } return this; }
该实现存在两个主要问题：
-
单一父子映射的滥用： searchTreeParentByChild 被用于同时记录前向搜索和后向搜索的父子关系。
立即学习“Java免费学习笔记（深入）”；
- 前向搜索 searchTreeParentByChild.put(e.to(), curStart); 记录的是 子节点 -> 父节点 的关系（从start到e.to()）。
- 后向搜索 searchTreeParentByChild.put(curEnd, e.to()); 记录的是 curEnd -> e.to()。如果e.to()是curEnd的邻居，且我们希望构建从end到curEnd的路径，那么e.to()应该是curEnd的父节点。但这里的键值对是curEnd作为键，e.to()作为值，这实际上是在说curEnd是e.to()的父节点，与前向搜索的语义相同，但方向相反。更严重的是，它会覆盖或混淆前向搜索已经记录的父子关系，导致路径无法正确重构。
- searchTreeParentByChild.containsValue(e.to()) 这里的检查也是错误的，应该检查containsKey(e.to())来判断e.to()是否已经被后向搜索访问过。
-
路径重构缺失： 即使找到了交点，当前代码也只是简单地 return this;，并没有提供任何机制来从 searchTreeParentByChild 中提取完整的路径。由于映射被混用，即便尝试提取，也只会得到不完整的或错误的结果。
修正后的双向搜索实现策略
为了正确实现双向搜索并重构完整路径，我们需要：
-
使用两个独立的父节点映射：
- Map<Vertex, Vertex> parentFromStart; 用于记录从start出发的前向搜索路径中，每个节点的前一个节点。
- Map<Vertex, Vertex> parentFromEnd; 用于记录从end出发的后向搜索路径中，每个节点的前一个节点。
-
正确的交集判断： 在任一搜索步骤中，如果发现当前访问到的节点已经被另一个方向的搜索访问过，则找到了交点。
-
路径重构： 一旦找到交点，结合两个父节点映射来构建完整路径。
示例代码：修正后的 buildSearchTree 方法
import java.util.*; // 假设 Vertex 和 Edge 类已定义如下： class Vertex { String name; List<Edge> edges; // 出边列表，对于无向图，通常双向添加 // 构造函数、equals、hashCode、toString 等 public Vertex(String name) { this.name = name; this.edges = new ArrayList<>(); } public List<Edge> edges() { return edges; } public void addEdge(Edge edge) { this.edges.add(edge); } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Vertex vertex = (Vertex) o; return Objects.equals(name, vertex.name); } @Override public int hashCode() { return Objects.hash(name); } @Override public String toString() { return name; } } class Edge { Vertex from; Vertex to; int weight; // 构造函数、getter等 public Edge(Vertex from, Vertex to, int weight) { this.from = from; this.to = to; this.weight = weight; } public Vertex from() { return from; } public Vertex to() { return to; } public int weight() { return weight; } } // 假设 Graph 类已定义 class Graph { Set<Vertex> vertices; // 构造函数、添加节点、添加边等 public Graph() { this.vertices = new HashSet<>(); } public void addVertex(Vertex v) { vertices.add(v); } public Set<Vertex> vertices() { return vertices; } } public class BidirectionalSearcher { private final Graph graph; public BidirectionalSearcher(Graph graph) { this.graph = graph; } /** * 执行双向搜索并返回从起点到终点的路径。 * * @param start 路径起点 * @param end 路径终点 * @return 包含路径上所有顶点的列表，如果不存在路径则返回空列表。 * @throws IllegalArgumentException 如果起点或终点不在图中。 */ public List<Vertex> findPath(Vertex start, Vertex end) { if (!graph.vertices().containsAll(List.of(start, end))) { throw new IllegalArgumentException("起点或终点不在图中。"); } if (start.equals(end)) { return List.of(start); // 起点和终点相同，路径就是自身 } // 记录前向搜索的父节点：child -> parent Map<Vertex, Vertex> parentFromStart = new HashMap<>(); // 记录后向搜索的父节点：child -> parent Map<Vertex, Vertex> parentFromEnd = new HashMap<>(); // 前向搜索队列 Queue<Vertex> queueFromStart = new ArrayDeque<>(); // 后向搜索队列 Queue<Vertex> queueFromEnd = new ArrayDeque<>(); // 初始化前向搜索 queueFromStart.add(start); parentFromStart.put(start, null); // 起点没有父节点 // 初始化后向搜索 queueFromEnd.add(end); parentFromEnd.put(end, null); // 终点没有父节点 Vertex meetingPoint = null; // 记录相遇点 while (!queueFromStart.isEmpty() && !queueFromEnd.isEmpty() && meetingPoint == null) { // 执行前向搜索一步 meetingPoint = searchStep(queueFromStart, parentFromStart, parentFromEnd); if (meetingPoint != null) break; // 执行后向搜索一步 meetingPoint = searchStep(queueFromEnd, parentFromEnd, parentFromStart); if (meetingPoint != null) break; } if (meetingPoint == null) { return List.of(); // 未找到路径 } // 重构路径 return reconstructPath(start, end, meetingPoint, parentFromStart, parentFromEnd); } /** * 单步搜索逻辑，用于前向或后向搜索。 * * @param currentQueue 当前搜索方向的队列 * @param currentParents 当前搜索方向的父节点映射 (child -> parent) * @param otherParents 另一个搜索方向的父节点映射 (child -> parent) * @return 如果找到交点则返回交点Vertex，否则返回null */ private Vertex searchStep(Queue<Vertex> currentQueue, Map<Vertex, Vertex> currentParents, Map<Vertex, Vertex> otherParents) { if (currentQueue.isEmpty()) { return null; } Vertex current = currentQueue.poll(); // 遍历当前节点的邻居 for (Edge edge : current.edges()) { Vertex neighbor = edge.to(); // 假设边是 from -> to // 如果邻居未被当前搜索方向访问过 if (!currentParents.containsKey(neighbor)) { currentParents.put(neighbor, current); // 记录父节点 currentQueue.add(neighbor); // 检查是否与另一个搜索方向相遇 if (otherParents.containsKey(neighbor)) { return neighbor; // 找到交点 } } } return null; } /** * 从两个父节点映射和交点重构完整路径。 * * @param start 起点 * @param end 终点 * @param meetingPoint 相遇点 * @param parentFromStart 前向搜索的父节点映射 * @param parentFromEnd 后向搜索的父节点映射 * @return 完整的路径列表 */ private List<Vertex> reconstructPath(Vertex start, Vertex end, Vertex meetingPoint, Map<Vertex, Vertex> parentFromStart, Map<Vertex, Vertex> parentFromEnd) { List<Vertex> path = new LinkedList<>(); // 使用 LinkedList 便于在头部
评论（已关闭）
评论已关闭