算法分析与设计

更新: 6/28/2025 字数: 0 字 时长: 0 分钟

• 时间：10:30 - 12:30
• 地点：中心楼 612-614
• 监考老师：杨晓明、肖琼谞

第一大题

分支限界法与回溯法（环保方案投资问题）

题目背景

有 3 个环保投资方案：

• 方案 1：成本 16 万元，减碳量 45 万吨
• 方案 2：成本 15 万元，减碳量 25 万吨
• 方案 3：成本 10 万元，减碳量 25 万吨

总投资成本上限 30 万元，目标是最大化总减碳量。

1.1

数学建模

1. 问题转化：将环保投资问题建模为 0-1 背包问题模型。
2. 变量定义：
   • $x_i\in \{0,1\}$ 表示是否投资第 $i$ 个方案（1=投资，0=不投资）。
3. 目标函数：最大化总减碳量 $max\sum _{i=1}^3{v}_i{x}_i$（$v_i$ 为减碳量）。
4. 约束条件：总成本 $\sum _{i=1}^3{w}_i{x}_i\le 30$（$w_i$ 为成本）。
5. 答案：
   • 减碳量等效为背包“价值”，成本等效为“重量”，投资上限 30 等效为背包容量。

1.2

队列式分支限界法求解过程

1. 构造解空间树：三层二叉树（左分支=选方案，右分支=不选）。
2. 搜索过程：
   • 扩展根节点 A → 生成 B（选方案 1，成本 16≤30）、C（不选方案 1，成本 0）。活结点表：[B, C]。
   • 扩展 B → 生成 D（选方案 2，成本 16+15=31>30，不可行）、E（不选方案 2，成本 16）。活结点表：[C, E]。
   • 扩展 C → 生成 F（选方案 2，成本 15）、G（不选方案 2，成本 0）。活结点表：[E, F, G]。
   • 扩展 E → 生成 J（选方案 3，成本 16+10=26）、K（不选方案 3，成本 16）。K 为叶子节点，减碳量=45。活结点表：[F, G]。
   • 扩展 F → 生成 L（选方案 3，成本 15+10=25）、M（不选方案 3，成本 15）。L 为叶子节点，减碳量=25+25=50。活结点表：[G, M]。
   • 扩展 G → 生成 N（选方案 3，成本 10）、O（不选方案 3，成本 0）。N 减碳量=25，O 减碳量=0。
3. 最优解：
   • 最大减碳量 = 50 万吨（方案组合：选方案 2 和方案 3，即 $x=[0,1,1]$）。

1.3

回溯法编程实现

1. 伪代码框架：

   def backtrack(i, cw, cv):
       # i: 当前决策方案索引，cw: 当前总成本，cv: 当前总减碳量
       if i > n:  # 到达叶子节点
           if cv > best_value:
               best_value = cv
               best_solution = x.copy()
           return
       # 左子树：选择当前方案
       if cw + w[i] <= C:  # 满足成本约束
           x[i] = 1
           backtrack(i+1, cw + w[i], cv + v[i])
           x[i] = 0  # 回溯
       # 右子树：不选当前方案（需剪枝）
       bound = cv + bound_func(i+1, C - cw)  # 计算剩余方案减碳量上界
       if bound > best_value:  # 上界可能更优才搜索
           x[i] = 0
           backtrack(i+1, cw, cv)

2. 关键函数：

   • bound_func：贪心估算剩余方案最大减碳量（允许部分投资）。

第二大题

贪心算法（哈夫曼编码应用）

题目背景

对 4 类垃圾编码，出现频率：

• 可回收物（45%）、厨余垃圾（30%）、有害垃圾（15%）、其他垃圾（10%）。

2.1

哈夫曼编码原理

1. 核心原则：频率越高，编码越短（不定长编码）。
2. 构造步骤：
   • 按频率升序排序节点。
   • 每次合并频率最小的两个节点，生成父节点（频率=子节点和）。
   • 重复直至只剩根节点。
   • 左分支标 0，右分支标 1，从根到叶路径即为编码。

2.2

构造哈夫曼树及编码

1. 构造过程：
   • 初始节点：其他 (10%)、有害 (15%)、厨余 (30%)、可回收 (45%)。
   • 合并其他 (10%) + 有害 (15%) → 节点 A(25%)。
   • 合并 A(25%) + 厨余 (30%) → 节点 B(55%)。
   • 合并 B(55%) + 可回收 (45%) → 根节点 (100%)。
2. 编码结果：
   • 可回收物：0
   • 厨余垃圾：11
   • 有害垃圾：101
   • 其他垃圾：100

2.3

编码长度与节省比例计算

1. 定长编码：
   • 4 种类型需 2 位二进制（$2^2=4$），总码长 = $2\times 10000=20000$ 位（假设处理 1 万次）。
2. 哈夫曼编码：
   • 可回收物：1 位 × 4500 次 = 4500 位
   • 厨余垃圾：2 位 × 3000 次 = 6000 位
   • 有害垃圾：3 位 × 1500 次 = 4500 位
   • 其他垃圾：3 位 × 1000 次 = 3000 位
   • 总码长 = $4500+6000+4500+3000=18000$ 位。
3. 节省比例：
   • 节省位数 = $20000-18000=2000$ 位
   • 节省比例 = $2000/20000=10\mathrm{\%}$。

第三大题

动态规划（多阶段决策问题）

题目背景 求图 3-16 中节点 1 到 10 的最短路径（边权已知）。

3.1

状态转移方程

1. 定义：
   • $f[s]$：从节点 1 到节点 $s$ 的最短距离。
   • $p[s]$：节点 $s$ 的前驱节点。
2. 转移方程：
   • 边界：$f[1]=0$
   • 递推：$f[s]=\underset{(x,s)\in E}{min}\{f[x]+c_{x,s}\}$（$x$ 为 $s$ 的前驱节点）。

3.2

填表计算最优值

节点	$f[s]$	$p[s]$	计算过程
1	0	-	边界
2	4	1	$f[1]+4$
3	2	1	$f[1]+2$
4	3	1	$f[1]+3$
5	8	3	$min(f[2]+10=14,f[3]+6=8)\to 8$
6	6	4	$min(f[2]+9=13,f[3]+7=9,f[4]+3=6)\to 6$
7	11	4	$min(f[3]+10=12,f[4]+8=11)\to 11$
8	12	7	$min(f[5]+4=12,f[6]+9=15,f[7]+5=16)\to 12$
9	12	6	$min(f[5]+8=16,f[6]+6=12,f[7]+4=15)\to 12$
10	16	9	$min(f[8]+8=20,f[9]+4=16)\to 16$

3.3

最优解构造

1. 最短路径长度：16。
2. 路径：
   • $10\stackrel{p[10]=9}{\leftarrow }9\stackrel{p[9]=6}{\leftarrow }6\stackrel{p[6]=4}{\leftarrow }4\stackrel{p[4]=1}{\leftarrow }1$
   • 即 $1\to 4\to 6\to 9\to 10$。

第四大题

分治法（大整数乘法）

题目背景 用分治法计算两个 8 位数乘法（如 $X=12345678$, $Y=56784321$)。

4.1

普通乘法复杂度

1. 算法：每位相乘，复杂度 $O(n^2)$。

4.2

分治法原理及优化

1. 分治步骤：
   • 将 $X,Y$ 拆分为两半（$k=n/2$ 位）： $X=A\times {10}^k+B$（$A=1234$, $B=5678$) $Y=C\times {10}^k+D$（$C=5678$, $D=4321$)
   • 原始计算：$XY=AC\cdot {10}^{2k}+(AD+BC)\cdot {10}^k+BD$（需 4 次乘法）。
2. 优化（减少乘法次数）：
   • 公式：$XY=AC\cdot {10}^{2k}+[(A+B)(C+D)-AC-BD]\cdot {10}^k+BD$
   • 乘法次数：3 次（计算 $AC$, $BD$, $(A+B)(C+D)$)。

4.3

复杂度对比

1. 优化前：$T(n)=4T(n/2)+O(n)$，解得 $T(n)=O(n^2)$。
2. 优化后：$T(n)=3T(n/2)+O(n)$，解得 $T(n)=O(n^{{\log }_{2}3})\approx O(n^{1.585})$。
3. 结论：优化后效率显著提升（指数级降低）。

贡献者

AKAcxp

页面历史

最后编辑于 大约 9 小时前

查看完整历史

75dd19a-个人博客

f3d924b-个人博客