问答

贪心算法和最优子结构

 来源    2019-03-25    0  

Wikipedia page,据说贪婪算法仅适用于具有最佳子结构的问题.

问题:

>什么是最优/非最佳子结构?
>什么是本地和全球最优?
>如何证明贪婪算法能够产生全局最优?

我找到了答案,很高兴分享:

>什么是最优/非最佳子结构?如果可以从其子问题的最优解构建有效地构造最优解,则认为问题具有最优子结构.此属性用于确定问题的动态编程和贪婪算法的有用性
>什么是本地和全球最优?优化问题的局部最优是在相邻候选解集合中最优(最大或最小)的解决方案.
全局最优 – 是所有可能解决方案中的最佳解决方案,而不仅仅是特定价值邻域中的解决方案.
>如何证明贪婪算法能够产生全局最优?
通常,可以通过归纳证明全局最优.通常,贪婪算法用于解决具有最佳子结构的问题,如果可以通过归纳证明这在每个步骤是最佳的.否则,提供问题也表现出重叠的子问题,使用动态编程.

为了证明使用贪婪算法可以解决优化问题,我们需要证明问题具有以下内容:

最优子结构属性:最优全局解包含所有子问题的最优解.

贪婪的选择属性:通过贪婪地选择局部最优选择,可以获得全局最优解.

在某些情况下,可以使用拟阵来机械地证明特定问题可以通过贪婪方法来解决.

最后,贪婪算法的好例子是:
http://www.cs.nott.ac.uk/~nza/G52ADS/dijkstra1.pdf

相关文章
贪心算法:最优装载问题
日志/*----------------------------------------------------- 给出n个物体,第i个物体的重量为wi. 选择尽量多的物体,使得总重量不超过C. 输入: ...
贪心算法 POJ-3040 局部最优到全局最优
日志一.题目 Description As a reward for record milk production, Farmer John has decided to start paying Bes ...
贪心算法:间隔着色
问答在区间调度中,算法是选择最早的完成时间.但在间隔着色中,前者不起作用.是否有一个例子或解释为什么选择最早的完成时间不适用于间隔着色? 区间着色问题是:给定一组间隔,我们想要着色 所有间隔使得给定相同颜 ...
贪心算法的改进
问答我一直在研究使用Haskell的抽象国际象棋算法(试图扩展我对不同范式的理解),并且我遇到了一个我一直在思考几周的挑战. 这是问题所在: Given a board (represented by a ...
贪心算法Java / firstFit方法
问答我正在当地社区大学学习Java课程的数据结构和算法,而且我完全坚持目前的家庭作业.问题如下-- 编写一个程序,将各种权重的对象打包到容器中.每个容器最多可容纳10磅. 该程序使用一种贪婪的算法,将一个 ...
Haskell中编辑距离算法 – 性能调优
问答我试图在Haskell中实现levenshtein距离(或编辑距离),但是当字符串长度增加时,其性能会迅速下降. 我还是Haskell的新手,所以如果你能给我一些关于如何改进算法的建议,那将是很好的. ...
python – 贪心算法和硬币算法?
问答我一直致力于项目Euler的一些问题/练习,希望练习/学习一些最佳算法和使用python编程习语. 我遇到了一个问题,要求找到所有使用至少两个值总和为100的独特组合.在研究这个问题时,我遇到了人们提 ...
1
贪心算法的正确性
问答In non-decreasing sequence of (positive) integers two elements can be removed when . How many pairs ...
如何发现“贪心”算法?
问答我正在读一本关于"贪心"算法的tutorial,但是我很难发现他们解决真正的"顶级编码器"问题. 如果我知道使用"贪心"算法可以解决给定的问 ...
k-limited资源的贪心算法
问答我正在研究贪心算法,我想知道不同情况的解决方案. 对于区间选择问题,我们希望选择不会相互冲突的最大活动数,因此选择具有最早结束时间的作业是有效的. 另一个例子;我们有n个工作岗位,我们希望以尽可能少的 ...
为什么贪心算法没有找到最大的独立图集?
问答给定图G,为什么跟随贪心算法不能保证找到G的maximum independent set: Greedy(G): S = {} While G is not empty: Let v be a no ...
计算机科学 – 进化算法:最优重建分析
问答这真的是所有的标题,但是对于对进化算法感兴趣的人来说,这是一个细分: 在EA中,基本的前提是您随机生成一定数量的生物(这些只是一组参数),运行它们来解决问题,然后让最佳表现者生存下去. 然后,随着幸存 ...
数学优化 – 贪心算法和最陡算法有什么区别?
问答我有幻灯片,其中比较了2个版本的本地搜索算法:贪婪和最陡. 贪婪:     生成解x;     重复     {         对于N(x)中的每个y,以随机顺序         {         ...
算法 – TSP最优游
问答我写了一个细菌进化算法来解决TSP问题.我选择了XQF131实例(http://www.math.uwaterloo.ca/tsp/vlsi/index.html)来测试我的算法. 这个问题由Conc ...
贪心算法将数字配对,最小化最大总和
问答输入是实数x1,x2,-,x2n的序列.我们想将这些数字配对成n对.对于第i对,(i = 1,2,-,n),让Si表示该对中的数字之和. (例如,如果将x(2i-1)和x2i配对作为第i对,则Si = ...
调度,贪心算法
问答这是流行的El Goog问题的变种. 考虑以下调度问题:有n个作业,i = 1..n.有1台超级计算机和无限制的电脑.每个作业需要先由超级计算机预处理,然后在PC上处理.超级计算机上作业i所需的时间是 ...
算法学习——贪心算法之币种统计
日志算法描述 币种统计 单位给每一位员工发工资(精确到元),为了保证不临时换零钱,使得每个员工取款的张数最少,在取工资前统计所有员工所需要的各种票面的张数(约定票种为100,50,20,10,5,2,1元 ...
算法学习——贪心算法之取数游戏(显示两端数字)
日志算法描述 取数游戏:A与B玩取数游戏,随机产生的2n个整数排成一列,只显示两端的整数,只有当A或B取完数会显示下一个数或者是前一个数(若是取末尾的数) A的取数策略:采用贪心策略,每次取数取两个数中最 ...
算法学习——贪心算法之可拆背包
日志算法描述 已知道n种物品和一个可容纳c重量的背包,第i种物品的重量为wi,价值为pi,装包的时候可以把物品拆开(即可只装每种物品的一部分),设计如何装包,使装包所得整体的价值最高? 算法思路 首先,我 ...