知识卡片
贪心流程先筛可行再合成
贪心流程先建模,再按规则拆成较小子问题,逐个求局部最优;每个候选加入部分解前还要检查可行性,最后把局部结果合成为原问题的可行解。停止条件可由数据枚举完或再无可行候选触发。局部最优组合成可行解后,是否整体最优仍要依据问题性质证明。
示例(补充教学示例,非书中数据):容量 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 处
- 1 2 . 2 . 2 贪 心 算 法 流 程 · 查看原书依据
若下个数据和部分最优解连在一起不再是可行解,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加时,算法停止[4]。
参考来源
- 位置:《智能算法导论》第 124 项《12.2.2 贪心算法流程》(源文件:`_epub-src/EPUB/xhtml/chapter12_0004.xhtml`)
- 结论依据:原文四步为建模、划分子问题、求局部最优、合成可行解;并规定下一数据与部分解合在一起不可行时不加入,直到枚举完或不能再添加。容量超限跳过是补充教学示例,非书中数据。
- 原始内容:若下个数据和部分最优解连在一起不再是可行解,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加时,算法停止。算法的实现流程如下。(1)建立数学模型来描述问题。(2)应用某一规则把求解的问题分成若干个规模较小的子问题。