跳到主要内容

分治算法

分治把问题拆成哪两步？​

  • 分: 递归地把原问题拆成多个形式相同的子问题, 直到子问题足够小可直接求解;
  • 治: 自底向上合并子问题的解, 构造出原问题的解;
  • 别名: 分而治之;

什么问题才能用分治？​

  • 可分解: 原问题能拆成同类子问题;
  • 子问题独立: 子问题之间不共享状态、不互相依赖;
  • 可合并: 子问题的解能合成为原问题的解;
  • 反例: 子问题重叠时更适合动态规划, 而非分治;

分治与递归是什么关系？​

  • 关系: 分治是算法思想, 递归是实现方式之一;
  • 实现选择: 分治既可用递归实现, 也可用迭代实现;
  • 典型应用: 大数乘法、矩阵乘法、汉诺塔、二分查找、归并/快速/桶排序、深度优先搜索;

分治的通用模板是什么？​

def divide_and_conquer(problems_n):             # problems_n 为问题规模
    if problems_n < d:                          # 规模足够小时直接求解
        return solove()

    problems_k = divide(problems_n)             # 分解为 k 个同形式子问题

    res = [0 for _ in range(k)]
    for i, problem_k in enumerate(problems_k):
        res[i] = divide_and_conquer(problem_k)  # 递归求解子问题

    return merge(res)                           # 合并子问题的解
  • 四个位置: 直接求解的边界、分解函数、递归调用、合并函数;
  • 只分不合并的退化形态: 每层只保留一个子问题, 如二分查找与快速幂, 见 分治的经典应用;