← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3768

贪心选择不等于整体最优

理解等级:高级

局部最优只要求在限定范围或部分可行决策中最好;全局最优则要与所有可行决策比较。贪心算法每步选择当前看来最好的方案,但这种局部最优不自动推出整体最优;只有问题同时具备两条性质时,才可据此求整体最优:

  • 贪心选择性质:整体最优解可由一系列局部最优选择达到,见 [[贪心选择须能延伸为全局最优]]。
  • 最优子结构:问题的最优解包含其子问题的最优解,见 [[最优子结构保留子问题最优解]]。

不满足这两条时,贪心结果只能当近似解。原书以最大权森林、最小生成树作可直接求解的例子,以 TSP 和 0-1 背包说明贪心可能只给近似解;这些结论仍须对应具体模型,不能按问题名称泛化。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 1 2 . 3 基 于 贪 心 算 法 的 组 合 优 化 · 查看原书依据

      当然,贪心算法并不是万能的,在一些情况下,贪心算法不能求得整体最优解,如TSP、0-1背包问题,但其最终结果是最优解的近似。如果不要求绝对的最优解,那么简单高效得到近似最优解的贪心算法相比一般产生准确答案的复杂算法更受人们的喜爱。

    参考来源

    - 位置:《智能算法导论》第 121 项《贪心算法导言》、第 123 项《局部最优解概念》、第 125 项《基于贪心算法的组合优化》(源文件:`_epub-src/EPUB/xhtml/chapter12_0001.xhtml`、`_epub-src/EPUB/xhtml/chapter12_0003.xhtml`、`_epub-src/EPUB/xhtml/chapter12_0005.xhtml`) - 结论依据:第 121 项给出贪心选择与最优子结构的适用条件;第 123 项区分局部与全局比较范围;第 125 项列出最大权森林/最小生成树与 TSP/0-1 背包作为直接求解和近似求解示例,说明边界依具体问题而定。 - 原始内容:贪心选择并不从整体最优上加以考虑,它做出的选择只是某种意义上的局部最优解。局部最优是指问题的可行解只在一定范围内最优;贪心算法并不是万能的,在一些情况下,贪心算法不能求得整体最优解,如TSP、0-1背包问题,但其最终结果是最优解的近似。