迭代加深搜索（图的路径查找）

package routine.suibi;
 
import java.util.*;
 
public class IterativeDeepeningSearch {
 
    // 图的节点类  
    static class Node {
        int id; // 节点编号  
        List<Node> neighbors; // 相邻节点列表  
 
        Node(int id) {
            this.id = id;
            this.neighbors = new ArrayList<>();
        }
 
        // 添加相邻节点  
        void addNeighbor(Node node) {
            neighbors.add(node);
        }
 
        @Override
        public String toString() {
            return "Node{" + "id=" + id + '}';
        }
    }
 
    // 路径类  
    static class Path {
        List<Node> nodes; // 路径上的节点列表  
        int depth; // 路径深度  
 
        Path(Node startNode) {
            this.nodes = new ArrayList<>();
            this.nodes.add(startNode);
            this.depth = 1;
        }
 
        // 添加节点到路径中  
        void addNode(Node node) {
            nodes.add(node);
            depth++;
        }
 
        // 获取路径上的最后一个节点  
        Node getLastNode() {
            return nodes.get(nodes.size() - 1);
        }
 
        @Override
        public String toString() {
            return "Path{" + "nodes=" + nodes + ", depth=" + depth + '}';
        }
    }
 
    // 迭代加深搜索算法  
    public static Path iterativeDeepeningSearch(Node start, Node goal) {
        int maxDepth = 0; // 初始化最大深度为0  
        while (true) {
            Path result = dfs(start, goal, maxDepth);
            if (result != null) {
                return result; // 找到路径，返回结果  
            }
            maxDepth++; // 增加最大深度限制，继续搜索  
            if (maxDepth > getMaxDepth(start, goal)) {
                break; // 超过最大可能深度，退出循环  
            }
        }
        return null; // 没有找到路径  
    }
 
    // 深度优先搜索辅助方法  
    private static Path dfs(Node current, Node goal, int maxDepth) {
        if (current.equals(goal)) {
            return new Path(current); // 到达目标节点，返回路径  
        }
        if (maxDepth <= 0) {
            return null; // 达到最大深度限制，返回null  
        }
 
        for (Node neighbor : current.neighbors) {
            Path result = dfs(neighbor, goal, maxDepth - 1); // 递归搜索相邻节点  
            if (result != null) {
                result.addNode(current); // 将当前节点添加到路径中  
                return result; // 返回找到的路径  
            }
        }
        return null; // 没有找到路径  
    }
 
    // 获取从起点到终点的最大可能深度（可选，用于提前退出循环）  
    private static int getMaxDepth(Node start, Node goal) {
        Queue<Node> queue = new LinkedList<>();
        Set<Node> visited = new HashSet<>();
        queue.add(start);
        visited.add(start);
        int depth = 0;
 
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node current = queue.poll();
                if (current.equals(goal)) {
                    return depth; // 找到目标节点，返回当前深度  
                }
                for (Node neighbor : current.neighbors) {
                    if (!visited.contains(neighbor)) {
                        queue.add(neighbor);
                        visited.add(neighbor);
                    }
                }
            }
            depth++;
        }
        return -1; // 没有找到目标节点，返回-1（理论上这种情况不会发生，因为图是连通的）  
    }
 
    public static void main(String[] args) {
        // 创建图的节点和边  
        Node A = new Node(1);
        Node B = new Node(2);
        Node C = new Node(3);
        Node D = new Node(4);
 
        // 添加边
        A.addNeighbor(B);
        A.addNeighbor(C);
        B.addNeighbor(C);
        B.addNeighbor(D);
        C.addNeighbor(D);
 
        // 执行迭代加深搜索
        Path path = iterativeDeepeningSearch(A, D);
 
        // 输出结果
        if (path != null) {
            System.out.println("找到路径: " + path);
        } else {
            System.out.println("没有找到路径");
        }
    }
}