UCB CS188:Pacman Agent(1)

探索基础搜索算法：DFS、BFS与UCS

在人工智能和计算机科学领域，搜索算法是解决许多问题的核心工具。本文将深入探讨三种经典搜索算法：深度优先搜索（DFS）、广度优先搜索（BFS）和均匀成本搜索（UCS），并结合具体的Python代码实现来分析它们的工作原理和适用场景。

1 算法原理概述

1.1 深度优先搜索（DFS）

深度优先搜索采用后进先出（LIFO）的策略，优先探索分支的最深处。它使用栈（Stack） 结构来存储待探索的节点，适合寻找任意解或拓扑排序。

1.2 广度优先搜索（BFS）

广度优先搜索采用先进先出（FIFO）的策略，按层次逐步扩展搜索。它使用队列（Queue） 结构来存储待探索的节点，能确保找到最短路径（在无权图中）。

1.3 均匀成本搜索（UCS）

均匀成本搜索是BFS的推广，用于加权图。它优先扩展当前路径成本最低的节点，使用优先队列（Priority Queue） 结构，确保找到成本最低的路径。

2 代码实现分析

以下代码实现了上述三种搜索算法，均采用图搜索方式（避免重复访问节点）。

2.1 深度优先搜索（DFS）实现

def depthFirstSearch(problem: SearchProblem) -> List[Directions]:
    """
    Search the deepest nodes in the search tree first.
    Your search algorithm needs to return a list of actions that reaches the goal. 
    Make sure to implement a graph search algorithm.
    """
    frontier = util.Stack()  # 使用栈实现DFS
    searched = set()         # 记录已访问节点，避免重复
    # 初始状态：起点、空动作序列、初始成本0
    frontier.push((problem.getStartState(), [], 0))

    while not frontier.isEmpty():
        state, actions, cost = frontier.pop()
        
        if problem.isGoalState(state):  # 目标测试
            return actions
            
        if state not in searched:        # 仅处理未访问节点
            searched.add(state)
            successors = problem.getSuccessors(state)
            for next_state, action, step_cost in successors:
                if next_state not in searched:  # 图搜索：忽略已访问节点
                    # 新动作序列 = 当前动作序列 + 新动作
                    new_actions = actions + [action]
                    new_cost = cost + step_cost
                    frontier.push((next_state, new_actions, new_cost))
                    
    return []  # 未找到路径时返回空列表

关键点： - 数据结构：使用util.Stack()（栈），后进先出（LIFO）。 - 状态记录：searched集合记录已扩展节点，避免重复访问和循环（图搜索）。 - 路径记录：在节点中存储actions列表，记录从起点到当前节点的动作序列。 - 扩展规则：对于每个节点的后继节点，若未访问，则计算新路径的成本和动作序列，并压入栈中。

2.2 广度优先搜索（BFS）实现

def breadthFirstSearch(problem: SearchProblem) -> List[Directions]:
    """Search the shallowest nodes in the search tree first."""
    frontier = util.Queue()  # 使用队列实现BFS
    searched = set()
    frontier.push((problem.getStartState(), [], 0))

    while not frontier.isEmpty():
        state, actions, cost = frontier.pop()
        
        if problem.isGoalState(state):
            return actions
            
        if state not in searched:
            searched.add(state)
            successors = problem.getSuccessors(state)
            for next_state, action, step_cost in successors:
                if next_state not in searched:
                    new_actions = actions + [action]
                    new_cost = cost + step_cost
                    frontier.push((next_state, new_actions, new_cost))
                    
    return []

关键点： - 数据结构：使用util.Queue()（队列），先进先出（FIFO）。 - 完备性与最优性：在无权图中，BFS是完备的，且总能找到最短路径（最少步数）。 - 扩展顺序：先扩展深度最浅的节点，确保按层次遍历。

2.3 均匀成本搜索（UCS）实现

def uniformCostSearch(problem: SearchProblem) -> List[Directions]:
    """Search the node of least total cost first."""
    frontier = util.PriorityQueue()  # 使用优先队列实现UCS
    searched = set()
    # 初始状态按成本0优先级入队
    frontier.push((problem.getStartState(), [], 0), 0)

    while not frontier.isEmpty():
        state, actions, cost = frontier.pop()
        
        if problem.isGoalState(state):
            return actions
            
        if state not in searched:
            searched.add(state)
            successors = problem.getSuccessors(state)
            for next_state, action, step_cost in successors:
                if next_state not in searched:
                    new_actions = actions + [action]
                    new_cost = cost + step_cost  # 累计成本
                    # 以新成本作为优先级入队
                    frontier.push((next_state, new_actions, new_cost), new_cost)
                    
    return []

关键点： - 数据结构：使用util.PriorityQueue()（优先队列），按路径成本排序。 - 成本敏感：每次扩展累计成本new_cost最低的节点，确保找到成本最低的路径。 - 最优性：在有权图中，UCS是完备的，且总能找到成本最低的路径（当成本非负时）。

3 三种算法的对比与应用

为了更直观地比较这三种算法，以下是它们在数据结构、扩展顺序、最优性等方面的差异：

特征	深度优先搜索（DFS）	广度优先搜索（BFS）	均匀成本搜索（UCS）
数据结构	栈（Stack）	队列（Queue）	优先队列（Priority Queue）
扩展顺序	最深节点	最浅节点	最小成本节点
最优性	否（可能找到非最短路径）	是（无权图最短路径）	是（加权图最低成本路径）
完备性	是（有限图）	是（有限图）	是（有限图，成本≥0）
空间复杂度	O(bm)	O(b^d)	O(b^d)
时间复杂度	O(b^m)	O(b^d)	O(b^d)

符号说明：b为分支因子，d为解所在深度，m为最大深度。

3.1 实际应用场景

• DFS：适用于解空间较深、需快速找到一个可行解的场景，如迷宫求解、拓扑排序。
• BFS：适用于寻找最短路径（步数），如社交网络中的最短关系链、迷宫的最短出口路径。
• UCS：适用于考虑行动成本的场景，如地图导航中的最短行驶时间、资源消耗最小化。

4 总结

深度优先搜索、广度优先搜索和均匀成本搜索是图搜索中最基础的算法。它们通过不同的数据结构和控制策略，实现了各自优势的搜索策略。在实际应用中，根据问题需求（如是否需要最优解、解的空间特征、是否有权重等）选择合适的算法至关重要。理解这些算法的原理和实现，是构建更复杂人工智能系统（如A*搜索、蒙特卡洛树搜索等）的坚实基础。

提示：以上代码均基于图搜索（避免重复访问），若采用树搜索（允许重复访问），需移除searched集合的相关操作，但可能陷入循环。