编辑“︁树搜索算法”︁

{{DISPLAYTITLE:树搜索算法}}  
'''树搜索算法'''是计算机科学中用于在[[树 (数据结构)|树结构]]中查找特定节点或路径的一类算法，广泛应用于人工智能、数据库系统和网络路由等领域。本文将系统介绍基础与进阶的树搜索方法，包括深度优先搜索（DFS）、广度优先搜索（BFS）及其变体，并提供代码实现与案例分析。

== 概述 ==  
树搜索算法的核心目标是通过遍历树的节点，找到满足特定条件的解。根据搜索策略的不同，主要分为两类：  
* '''盲目搜索'''（如DFS、BFS）：不利用目标信息，按固定规则遍历。  
* '''启发式搜索'''（如A*算法）：利用启发函数指导搜索方向，提高效率。  

== 基础算法 ==  

=== 深度优先搜索（DFS） ===  
DFS沿树的深度方向优先遍历，直到叶子节点再回溯。适合解决路径存在性问题。  

==== 递归实现 ====  
<syntaxhighlight lang="python">  
def dfs(node, target):  
    if node is None:  
        return False  
    if node.value == target:  
        return True  
    return dfs(node.left, target) or dfs(node.right, target)  
</syntaxhighlight>  

'''输入'''：二叉树根节点和目标值  
'''输出'''：布尔值（是否找到目标）  

=== 广度优先搜索（BFS） ===  
BFS按层级遍历，使用队列实现。适合寻找最短路径。  

==== 队列实现 ====  
<syntaxhighlight lang="python">  
from collections import deque  

def bfs(root, target):  
    queue = deque([root])  
    while queue:  
        node = queue.popleft()  
        if node.value == target:  
            return True  
        if node.left:  
            queue.append(node.left)  
        if node.right:  
            queue.append(node.right)  
    return False  
</syntaxhighlight>  

== 进阶算法 ==  

=== 启发式搜索（A*算法） ===  
结合路径成本与启发式函数<math>h(n)</math>，优先扩展最有希望的节点。  

<mermaid>  
graph TD  
    A[Start] -->|g=0, h=5| B(("Node (f=5)"))  
    B -->|g=1, h=3| C(("Goal (f=4)"))  
    B -->|g=2, h=4| D(("Node (f=6)"))  
</mermaid>  

'''公式'''：<math>f(n) = g(n) + h(n)</math>  
其中<math>g(n)</math>为实际成本，<math>h(n)</math>为预估成本。  

== 应用案例 ==  
'''案例：迷宫求解'''  
使用DFS和BFS在二维网格中寻找出口路径：  
* DFS可能找到非最短路径但内存占用低。  
* BFS保证找到最短路径但需更多内存。  

== 性能对比 ==  
{| class="wikitable"  
|+ 时间复杂度与空间复杂度  
! 算法 !! 时间复杂度 !! 空间复杂度  
|-  
| DFS || O(b^d) || O(d)  
|-  
| BFS || O(b^d) || O(b^d)  
|}  
* <math>b</math>：分支因子，<math>d</math>：目标深度  

== 总结 ==  
树搜索算法的选择需权衡问题需求与资源限制。初学者应从DFS/BFS入手，进阶者可探索启发式方法如A*或IDA*。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:搜索算法]]