算法设计与分析第五周作业

Posted by 韩同学的笔记本 on March 16, 2020

4.1

(1)

按照 $t_i$ 从小到大的顺序安排顾客的服务次序。

正确性证明:

假设我们按照 $n$ 的某个排列 $p$ 安排顾客服务次序时总时间达到最小,且存在一对 $i,j$ 满足 $i<j \wedge t_{p_i} > t_{p_j}$。记在排列 $p$ 下顾客们等待的总时间为 $T(p)$ 那么:

\[\begin{aligned} T(p) =& \sum_{k=1}^n (t_{p_1} + t_{p_2} + \cdots + t_{p_{k-1}}) \\ = & (n-1) t_{p_1} + (n-2) t_{p_2} + \cdots + t_{p_{n-1}} \end{aligned}\]

设 $p’$ 为排列 $p$ 中交换位置 $i$ 和位置 $j$ 上的元素 $(i < j)$ 所得到的排列。

\[\begin{aligned} & T(p) - T(p') \\ = & (n-1) t_{p_1} + (n-2) t_{p_2} + \cdots + t_{p_{n-1}} - ((n-1) t_{p'_1} + (n-2) t_{p'_2} + \cdots + t_{p'_{n-1}}) \\ = & (n-i) t_{p_i} + (n-j) t_{p_j} - (n-j) t_{p_i} - (n-i) t_{p_j} \\ = & (j-i) t_{p_i} + (i-j) t_{p_j} \\ = & (j-i) t_{p_i} - (j-i) t_{p_j} \\ > & 0 \end{aligned}\]

所以交换 $p$ 中不满足贪心策零的一对元素所得等待时间一定不会比 $T(p)$ 这个最优解的总时间更差(甚至更优)。而逆序对数是有限的,所以一定在有限步内将最优解转化为贪心所得的解。算法正确性得到证明。

(2)

  1. 建立二元组数组 $A_i=(t_i,i)$
  2. 对 $A_i$ 按照第一关键字排序
  3. $i$ 从 $1$ 到 $n$ 输出 $A_i$ 的第二关键字

其中 1.3. 复杂度为 $O(n)$,第二步复杂度为 $O(n\log n)$,所以总复杂度为 $O(n\log n)$.

(3)

  1. 建立二元组数组,$A=[(1,1),(3,2),(2,3),(15,4),(10,5),(6,6),(12,7)]$
  2. 对 $A$ 按照第一关键字排序,$A$ 变为 $[(1,1),(2,3),(3,2),(6,6),(10,5),(12,7),(15,4)]$
  3. $i$ 从 $1$ 到 $n$ 输出 $A_i$ 的第二关键字:

得到安排顺序:1, 3, 2, 6, 5, 7, 4

4.3

从 $1$ 到 $n$ 考察每一个房子,然后构造解。假设我们考察到了第 $i$ 个房子,如果第 $i$ 个房子目前没有被任何基站覆盖,那么我们就在(距离A城市) $(d_i+4)$ 的位置建立一所基站。重复上述过程直到每一所房子被覆盖。

伪码:

1
2
3
4
5
6
7
8
9
10
11
12
13
# 输入:房子个数 n、每个房子到城市A的距离 d[i]
# 输出:基站总数 m、每个基站的位置 p[j]

R = -1
m = 0
p = []
for i = 1 to n do:
    if d[i] > R:
        m = m + 1
        p[m] = d[i] + 4
        R = p[m] + 4

print(m, p)

正确性证明:

  1. 按以上贪心策略,我们可以得到每个基站覆盖的范围的最靠近A城市的位置一定有一个房子
  2. 当只有一个房子的时候上述贪心策略显然成立
  3. 假设有 $k$ 个房子的时候上述贪心策略成立,现证明上述贪心策略也对 $(k+1)$ 个房子的情况成立
  4. 令 $m_k$ 表示覆盖前 $k$ 个房子所用最少基站数。显然有 $m_k \le m_{k+1} \le m_k + 1$
  5. 若 $k+1$ 个房子在某个基站的覆盖范围内,则 $m_{k+1} = m_k$ 达到下界,算法正确
  6. 若 $k+1$ 个房子在某个基站的覆盖范围内:
    • 假设此时也有 $m_{k+1} = m_k$,那么第 $k$ 个房子必须被覆盖。所以我们必须移动之前的某个基站来覆盖第 $k$ 个房子,然而根据 1. 每一个基站覆盖范围的最左端为一个房子,若要移动某个基站覆盖第 $k$ 个房子,该基站距离A城市的距离一定变大。因此总有一个处在某个基站覆盖范围的最靠近A城市的房子在移动后无法被覆盖到。
    • 因此假设不成立。$m_{k+1} \neq m_k$,又因为 4. ,所以 $m_{k+1} = m_k+1$,此时算法所求即为 $m_{k+1}$,算法正确
  7. 因此算法的正确性得到证明

复杂度分析:考虑伪码中循环的复杂度为 $O(n)$,其他部分均为 $O(1)$ 所以算法最后的总复杂度也为 $O(n)$

4.12

(1)

Fibonacci数列1至8项为:$[1,1,2,3,5,8,13,21]$

画出哈夫曼树(叶节点概率应该除以一百,这里为了直观没有除以):

Huffman-Tree

(2)

设斐波那契数列的第 $i$ 项为 $F(i)$,那么最终所得的树应该为如下图所示的,除根结点之外,树的每一层只有2个节点的树。

Fiffman-Tree

只需证 $\sum_{i=1}^k F(i) \le F(k+2), \forall k \in {1,2,\dots,n}$

  • 首先验证 $k=1,2$ 时上式成立
  • 假设对命题对 $k’=n$ 时成立,考虑 $k=n+1$ 时:
    • \[\begin{aligned}F(k+2)&=F(k+1)+F(k) \\ &=F(k'+2)+F(k) \\ &\ge \sum_{i=1}^{k'} F(i) + F(k) \\ &= \sum_{i=1}^{k}F(i) \end{aligned}\]
    • 这样就证明了 $k=n+1$ 时也成立
  • 命题得证

4.15

按照 $b_i$ 从大到小的顺序安排这些任务。然后按上述顺序,把任务逐一安排在A上做,在A上预处理完成后,立刻转移到任意一台B机器上完工。

时间复杂度分析:因为排序的时间复杂度为 $O(n\log n)$,最终扫描遍历任务求总时间的复杂度为扫描序列的复杂度 $O(n)$,所以算法总的时间复杂度为 $O(n\log n)$

正确性证明:

假设我们是按 $1,2,\dots,n$ 的顺序安排任务的。总加工时间可以这么计算: \(\max\left\{\sum_{i=1}^k a_k+b_k \mid \forall k \in \{1,2,3,\dots,n\}\right\}\)

考虑任意的一种最优解。假设在此最优解中存在一对 $i,j$ 使得 $i<j \wedge b_i<b_j$. 我们可以算得 $i,j$ 对答案的贡献为 $\max{a_1+a_2+\dots+a_i+b_i,a_1+a_2+\dots+a_i+\dots+a_j+b_j}$

交换 $i,j$ 的位置,我们有 $i,j$ 对答案的贡献为 $\max{a_1+a_2+\dots+a_j+b_j,a_1+a_2+\dots+a_j+\dots+a_i+b_i}$

因为:

  • $a_1+a_2+\dots+a_i+\dots+a_j+b_j \ge a_1+a_2+\dots+a_j+b_j$
  • $a_1+a_2+\dots+a_j+\dots+a_i+b_i \ge a_1+a_2+\dots+a_i+b_i$
  • $b_i<b_j$

所以

\[\begin{aligned} &\max\{a_1+a_2+\dots+a_i+b_i,a_1+a_2+\dots+a_i+\dots+a_j+b_j\} \\ =& a_1+a_2+\dots+a_i+\dots+a_j+b_j\\ >& a_1+a_2+\dots+a_j+\dots+a_i+b_i\\ \end{aligned}\]

而且

\[\begin{aligned} &\max\{a_1+a_2+\dots+a_i+b_i,a_1+a_2+\dots+a_i+\dots+a_j+b_j\} \\ =& a_1+a_2+\dots+a_i+\dots+a_j+b_j\\ >& a_1+a_2+\dots+a_j+b_j\\ \end{aligned}\]

因此

\[\begin{aligned} &\max\{a_1+a_2+\dots+a_i+b_i,a_1+a_2+\dots+a_i+\dots+a_j+b_j\} \\ > & \max\{a_1+a_2+\dots+a_j+b_j,a_1+a_2+\dots+a_j+\dots+a_i+b_i\} \end{aligned}\]

所以交换这样的符合贪心策略的 $i,j$,减小了 $i,j$ 的贡献,因此不会让答案变差。

因为这样的逆序是有限多个,所以通过有限步转换我们可以将一个最优解,在不让答案变差的情况下,转化为贪心法得到的解。算法正确性也就得到证明了。

4.18

(1)

因为所有广告的收益相同,所以问题的答案只与广告数目有关。问题可以转化为活动选择问题。

具体来说:我们需要维护当前选择广告最晚的截止时间 $T$。从 $1$ 到 $n$ 考察每一条广告,假设我们考虑到了第 $i$ 条广告,如果 $T \le d(i)$,则选择第 $i$ 条广告,然后令 $T \leftarrow d(i)$,然后继续考虑下一条广告。

正确性:

设 $S ={1,2,\dots, n}$ 是广告集,广告按截止时间递增顺序排序

$k=1$, 显然存在一种最优解包含广告 $1$

任取最优解$A$,$A$ 中的广告按照截止时间递增的顺序排列。如果 $A$ 的第一个广告为 $j, j \neq 1$,令 $A’= (A - { j }) \cup {1}$,由于$f_1\le f_j$,$A$ 也是最优解,且含有 $1$.

假设命题对 $k$ 为真,证明对 $k+1$ 也为真.

算法执行到第 $k$ 步, 选择了广告$i_1=1, i_2, \dots, i_k$, 根据归纳假设存在最优解 $A$ 包含 $i_1= 1, i_2, \dots , i_k$,

$A$ 中剩下的广告选自集合 $S’={ i \mid i\in S, s_i \ge f_k}$,且

\[A = { i_1, i_2, \dots , i_k }\cup B\]

$B$ 是 $S’$ 的最优解.(若不然, $S’$ 的最优解为 $B^*$, $B^*$ 的广告数目比 $B$ 多,那么 $B^*\cup{1, i_2, … , i_k}$是 $S$ 的最优解,且比 $A$ 的广告数目多,与 $A$ 的最优性矛盾.)

根据归纳基础,存在 $S’$ 的最优解 $B’$ 含有 $S’$ 中的第一个活动,设为 $i_{k+1}$,且 $|B’|=|B|$, 于是 \(\{i_1,i_2,\dots,i_k\} \cup B' = \{i_1,i_2,\dots,i_k,i_{k+1}\}\cup (B'- \{i_{k+1}\})\) 也是原问题的最优解。正确性得证。

(2)

设 $F(i)$ 表示考虑了前 $i$ 个广告,选择第 $i$ 条广告并采用最优策略获得的最大总效益。

有递推方程:

\[F(i) = \begin{cases} 0 & \text{ if } i = 0 \\ \max _{k\in \{0,1,...,i-1\}\wedge d(k) \le s(i)}\{F(k) + v(i)\} & \text{ if } 1 \le i \le n\\ \end{cases}\]

有追踪函数:

\[I(i) = \begin{cases} 0 & \text{ if } i = 0 \\ \text{arg}\max_{k\in \{0,1,...,i-1\}\wedge d(k) \le s(i)}\{I(k) + v(i)\} & \text{ if } 1 \le i \le n\\ \end{cases}\]

最大收益为 $F$ 中最大值。

得到解的方法:

  1. 令 $k=\text{arg}\max_{1 \le i \le n} {F(i)}$
  2. 将 $k$ 加入解
  3. $k \leftarrow I(k)$
  4. 如果 $k\neq 0$ 则跳转至 2.
  5. 结束算法

4.20

贪心算法:按照 $r_i$ 从大到小的顺序购买许可证。

正确性证明:

设某个最优解中第 $i$ 个软件在第 $p_i$ 个月购买,对于第 $j$ 个软件在第 $p_j$ 个月购买,有 $p_i < p_j \wedge r_i < r_j$,$i,j$ 贡献代价为:$r_i ^ {p_i} \times 1000+r_j ^ {p_j} \times 1000$

考虑交换第 $i$ 个软件和第 $j$ 个软件的购买次序,调整之后 $i,j$ 的贡献代价为:$r_i ^ {p_j} \times 1000+r_j ^ {p_i} \times 1000$

\[\begin{aligned} & r_i ^ {p_i} \times 1000+r_j ^ {p_j} \times 1000 - (r_i ^ {p_j} \times 1000+r_j ^ {p_i} \times 1000) \\ = & r_i^{p_i}(1-r_i^{p_j-p_i}) \times 1000 - r_j^{p_i} (1-r_j^{p_j-p_i}) \times 1000 \\ = & (r_i^{p_i} - r_j^{p_i}) (1-r_j^{p_j-p_i}) \times 1000 \\ \ge& 0 \end{aligned}\]

因此调整之后 $i,j$ 的贡献代价会降低,也就是说答案不会变差。因为逆序对数是有限的,所以上述调整一定会在有限步内将一个最优解在不使答案变差的情况下转变为通过贪心算法所得的解。

复杂度分析:因为我们需要按照 $r_i$ 从大到小的顺序购买许可证,所以需要将 $r_i$ 进行一遍排序,复杂度为 $O(n \log n)$