如何用Python实现迭代加深广度优先搜索找未知树的最短路径？

问题背景 #

需要用Python实现迭代加深广度优先搜索（Iterative Deepening Breadth-First Search），从已知根节点找到到指定目标节点的最短路径，搜索深度上限设为5个顶点。存在两个特殊约束：

• 树结构完全未知：仅知晓根节点和目标节点存在，每个节点可拥有0至多个子节点，根与目标的距离可能为1、5甚至10个顶点。
• 仅返回最短路径：找到目标后立即终止搜索，无需返回完整遍历顺序（例如示例树中，按字母顺序遍历应返回[Root, B, E, H, Target]）。

示例树：

解决方案 #

迭代加深BFS（IDBFS）结合了BFS的最短路径特性和DFS的空间高效性，非常适合这种未知结构的场景——无需预加载所有节点，而是逐步提升搜索深度，每次在当前深度限制内执行DFS，找到目标后立即返回路径。

实现思路 #

1. 分层递进搜索：从路径长度2（根+1个子节点）开始，依次尝试到路径长度5（5个顶点），每次在当前路径长度限制内做DFS。
2. 路径回溯：DFS过程中维护当前路径，遇到目标节点直接返回该路径；遍历完当前节点的子节点后回溯，尝试下一个分支。
3. 终止条件：超过当前设定的路径长度则停止递归；找到目标后立即终止所有搜索流程。
4. 动态获取子节点：需要实现一个get_children函数，用于获取当前节点的子节点（根据实际场景实现，比如API调用、数据库查询等）。

Python 代码实现 #

def iterative_deepening_bfs(root, target, max_path_nodes=5):
    def dfs(current_node, current_path, remaining_nodes):
        # 找到目标节点，返回当前路径
        if current_node == target:
            return current_path.copy()
        # 剩余可添加节点数为0，停止搜索
        if remaining_nodes == 0:
            return None
        # 按预设顺序遍历子节点（比如示例中的字母顺序）
        for child in get_children(current_node):
            current_path.append(child)
            result = dfs(child, current_path, remaining_nodes - 1)
            if result is not None:
                return result
            # 回溯，移除当前子节点，尝试下一个分支
            current_path.pop()
        return None

    # 尝试路径长度从2到max_path_nodes（包含）
    for path_length in range(2, max_path_nodes + 1):
        # 初始路径已有1个节点（root），剩余可添加path_length-1个节点
        path = dfs(root, [root], path_length - 1)
        if path is not None:
            return path
    # 达到最大路径节点数仍未找到目标
    return None

# 示例：根据实际节点结构实现子节点获取函数
def get_children(node):
    # 对应示例树的节点映射
    node_map = {
        "Root": ["A", "B"],
        "A": ["C", "D"],
        "B": ["E", "F"],
        "E": ["G", "H"],
        "H": ["Target"],
        "F": ["K", "L"]
        # 其他节点默认返回空列表
    }
    return node_map.get(node, [])

# 测试示例
if __name__ == "__main__":
    root = "Root"
    target = "Target"
    shortest_path = iterative_deepening_bfs(root, target)
    print(shortest_path)  # 输出: ['Root', 'B', 'E', 'H', 'Target']

关键说明 #

• 路径长度定义：max_path_nodes=5对应最多返回包含5个顶点的路径，与需求中的“深度上限设为5个顶点”匹配。
• 子节点遍历顺序：get_children返回的子节点顺序决定了搜索优先级（示例中是字母顺序），可根据实际需求调整。
• 空间效率：由于采用DFS回溯，无需存储整个层级的节点，仅需维护当前路径，适合未知结构的大场景。

内容的提问来源于stack exchange，提问作者jayp