17370845950

新闻动态

Java双向搜索路径算法实现与常见错误解析

本文深入探讨了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 unvisitedVertexQueueFromStart = new ArrayDeque<>();
    Queue 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 被用于同时记录前向搜索和后向搜索的父子关系。
- 前向搜索 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 parentFromStart; 用于记录从start出发的前向搜索路径中，每个节点的前一个节点。
- Map parentFromEnd; 用于记录从end出发的后向搜索路径中，每个节点的前一个节点。
正确的交集判断： 在任一搜索步骤中，如果发现当前访问到的节点已经被另一个方向的搜索访问过，则找到了交点。
路径重构： 一旦找到交点，结合两个父节点映射来构建完整路径。

示例代码：修正后的 buildSearchTree 方法

import java.util.*;

// 假设 Vertex 和 Edge 类已定义如下：
class Vertex {
    String name;
    List edges; // 出边列表，对于无向图，通常双向添加
    // 构造函数、equals、hashCode、toString 等

    public Vertex(String name) {
        this.name = name;
        this.edges = new ArrayList<>();
    }

    public List 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 vertices;
    // 构造函数、添加节点、添加边等

    public Graph() {
        this.vertices = new HashSet<>();
    }

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

    public Set 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 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 parentFromStart = new HashMap<>();
        // 记录后向搜索的父节点：child -> parent
        Map parentFromEnd = new HashMap<>();

        // 前向搜索队列
        Queue queueFromStart = new ArrayDeque<>();
        // 后向搜索队列
        Queue 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 currentQueue,
                              Map currentParents,
                              Map 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 reconstructPath(Vertex start, Vertex end, Vertex meetingPoint,
                                         Map parentFromStart,
                                         Map parentFromEnd) {
        List path = new LinkedList<>(); // 使用 LinkedList 便于在头部

17370845950

双向搜索算法概述

初始实现的问题分析

修正后的双向搜索实现策略

示例代码：修正后的 buildSearchTree 方法

关于我们

服务项目

广告推广

案例欣赏