双向搜索算法Java实现与路径解析

本文旨在帮助开发者理解和实现双向路径搜索算法。通过分析常见的实现错误，并提供改进方案，本文将详细介绍如何使用Java构建高效的双向搜索树，并从搜索树中正确提取完整的路径信息，最终实现从起点到终点的完整路径搜索。

理解双向路径搜索

双向路径搜索是一种在图中寻找从起点到终点路径的优化算法。它同时从起点和终点开始搜索，当两个搜索方向相遇时，就找到了连接起点和终点的路径。相比于单向搜索，双向搜索通常能够更快地找到目标路径，尤其是在搜索空间较大的情况下。

常见的实现错误

原始代码中存在一些关键问题，导致无法正确构建和使用双向搜索树：

1. 共享搜索树: 使用单一的 searchTreeParentByChild 存储两个方向的搜索结果是不正确的。因为两个方向的路径是从不同的起点构建，并且方向相反。使用同一个树结构无法区分路径的方向。
2. 路径构建方向错误: searchTreeParentByChild 只能从子节点追溯到父节点，而无法反向查找。这导致无法从相遇点正确构建从起点到终点的完整路径。
3. containsValue 的错误使用: 在 curEnd 的循环中，使用 searchTreeParentByChild.containsValue(e.to()) 来判断顶点是否被访问过是错误的。containsValue 用于检查 Map 中是否存在特定的值，而不是键。正确的做法是使用 containsKey(e.to())。

改进的实现方案

为了解决上述问题，我们需要进行以下改进：

1. 使用两个独立的搜索树: 为从起点和终点开始的搜索分别创建 searchTreeParentByChildFromStart 和 searchTreeParentByChildFromEnd。这两个 Map 分别存储从起点和从终点开始的搜索树。
2. 正确的顶点访问检查: 使用 containsKey() 方法检查顶点是否已经被访问过。
3. 完整路径构建: 当两个搜索方向相遇时，需要分别从相遇点向起点和终点追溯路径，然后将两条路径合并。

以下是改进后的 Java 代码示例：

import java.util.*;

public class BidirectionalSearch {

    private final Graph graph;
    private final Map searchTreeParentByChildFromStart = new HashMap<>();
    private final Map 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 unvisitedVertexQueueFromStart = new ArrayDeque<>();
        Queue 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 getPath(Vertex start, Vertex end) {
        buildSearchTree(start, end);
        Vertex intersection = findIntersection(start, end);

        if (intersection == null) {
            return Collections.emptyList(); // No path found
        }

        List pathToIntersectionFromStart = buildPath(searchTreeParentByChildFromStart, intersection);
        List pathToIntersectionFromEnd = buildPath(searchTreeParentByChildFromEnd, intersection);

        Collections.reverse(pathToIntersectionFromEnd); // Reverse the end path

        List 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 buildPath(Map searchTree, Vertex intersection) {
        List 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 vertices = new HashSet<>();

        public void addVertex(Vertex vertex) {
            vertices.add(vertex);
        }

        public Set vertices() {
            return vertices;
        }
    }

    static class Vertex {
        private final String name;
        private final List 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 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 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 searchTree, Vertex intersection): 从相遇点开始，通过搜索树向上追溯到起点或终点，构建单向路径。
• findIntersection(Vertex start, Vertex end): 找到两个搜索树的相交顶点。

注意事项

• 图的表示: 上述代码示例中使用了简单的 Graph, Vertex 和 Edge 类。在实际应用中，你需要根据你的图的结构来调整这些类的实现。
• 性能优化: 双向搜索的性能高度依赖于图的结构。在某些情况下，单向搜索可能更有效。可以考虑使用启发式函数来指导搜索方向，进一步优化性能。
• 路径权重: 上述代码只关注是否存在路径，没有考虑路径的权重。如果需要找到最短路径，需要修改代码，在搜索过程中维护每个节点的距离信息，并使用合适的优先队列（例如，使用 PriorityQueue）来选择下一个要访问的节点。
• 环路处理: 在构建搜索树时，需要小心处理环路，避免无限循环。可以使用一个额外的 visited 集合来记录已经访问过的节点。

总结

双向路径搜索是一种强大的图搜索算法，可以有效地找到起点和终点之间的路径。 通过使用两个独立的搜索树，并正确地构建和合并路径，可以避免常见的实现错误，获得正确的搜索结果。 在实际应用中，需要根据图的结构和性能需求，对算法进行适当的优化。