本文旨在帮助开发者理解和实现双向路径搜索算法。通过分析常见的实现错误，并提供改进方案，本文将详细介绍如何使用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 集合来记录已经访问过的节点。
总结
双向路径搜索是一种强大的图搜索算法，可以有效地找到起点和终点之间的路径。 通过使用两个独立的搜索树，并正确地构建和合并路径，可以避免常见的实现错误，获得正确的搜索结果。 在实际应用中，需要根据图的结构和性能需求，对算法进行适当的优化。
评论（已关闭）
评论已关闭