算法设计复习内容提要：口算法设计思想回顾（递归和分治、动态规划、贪心算法、回溯法、分支限界法）口经典例子讲解2026/9/22
2026/9/22 1 算法设计复习 内容提要： 算法设计思想回顾（递归和分治、动态规划、贪心算法、回溯法、 分支限界法） 经典例子讲解
算法设计策略已学过的算法设计策略：递归和分治动态规划贪心算法回溯法分支限界法22026/9/22
算法设计策略 已学过的算法设计策略： ✓ 递归和分治 ✓ 动态规划 ✓ 贪心算法 ✓ 回溯法 ✓ 分支限界法 2026/9/22 2
Sch1-4分治法基本思想：把一个规模大的问题划分为规模较小的子问题，然后分而治之，最后合并子问题的解得到原问题的解。步骤:分割原问题：①求解子问题：②合并子问题的解为原问题的解。3在分治法中，子问题一般是相互独立的，因此，经常通过递归调用算法来求解子问题。3
3 ⚫ 基本思想：把一个规模大的问题划分为规模较小的子问题，然 后分而治之，最后合并子问题的解得到原问题的解。 ⚫ 步骤： ① 分割原问题： ② 求解子问题： ③ 合并子问题的解为原问题的解。 ⚫ 在分治法中，子问题一般是相互独立的，因此，经常通过递归 调用算法来求解子问题。 Sch1-4 分治法
Sch1-4分治法分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决①该问题可以分解为若干个规模较小的相同问题2)利用该问题分解出的子问题的解可以合并为该问题的解?该问题所分解出的各个子问题是相互独立的，即子问题之间不包④含公共的子问题。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。4
4 Sch1-4 分治法 分治法所能解决的问题一般具有以下几个特征： ① 该问题的规模缩小到一定的程度就可以容易地解决； ② 该问题可以分解为若干个规模较小的相同问题 ③ 利用该问题分解出的子问题的解可以合并为该问题的解； ④ 该问题所分解出的各个子问题是相互独立的，即子问题之间不包 含公共的子问题。 这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治 法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可 用分治法，但一般用动态规划较好
Sch1-4 分治法例1：最近点对问题为了使问题易于理解和分析，先来考虑一维的情形。此时，S中的n个点退化为x轴上的n个实数xl,x2，,xn。最接近点对即为这n个实数中相差最小的2个实数。假设我们用×轴上禁个点m将S划分为2个子集S1和S2，基于平衡子问题的思想，用S中各点坐标的中位数来作分割点。递归地在S1和S2上找出其最接近点对p1,p2)和l,q2)，并设d=minl/p1-p2l,lql-q2/}，S中的最接近点对或者是(pl,p2)，或者是[ql,q2]，或者是禁个p3,3]，其中p3ES1且q3Es2。能否在线性时间内找到p3,q3?S1S2pl p2q3p3ql q2m5
5 例1：最近点对问题 ⚫ 为了使问题易于理解和分析，先来考虑一维的情形。此时，S中的 n个点退化为x轴上的n个实数x1,x2,.,xn。最接近点对即为这n个 实数中相差最小的2个实数。 ⚫ 假设我们用x轴上某个点m将S划分为2个子集S1和S2 ，基于平衡子 问题的思想，用S中各点坐标的中位数来作分割点。 ⚫ 递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2}，并设 d=min{|p1-p2|,|q1-q2|}，S中的最接近点对或者是{p1,p2}，或者 是{q1,q2}，或者是某个{p3,q3}，其中p3∈S1且q3∈S2。 ⚫ 能否在线性时间内找到p3,q3？ Sch1-4 分治法