← 返回刚才阅读的位置

知识卡片

结构图卡 · 3768.d

贪心流程先筛可行再合成

理解等级:中级

贪心流程先建模,再按规则拆成较小子问题,逐个求局部最优;每个候选加入部分解前还要检查可行性,最后把局部结果合成为原问题的可行解。停止条件可由数据枚举完或再无可行候选触发。局部最优组合成可行解后,是否整体最优仍要依据问题性质证明。

示例(补充教学示例,非书中数据):容量 50 已装入重量 20 与 30 的两件,下一件重量 10。加入后总重 60>50,该件不进入部分解,算法改看后续候选或停止。这里筛掉的是可行性,不等于证明留下的组合是整体最优。

结构图:

flowchart TD
  A[建立问题模型] --> B[按规则划分子问题]
  B --> C[求当前局部最优候选]
  C --> D{加入后仍可行?}
  D -- 是 --> E[纳入部分解]
  D -- 否 --> F[跳过候选]
  E --> G{仍有数据或可行候选?}
  F --> G
  G -- 是 --> C
  G -- 否 --> H[合成原问题可行解]
这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《智能算法导论》第 124 项《12.2.2 贪心算法流程》(源文件:`_epub-src/EPUB/xhtml/chapter12_0004.xhtml`) - 结论依据:原文四步为建模、划分子问题、求局部最优、合成可行解;并规定下一数据与部分解合在一起不可行时不加入,直到枚举完或不能再添加。容量超限跳过是补充教学示例,非书中数据。 - 原始内容:若下个数据和部分最优解连在一起不再是可行解,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加时,算法停止。算法的实现流程如下。(1)建立数学模型来描述问题。(2)应用某一规则把求解的问题分成若干个规模较小的子问题。