算法设计与分析——贪心算法——具有贪心性的证明——局部最优可以得到全局最优

客院载论

5296人浏览 · 2021-06-16 17:02:26

客院载论 · 2021-06-16 17:02:26 发布

文章目录

基本知识回顾

贪心算法的基本要素
- 最优子结构性质：一个问题的最优解包含其子问题的最优解时，称这个问题具有最优子结构性质
- 贪心选择性质：所求问题的整体最优解可以通过一系列的局部最优解选择，也就是贪心选择来得到。
  - 这也是贪心算法对于最优解问题可行的基本要素，是贪心算法区别于动态规划算法的主要区别
  - 如果要使用贪心算法，一定要证明由算法所得到的解是最优的，通过局部最优可以得到整体最优

如何证明问题具有贪心选择性质

对于一个具体的问题，确定是否具有贪心选择的性质，必须证明每一步所作的贪心选择最终导致问题的整体的最优解

样例一：活动安排问题

分为两步：
- 证明总存在一个以贪心选择开始的最优活动安排方案
- 再证明每一步所作的贪心选择都将问题简化为一个更小的与原问题具有相同形式的子问题

问题描述

在这里插入图片描述

总有一个以贪心选择为开始的最优解

在这里插入图片描述

每一步所作的贪心选择都将问题简化为一个更小的与原问题具有相同形式的子问题

在这里插入图片描述

样例二、最优装载的贪心性证明

对于一个具体的问题，要确定她是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解

问题描述

在这里插入图片描述

证明过程

证明贪心性分两步
- 首先证明最佳装载问题有一个最优解以贪心选择开始的，即该最优解包含最轻的物体
- 然后证明每一个所作的贪心选择都将问题简化为一个更小的与原问题具有相同形式的子问题
该问题有一个最优解是贪心选择开始的
每一个所作的贪心选择，都将问题转化为与更小的与原问题相同形式的子问题

在这里插入图片描述

分析与总结

但愿考到
照葫芦画瓢，理解起来都好办

乐奇 Rokid 开放社区

更多推荐

Word Embedding ：从分布式假设到神经网络语言模型

Word Embedding（词嵌入）是一种将离散的词汇符号映射到连续的低维稠密向量空间的技术。在这个向量空间中，语义相似的词在几何距离上彼此接近，从而实现了从"符号匹配"到"语义计算"的跨越。核心定义词嵌入是将单词（或多词短语）表示为固定维度的实值向量，这些向量之间的距离（例如余弦相似度）反映了单词之间的相关性，这种相关性基于单词通常出现的上下文。分布式假设（1954）↓统计共现分析（LSA/S

乐奇 Rokid 开放社区

3 分钟装好 foobox 皮肤：foobar2000 界面升级安装教程

foobox 是一个 foobar2000 的 DUI 皮肤配置，装好后默认界面就变成带亮、暗两套主题的多面板播放器。它适合已经用 foobar2000、只想换界面不想改播放习惯的 Windows 用户：皮肤只动外观，不碰播放器核心。## 先看适不适合你- 你在 Windows 10 1607 或更高版本上用 foobar2000，想要更顺眼的界面；- 你的曲库不小，想要分组管理和搜索；

乐奇 Rokid 开放社区

镜游小导：运行在 Rokid AR 眼镜上的景区实景讲解智能体

项目以 RokidAIUI 开放智能体形态交付：页面用.ink描述，运行在眼镜端智能体运行时，直接调用系统能力。AGENTS.md身份镜游小导v1.0.0，景区 AR 实景讲解智能体；权限（Capabilities）microphonenetworkaudiogyroscope；技能（Skills）。