第12次课

【03:00】复习上一节

image-20200613122220367

对于一个问题，如果能 抽象成胚，则可以直接用贪心方法求最优解，不用证明他的正确性

image-20200613122655331

有序对不能随便找。

image-20200613122805474

  • 贪心算法=(不断的)选择+独立性检测
  • 加权胚是要求最大问题，如果实际问题是求最小的，要做转化
  • A一直是独立的
  • 算法返回的结果A是最优子集

【18:00】 加权胚的贪心选择性质

image-20200613123317650

image-20200613124445840

image-20200613125158657

  • 现在要证明A也是最优子集, 怎么证明？通过权值

image-20200613125331707

【47:00】加权胚的最优子结构性质

image-20200613125443061

image-20200613142723086

image-20200613143620376

  • 正确性要说明通用贪心算法返回的结果A是一个最优子集.
  • image-20200613144133864

【01:06:00】加权胚模型的应用

从理论->求解实际问题的过程

  1. 定义有序对(S,I) I是S中具有共性元素组成的子集族.
  2. S一般是输入集
  3. 遗传性是好证的，比如无向图中的没有回路的边的集合，去掉一些还是无回路
  4. 交换性证明要困难一点
  5. 当胚的3个条件都满足了以后，后面就简单了，用通用贪心算法

image-20200615093427535

  • 要定义出能求解这个问题的独立集，先来看调度问题

image-20200615093847440

什么叫把一种调度调成规范形式？

  • 早任务还是早任务，晚任务还是晚任务。早任务按截止期递增。迟任务不用管它。
  • 交换以后早任务的性质会不会发生变化呢？

image-20200615122608700

为什么要求晚任务权值之和最小 就是求 早任务权值之和最大的问题？

image-20200615125100986

【01：50：30】引理16.12

  • A独立是说 A是早任务集。
  • A中的元素的值表示任务的deadline

image-20200615130754851

  • 其中②可以用来判定是不是一个早任务集。

image-20200615135759428

image-20200615140220509

image-20200615140646933

A属于I表明A是一个早任务集。

image-20200615141014568

image-20200615141225572

结束

image-20200615141240869

【13次课开始~27:30 】

image-20200616173546632

  • 按通用的加权胚的贪心算法，把任务先按权值递减排列
  • A一开始是空集，是独立子集,先加入a1,进行独立性检测
  • A独立是指A中的任务都是早任务
  • 遍历所有任务，找出独立集
  • 求最优调度怎么求？
    • 按早任务优先（不一定是最优调度,其中某些任务可能会变成迟任务），调成规范形式，迟任务

【】

【】