本文旨在帮助开发者理解和实现双向路径搜索算法。通过分析常见的实现错误，并提供改进方案，本文将详细介绍如何使用Java构建高效的双向搜索树，并从搜索树中正确提取完整的路径信息，最终实现从起点到终点的完整路径搜索。
理解双向路径搜索
双向路径搜索是一种在图中寻找从起点到终点路径的优化算法。它同时从起点和终点开始搜索，当两个搜索方向相遇时，就找到了连接起点和终点的路径。相比于单向搜索，双向搜索通常能够更快地找到目标路径，尤其是在搜索空间较大的情况下。
常见的实现错误
原始代码中存在一些关键问题，导致无法正确构建和使用双向搜索树：
- 共享搜索树: 使用单一的 searchTreeParentByChild 存储两个方向的搜索结果是不正确的。因为两个方向的路径是从不同的起点构建，并且方向相反。使用同一个树结构无法区分路径的方向。
- 路径构建方向错误: searchTreeParentByChild 只能从子节点追溯到父节点，而无法反向查找。这导致无法从相遇点正确构建从起点到终点的完整路径。
- containsValue 的错误使用: 在 curEnd 的循环中，使用 searchTreeParentByChild.containsValue(e.to()) 来判断顶点是否被访问过是错误的。containsValue 用于检查 Map 中是否存在特定的值，而不是键。正确的做法是使用 containsKey(e.to())。
改进的实现方案
为了解决上述问题，我们需要进行以下改进：
立即学习“Java免费学习笔记（深入）”；
- 使用两个独立的搜索树: 为从起点和终点开始的搜索分别创建 searchTreeParentByChildFromStart 和 searchTreeParentByChildFromEnd。这两个 Map 分别存储从起点和从终点开始的搜索树。
- 正确的顶点访问检查: 使用 containsKey() 方法检查顶点是否已经被访问过。
- 完整路径构建: 当两个搜索方向相遇时，需要分别从相遇点向起点和终点追溯路径，然后将两条路径合并。
以下是改进后的 Java 代码示例：
import java.util.*;
public class BidirectionalSearch {
private final Graph graph;
private final Map<Vertex, Vertex> searchTreeParentByChildFromStart = new HashMap<>();
private final Map<Vertex, Vertex> searchTreeParentByChildFromEnd = new HashMap<>();
public BidirectionalSearch(Graph graph) {
this.graph = graph;
}
public BidirectionalSearch buildSearchTree(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 this;
searchTreeParentByChildFromStart.clear();
searchTreeParentByChildFromEnd.clear();
Queue<Vertex> unvisitedVertexQueueFromStart = new ArrayDeque<>();
Queue<Vertex> unvisitedVertexQueueFromEnd = new ArrayDeque<>();
unvisitedVertexQueueFromStart.add(start);
unvisitedVertexQueueFromEnd.add(end);
searchTreeParentByChildFromStart.put(start, null);
searchTreeParentByChildFromEnd.put(end, null);
Vertex intersectionVertex = null;
while (!unvisitedVertexQueueFromStart.isEmpty() && !unvisitedVertexQueueFromEnd.isEmpty()) {
Vertex curStart = unvisitedVertexQueueFromStart.poll();
for (Edge e : curStart.edges()) {
Vertex neighbor = e.to();
if (!searchTreeParentByChildFromStart.containsKey(neighbor)) {
searchTreeParentByChildFromStart.put(neighbor, curStart);
unvisitedVertexQueueFromStart.add(neighbor);
if (searchTreeParentByChildFromEnd.containsKey(neighbor)) {
intersectionVertex = neighbor;
break; // Found intersection
}
}
}
if (intersectionVertex != null) break;
Vertex curEnd = unvisitedVertexQueueFromEnd.poll();
for (Edge e : curEnd.edges()) {
Vertex neighbor = e.to();
if (!searchTreeParentByChildFromEnd.containsKey(neighbor)) {
searchTreeParentByChildFromEnd.put(neighbor, curEnd);
unvisitedVertexQueueFromEnd.add(neighbor);
if (searchTreeParentByChildFromStart.containsKey(neighbor)) {
intersectionVertex = neighbor;
break; // Found intersection
}
}
}
if (intersectionVertex != null) break;
}
return this;
}
public List<Vertex> getPath(Vertex start, Vertex end) {
buildSearchTree(start, end);
Vertex intersection = findIntersection(start, end);
if (intersection == null) {
return Collections.emptyList(); // No path found
}
List<Vertex> pathToIntersectionFromStart = buildPath(searchTreeParentByChildFromStart, intersection);
List<Vertex> pathToIntersectionFromEnd = buildPath(searchTreeParentByChildFromEnd, intersection);
Collections.reverse(pathToIntersectionFromEnd); // Reverse the end path
List<Vertex> fullPath = new ArrayList<>();
fullPath.addAll(pathToIntersectionFromStart);
fullPath.addAll(pathToIntersectionFromEnd.subList(1, pathToIntersectionFromEnd.size())); // Avoid duplicate intersection vertex
return fullPath;
}
private Vertex findIntersection(Vertex start, Vertex end) {
for (Vertex vertex : searchTreeParentByChildFromStart.keySet()) {
if (searchTreeParentByChildFromEnd.containsKey(vertex)) {
return vertex;
}
}
return null;
}
private List<Vertex> buildPath(Map<Vertex, Vertex> searchTree, Vertex intersection) {
List<Vertex> path = new LinkedList<>();
Vertex current = intersection;
while (current != null) {
path.add(0, current); // Add to the beginning to reverse the path
current = searchTree.get(current);
}
return path;
}
// Example Graph, Vertex and Edge classes (replace with your actual implementations)
static class Graph {
private final Set<Vertex> vertices = new HashSet<>();
public void addVertex(Vertex vertex) {
vertices.add(vertex);
}
public Set<Vertex> vertices() {
return vertices;
}
}
static class Vertex {
private final String name;
private final List<Edge> edges = new ArrayList<>();
public Vertex(String name) {
this.name = name;
}
public String getName() {
return name;
}
public void addEdge(Edge edge) {
edges.add(edge);
}
public List<Edge> edges() {
return edges;
}
@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);
}
}
static class Edge {
private final Vertex from;
private final Vertex to;
private final int weight;
public Edge(Vertex from, Vertex to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
public Vertex to() {
return to;
}
}
public static void main(String[] args) {
// Example Usage
Graph graph = new Graph();
Vertex start = new Vertex("A");
Vertex b = new Vertex("B");
Vertex c = new Vertex("C");
Vertex end = new Vertex("D");
graph.addVertex(start);
graph.addVertex(b);
graph.addVertex(c);
graph.addVertex(end);
start.addEdge(new Edge(start, b, 1));
b.addEdge(new Edge(b, c, 1));
c.addEdge(new Edge(c, end, 1));
end.addEdge(new Edge(end, c, 1));
BidirectionalSearch search = new BidirectionalSearch(graph);
List<Vertex> path = search.getPath(start, end);
if (!path.isEmpty()) {
System.out.println("Path found: ");
for (Vertex vertex : path) {
System.out.print(vertex.getName() + " ");
}
System.out.println();
} else {
System.out.println("No path found.");
}
}
}代码解释:
- searchTreeParentByChildFromStart 和 searchTreeParentByChildFromEnd：分别存储从起点和终点开始的搜索树，记录每个节点的父节点。
- getPath(Vertex start, Vertex end): 构建搜索树，找到两个方向相遇的顶点，然后分别构建从起点到相遇点和从终点到相遇点的路径，最后合并这两条路径。
- buildPath(Map<Vertex, Vertex> searchTree, Vertex intersection): 从相遇点开始，通过搜索树向上追溯到起点或终点，构建单向路径。
- findIntersection(Vertex start, Vertex end): 找到两个搜索树的相交顶点。
注意事项
- 图的表示: 上述代码示例中使用了简单的 Graph, Vertex 和 Edge 类。在实际应用中，你需要根据你的图的结构来调整这些类的实现。
- 性能优化: 双向搜索的性能高度依赖于图的结构。在某些情况下，单向搜索可能更有效。可以考虑使用启发式函数来指导搜索方向，进一步优化性能。
- 路径权重: 上述代码只关注是否存在路径，没有考虑路径的权重。如果需要找到最短路径，需要修改代码，在搜索过程中维护每个节点的距离信息，并使用合适的优先队列（例如，使用 PriorityQueue）来选择下一个要访问的节点。
- 环路处理: 在构建搜索树时，需要小心处理环路，避免无限循环。可以使用一个额外的 visited 集合来记录已经访问过的节点。
总结
双向路径搜索是一种强大的图搜索算法，可以有效地找到起点和终点之间的路径。 通过使用两个独立的搜索树，并正确地构建和合并路径，可以避免常见的实现错误，获得正确的搜索结果。 在实际应用中，需要根据图的结构和性能需求，对算法进行适当的优化。
