7-AA2

:material-circle-edit-outline: 约 1255 个字 :material-clock-time-two-outline: 预计阅读时间 4 分钟

Greedy Algorithms

给定一个目标函数/优化函数（optimization function），取值有限制（constraints），限制下的子空间叫 feasible solutions，我们希望在限制下求一组使得函数值最大化/最小化的最优解（optimal solution）

简单来说，就是，面对规模为N的子问题，我们类似分治拆分为子问题，一般是让每个 stage 的规模减少1，然后让N-1的最优解加上按某策略得到的元素，就是N得最优解

比如，我们要从北门去南门，我们贪心策略就是就每到一个路口就往南走

Activity Selection Problem

Huffman Codes – for file compression

NP-Completeness

Approximation

Approximation Ratio 近似比就是近似解与正解之间的比值取大于1的比值的上界

\(\rho (n)\) 即近似比，其值为规模 \(n\) 时能得到的最大比值

近似比越小，精确度越高，算法也越慢越麻烦

a value \(\epsilon\) > 0 such that for any fixed \(\epsilon\), the scheme is a (1+ \(\epsilon\))-approximation algorithm.

如果算法的复杂度与\(\epsilon\)有关系就是一个PTAS

既与\(\epsilon\)有关系还与规模有关系就是 fully polynomial-time approximation scheme (FPTAS)

Approximate Bin Packing

Next Fit 近似比为2, 关键点是两个相邻的箱子物品体积和 \(> 1\)
First Fit 每次决策就依次检查前面所有的箱子，能放就放，都不行才开新箱子
Best Fit 在First Fit基础上，优先选前面剩余体积最多的箱子放

上面三个算法很垃圾，是顺序决策，只考虑过去，没考虑未来

我们称这种一个输入即时进行决策的算法叫在线算法，且决策是不能更改的，用于不知道输入是什么情况的情景

任何在线算法我们都能设计出一组解，让近似比大于5/3

离线算法就是完成所有输入后，才开始决策

The Knapsack Problem — fractional version

背包问题，我们放的东西不仅仅有体积，还有价格，而且还可以切开，切开后价格有系数 \(p_i\) 进行修正，使切后总价减少，我们希望让背包价格最大

正解算法是，找出性价比最高的物品，能整个放进去就放，不能就切了放进去，然后循环，保证性价比高的东西先进去

这个问题有一个变种叫0-1版本，即物品不能切了，要么放要么不放

The K-center Problem

Local Search

Randomized Algorithms

Parallel Algorithms

Parallel Random Access Machine (PRAM)

Work-Depth (WD) Presentation

评价并行算法需要考虑两个因素

Work load: total number of operations W(n)
Worst-case running time: T(n)

由这两个因素我们得出以下的指标：

W(n) operations and T(n) time
- T时间里完成的W工作量
P(n) = W(n)/T(n) processors and T(n) time
- T时间、P处理器数量
- on a PRAM，不能用于WD模型
W(n)/p time using any number of p ≤ W(n)/T(n) processors
- 这个算法能支持W(n)/T(n)个处理器，但是手上没这么多处理器，只有p个
- on a PRAM，不能用于WD模型
W(n)/p + T(n) time using any number of p processors
- 分情况
  - 如果p很大，那么这个式子就是T(n)，表示算法支持的最大处理器数量下的耗时
  - r如果p很小，那就是W(n)/p，同第三个
- on a PRAM，不能用于WD模型