算法设计与分析笔记0x02 —— 贪心法(1)

贪心法:每个步骤选择当前最优的

Interval Scheduling

  • Goal: 找到尽可能多的相容工作
  • Greed Algorithm
    • 排序 nlogn
      • 起始时间(break)
      • 结束时间(由早到晚)
      • 时间长度(break)
      • 冲突数量(break)
    • 当前工作与已选择工作无冲突的话,选择当前工作 n
  • Greedy algorithm Consider jobs in increasing order of finish time. Take each job provided it’s compatible with the ones already taken.

     
  • Implementation O(nlogn)
    • 记录A中结束时间最晚的工作 j*
    • 工作j的开始时间晚于j*的结束时间,则与A无冲突

Proof

  • 证明贪心法为最优算法:
  • 假设贪心法不是最优的
  • i_1,i_2,…i_k 表示贪心法算出的工作集合
  • j_i,j_2,…j_k 表示最优工作解
  • i_1=j_1,i_2=j_2,…i_r=j_r,前r个工作,两集和相同,使r尽可能大
  • 即$j_{r+1}$工作开始结束时间晚于$i_{r+1}$,将$j_{r+1}$替换为$i_{r+1}$,j工作序列依然为最优解

Interval Partitioning

  • Lower Bound on Optimal Solution
  • Goal: 找到最少的教室数量来安排所有的课程
  • Lecture j starts at sj and finishes at fj.
  • Greedy algorithm
    • 排序 nlogn
      • 按照开始时间排序
    • 若当前课程可以安排在已有教室则加入,不能安排则开新教室

       
  • Implementation O(nlogn)
    • 记录每个教室的最晚结束时间
    • 检查空闲时间最早的教室

Proof

  • 找出在任意时刻,最多有多少门课在同时进行
  • Key observation Number of classrooms needed >= depth (when it’s equal, it reaches optimal solution)
  • Let d = number of classrooms that the greedy algorithm allocates.
  • Classroom d is opened because we needed to schedule a job, say j, that is incompatible with all d-1 other classrooms.
  • Since we sorted by start time, all these incompatibilities are caused by lectures that start no later than $s_j$.
  • Thus, we have d lectures overlapping at time $s_j + \epsilon$.

Scheduling to Minimizing Lateness

  • Goal: minimize maximum lateness
  • Greedy algorithm
    • 排序
      • 持续时间(break)
      • 截止时间
      • 最晚开始(使得不迟交)时间 smallest slack(break)

 

Inversions 反转

  • Def: 有两个任务(i,j),i的截止时间早于j的截止时间,但是j被安排在i前面
  • In greedy schedule, no idle time, no inversions.
  • After we swap inversion jobs, lateness won’t increase.

Proof

Greedy schedule S is optimal.
Define S* to be an optimal schedule that has the fewest number of inversions, and let’s see what happens.

  • Can assume S* has no idle time.
  • If S* has no inversions, then S = S*.
  • If S* has an inversion, let i-j be an adjacent inversion.
    • swapping i and j does not increase the maximum lateness and strictly decreases the number of inversions
    • this contradicts definition of S*

Greedy Analysis Strategies

  • Greedy algorithm stays ahead Show that after each step of the greedy algorithm, its solution is at least as good as any other algorithm’s.
  • Structural Discover a simple “structural” bound asserting that every possible solution must have a certain value. Then show that your algorithm always achieves this bound.
  • Exchange argument Gradually transform any solution to the one found by the greedy algorithm without hurting its quality.

Shortest Path – Dijkstra’s Algorithm

  • Maintain a set of explored nodes S for which we have determined the shortest path distance d(u) from s to u.
  • Initialize S = { s }, d(s) = 0.
  • Repeatedly choose unexplored node v which minimizes
    $$\pi(v)=min_{e=(u,v):u\in S}d(u)+l_e$$
    add v to S, and set $d(v) = \pi(v)$.

Proof of Correctness

Invariant. For each node $u \in S$, d(u) is the length of the shortest s-u path.
Pf. (by induction on |S|)
Base case: |S| = 1 is trivial.
Inductive hypothesis: Assume true for |S| = k >= 1.

  • Let v be next node added to S, and let u-v be the chosen edge.
  • The shortest s-u path plus (u, v) is an s-v path of length $\pi(v)$.
  • Consider any s-v path P. We’ll see that it’s no shorter than $\pi(v)$.
  • Let x-y be the first edge in P that leaves S, and let P’ be the subpath to x.
  • P is already too long as soon as it leaves S.
    $$l(p)\geq l(p’) + l(x,y) \geq d(x) + l(x,y) \geq \pi(y) \geq \pi(v)$$

Implementation

For each unexplored node, explicitly maintain $\pi(v)=min_{e=(u,v):u\in S}d(u)+l_e$.

  • Next node to explore = node with minimum $\pi(v)$.
  • When exploring v, for each incident edge e = (v,w), update
    $$\pi(w)=min(\pi(w),\pi(v)+l_e)$$
    Efficient implementation. Maintain a priority queue of unexplored nodes, prioritized by $\pi(v)$.

Leave a Reply

Your email address will not be published.