第五节课作业：搜索算法

第五节课 搜索算法

作业题目

题目：给出广度优先搜索、深度优先搜索、回溯法、代价一致搜索四个算法的伪代码。可以从基准算法出发，修改insert()函数，说明每个算法的insert函数的实现差异。

基准算法

所有搜索算法都遵循相同的基准算法框架，唯一的关键差异在于INSERT函数的实现方式。

path <- (s0), Fringe <- ϕ;

if(GOAL(s0)==T) then
    return path=(s0);
end

INSERT(s0, Fringe);

while T do
    if empty(Fringe)==T then
        return failure;
    end
    N <- REMOVE(Fringe);
    s <- STATE(N);
    update path;
    foreach s' in succ(s) do
        if GOAL(s')==T then
            return(path, s');
        end
        INSERT(s', Fringe);
    end
end

算法说明

  • path：记录从起点到当前节点的路径
  • Fringe：待探索节点的集合（边界）
  • INSERT：将节点插入Fringe的操作
  • REMOVE：从Fringe中取出节点的操作
  • GOAL：判断是否到达目标状态
  • succ(s)：获取状态s的所有后继状态

1. 广度优先搜索（BFS）

修改要点

Fringe使用队列（FIFO），INSERT函数实现为ENQUEUE操作

path <- (s0), Fringe <- ϕ;

if(GOAL(s0)==T) then
    return path=(s0);
end

INSERT(s0, Fringe);  // INSERT_BFS: ENQUEUE操作

while T do
    if empty(Fringe)==T then
        return failure;
    end
    N <- REMOVE(Fringe);  // DEQUEUE操作
    s <- STATE(N);
    update path;
    foreach s' in succ(s) do
        if GOAL(s')==T then
            return(path, s');
        end
        INSERT(s', Fringe);  // INSERT_BFS: ENQUEUE操作
    end
end

INSERT_BFS函数实现

function INSERT_BFS(node, Fringe):
    // 队列操作：插入到尾部（FIFO）
    Fringe.append(node);  // 将新节点添加到队列末尾
end

特点

  • 先进先出：最先加入的节点最先被探索
  • 层次遍历：按照距离起点的层次逐层探索
  • 最短路径：在无权图中保证找到最短路径
  • 空间复杂度高：需要存储所有同层节点

2. 深度优先搜索（DFS）

修改要点

Fringe使用栈（LIFO），INSERT函数实现为PUSH操作

path <- (s0), Fringe <- ϕ;

if(GOAL(s0)==T) then
    return path=(s0);
end

INSERT(s0, Fringe);  // INSERT_DFS: PUSH操作

while T do
    if empty(Fringe)==T then
        return failure;
    end
    N <- REMOVE(Fringe);  // POP操作
    s <- STATE(N);
    update path;
    foreach s' in succ(s) do
        if GOAL(s')==T then
            return(path, s');
        end
        INSERT(s', Fringe);  // INSERT_DFS: PUSH操作
    end
end

INSERT_DFS函数实现

function INSERT_DFS(node, Fringe):
    // 栈操作：压入栈顶（LIFO）
    Fringe.push(node);  // 将新节点压入栈顶
end

特点

  • 后进先出：最后加入的节点最先被探索
  • 深度优先：沿着一条路径尽可能深入探索
  • 空间复杂度低：只需存储当前路径上的节点
  • 可能陷入死循环：在有环图中需要记录访问状态

3. 回溯法

修改要点

不使用Fringe数据结构，通过递归调用实现INSERT功能

path <- (s0), Fringe <- ϕ;

if(GOAL(s0)==T) then
    return path=(s0);
end

// 回溯法不需要显式的Fringe操作，直接使用递归

function BACKTRACK(s, path):
    if GOAL(s)==T then
        return(path, s);
    end
    foreach s' in succ(s) do
        new_path = path + (s');
        // INSERT_BACKTRACK: 递归调用
        result = BACKTRACK(s', new_path);
        if result != failure then
            return result;
        end
    end
    return failure;  // 相当于从栈中弹出（回溯）
end

return BACKTRACK(s0, (s0));

INSERT_BACKTRACK函数实现

function INSERT_BACKTRACK(node, path):
    // 递归操作：通过函数调用实现"插入"
    return BACKTRACK(node, path);  // 将节点"插入"到递归调用栈中
end

特点

  • 递归实现：利用函数调用栈代替显式的数据结构
  • 自动回溯：递归返回时自动回到上一层
  • 深度优先：本质上是DFS的递归实现
  • 代码简洁：不需要显式管理Fringe

4. 代价一致搜索（Uniform Cost Search）

修改要点

Fringe使用优先队列，INSERT函数按代价排序插入

path <- (s0), Fringe <- ϕ, costs <- ϕ;

if(GOAL(s0)==T) then
    return path=(s0), cost=0;
end

INSERT(s0, Fringe), INSERT(0, costs);  // INSERT_UNIFORM: 按代价排序插入

while T do
    if empty(Fringe)==T then
        return failure;
    end
    N <- REMOVE(Fringe);  // 移除代价最小节点
    cost <- REMOVE(costs);
    s <- STATE(N);
    update path;
    foreach s' in succ(s) with cost c do
        new_cost = cost + c;
        if GOAL(s')==T then
            return(path, s'), new_cost;
        end
        INSERT(s', Fringe), INSERT(new_cost, costs);  // INSERT_UNIFORM: 按new_cost插入
    end
end

INSERT_UNIFORM函数实现

function INSERT_UNIFORM(node, Fringe, cost):
    // 优先队列操作：按代价排序插入
    Fringe.insert_with_priority(node, cost);  // 按代价大小插入到合适位置
end

特点

  • 最小代价优先：总是探索当前代价最小的节点
  • 最优路径：保证找到代价最小的路径
  • 适用于加权图：考虑边的权重
  • 类似Dijkstra算法：是Dijkstra算法的一种实现

各算法INSERT函数实现差异总结

算法 数据结构 INSERT函数调用方式 实现原理
基准算法 通用结构 INSERT(s', Fringe) 通用插入操作
BFS 队列(FIFO) INSERT_BFS(s', Fringe) 插入队列尾部（先进先出）
DFS 栈(LIFO) INSERT_DFS(s', Fringe) 压入栈顶（后进先出）
回溯法 递归栈 INSERT_BACKTRACK(s', path) 递归调用（深度优先）
代价一致 优先队列 INSERT_UNIFORM(s', Fringe, new_cost) 按代价排序插入（最小代价优先）

算法对比分析

BFS

优点

  • 保证找到最短路径（无权图）
  • 完备性好

缺点

  • 空间复杂度高
  • 需要存储大量节点

DFS

优点

  • 空间复杂度低
  • 实现简单

缺点

  • 不保证最短路径
  • 可能陷入死循环

回溯法

优点

  • 代码简洁
  • 自动回溯

缺点

  • 递归深度限制
  • 本质上是DFS

代价一致

优点

  • 保证最优路径
  • 适用于加权图

缺点

  • 时间复杂度较高
  • 需要维护优先队列

核心结论

所有搜索算法都遵循相同的基准算法框架，唯一的关键差异在于INSERT函数的实现方式。通过修改INSERT函数就能实现不同的搜索策略：

  • BFS：队列（FIFO）→ 层次遍历
  • DFS：栈（LIFO）→ 深度优先
  • 回溯法：递归栈 → 自动回溯
  • 代价一致：优先队列 → 最优路径

这种统一的框架体现了算法设计的优雅性，通过简单的数据结构变化就能实现不同的搜索行为。

上一个作业 返回主页 下一个作业