2023年8月1日发(作者：)

证明kruskal算法求解图的最⼩⽣成树具有贪⼼选择性质_贪⼼算法如何贪⼼ 在前⾯学习最短路径和最⼩⽣成树的时候，我们发现Dijkstra算法，Prim算法，Kruskal算法都是属于 贪⼼算法的应⽤。这篇⽂章就是对于贪⼼算法的⼊门介绍贪⼼算法贪⼼算法(⼜称贪婪算法)是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪⼼算法不是对所有问题都能得到整体最优解，关键是贪⼼策略的选择，选择的贪⼼策略必须具备⽆后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。简单的说就是我们在问题处理中，将问题分解为很多步，然后在每⼀步的求解过程中，“贪婪”的选择最佳操作，并希望通过⼀系列的最优选择，能够产⽣⼀个问题的(全局的)最优解算法思路贪⼼算法的基本思路是从问题的某⼀个初始解出发⼀步⼀步地进⾏，根据某个优化测度，每⼀步都要确保能获得局部最优解。每⼀步只考虑⼀个数据，不能回退，他的选取应该满⾜局部优化的条件。若下⼀个数据和部分最优解连在⼀起不再是可⾏解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停⽌。最优⼦结构当⼀个问题的最优解包含着它的⼦问题的最优解时，称此问题具有最优⼦结构性质。问题所具有的这个性质是该问题可⽤动态规划算法或贪⼼算法求解的⼀个关键特征。我们通过下⾯两个例题来看下什么时候选⽤贪⼼算法求解。例题⼀题⽬：给出0-9的数字任意个，⽐如数字0两个，数字1两个，数字5三个。让你⽤所给的数据组成⼀个最⼩值，0不能放在⾸位。解题策略分析：对于组装数据的策略其实有很多种，但是如果组装成⼀个最⼩值，那么其实我们很容易想到策略其实只有⼀种，即每次都选取规定中的最⼩的值去组装新的数。既然策略只有⼀种，且是⽤给定的数去组成⼀个新的最⼩的数，那么运⽤贪⼼算法之前，我们需要考虑每⼀步组装新值所选取的数据如果是符合规定的最⼩值，那么能不能保证最终的数值是最⼩的。这⾥显⽽易见，每⼀步的⾸位数字是符合规定的最⼩值，那么最终组成的数据也是最⼩的(可以使⽤数学归纳法证明)。所以使⽤贪⼼算法是可以的。例题⼆题⽬：假如现在仓库囤有⼀批同款产品不同规格的货物，货A是30吨，货B是50吨，货C是30吨，总价值分别是，30万，50万，30万，货物A，B，C不可分解。现在有⼈准备收购60吨。那么如何分配呢？解题策略分析：这道题和例题⼀的区别在于，例题⼀策略只有⼀种，就是每次选取最⼩的即可，但是这道题我们⽆法准确定义策略有集中，因为他可能的策略都有可能是最优策略:策略⼀：卖货物价值最⾼的B，50万，但是如果卖A和B会有60万，所以不⾏策略⼆：卖货物最轻的A，C，⼀共60万。看似可⾏，但是我们需要想到的是，这些数据可能是任意的，如果A是10吨，那么A，C只有40万。策略三：卖单价最贵的，我们会发现他们单价是⼀样的，没法选。如果我们在该策略下再制定第⼆策略，优先卖重量⼩的，那么其实就会出现上⾯的策略⼆问题。⾛到这⾥我们就发现，贪⼼算法不能完全处理某⼀策略下的所有数据。因为每⼀步的最优解，会影响后续选择(由于60吨的限制)。我们想⼀下为什么不能使⽤贪⼼算法，那是因为我们⽆法确定贪⼼策略，限制贪⼼策略的原因是ABC不能拆分，不能拆分，就有了上⾯三种可能，但是如果可以拆分，那么策略三是可⾏的，先卖单价最贵的，但是如果单价相同那么得到的结果不是唯⼀的。如何选⽤贪⼼算法并不能总求得问题的整体最优解。但对于某些问题，却总能求得整体最优解，这要看问题是什么了。只要能满⾜贪⼼算法的两个性质：贪⼼选择性质和最优⼦结构性质，贪⼼算法就可以出⾊地求出问题的整体最优解。即使某些问题，贪⼼算法不能求得整体的最优解，贪⼼算法也能求出⼤概的整体最优解。如果你的要求不是太⾼，贪⼼算法是⼀个很好的选择。最优⼦结构性质是⽐较容易看出来的，但是贪⼼选择性质就没那么容易了，这个时候需要证明。证明往往使⽤数学归纳法。例题⼀代码(C++) // Minimun Created by 陈龙// Copyright © 2019 陈龙. All rights reserved.//#include using namespace std;int main(int argc, const char * argv[]) { int t[

2023年8月1日发(作者：)

证明kruskal算法求解图的最⼩⽣成树具有贪⼼选择性质_贪⼼算法如何贪⼼ 在前⾯学习最短路径和最⼩⽣成树的时候，我们发现Dijkstra算法，Prim算法，Kruskal算法都是属于 贪⼼算法的应⽤。这篇⽂章就是对于贪⼼算法的⼊门介绍贪⼼算法贪⼼算法(⼜称贪婪算法)是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪⼼算法不是对所有问题都能得到整体最优解，关键是贪⼼策略的选择，选择的贪⼼策略必须具备⽆后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。简单的说就是我们在问题处理中，将问题分解为很多步，然后在每⼀步的求解过程中，“贪婪”的选择最佳操作，并希望通过⼀系列的最优选择，能够产⽣⼀个问题的(全局的)最优解算法思路贪⼼算法的基本思路是从问题的某⼀个初始解出发⼀步⼀步地进⾏，根据某个优化测度，每⼀步都要确保能获得局部最优解。每⼀步只考虑⼀个数据，不能回退，他的选取应该满⾜局部优化的条件。若下⼀个数据和部分最优解连在⼀起不再是可⾏解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停⽌。最优⼦结构当⼀个问题的最优解包含着它的⼦问题的最优解时，称此问题具有最优⼦结构性质。问题所具有的这个性质是该问题可⽤动态规划算法或贪⼼算法求解的⼀个关键特征。我们通过下⾯两个例题来看下什么时候选⽤贪⼼算法求解。例题⼀题⽬：给出0-9的数字任意个，⽐如数字0两个，数字1两个，数字5三个。让你⽤所给的数据组成⼀个最⼩值，0不能放在⾸位。解题策略分析：对于组装数据的策略其实有很多种，但是如果组装成⼀个最⼩值，那么其实我们很容易想到策略其实只有⼀种，即每次都选取规定中的最⼩的值去组装新的数。既然策略只有⼀种，且是⽤给定的数去组成⼀个新的最⼩的数，那么运⽤贪⼼算法之前，我们需要考虑每⼀步组装新值所选取的数据如果是符合规定的最⼩值，那么能不能保证最终的数值是最⼩的。这⾥显⽽易见，每⼀步的⾸位数字是符合规定的最⼩值，那么最终组成的数据也是最⼩的(可以使⽤数学归纳法证明)。所以使⽤贪⼼算法是可以的。例题⼆题⽬：假如现在仓库囤有⼀批同款产品不同规格的货物，货A是30吨，货B是50吨，货C是30吨，总价值分别是，30万，50万，30万，货物A，B，C不可分解。现在有⼈准备收购60吨。那么如何分配呢？解题策略分析：这道题和例题⼀的区别在于，例题⼀策略只有⼀种，就是每次选取最⼩的即可，但是这道题我们⽆法准确定义策略有集中，因为他可能的策略都有可能是最优策略:策略⼀：卖货物价值最⾼的B，50万，但是如果卖A和B会有60万，所以不⾏策略⼆：卖货物最轻的A，C，⼀共60万。看似可⾏，但是我们需要想到的是，这些数据可能是任意的，如果A是10吨，那么A，C只有40万。策略三：卖单价最贵的，我们会发现他们单价是⼀样的，没法选。如果我们在该策略下再制定第⼆策略，优先卖重量⼩的，那么其实就会出现上⾯的策略⼆问题。⾛到这⾥我们就发现，贪⼼算法不能完全处理某⼀策略下的所有数据。因为每⼀步的最优解，会影响后续选择(由于60吨的限制)。我们想⼀下为什么不能使⽤贪⼼算法，那是因为我们⽆法确定贪⼼策略，限制贪⼼策略的原因是ABC不能拆分，不能拆分，就有了上⾯三种可能，但是如果可以拆分，那么策略三是可⾏的，先卖单价最贵的，但是如果单价相同那么得到的结果不是唯⼀的。如何选⽤贪⼼算法并不能总求得问题的整体最优解。但对于某些问题，却总能求得整体最优解，这要看问题是什么了。只要能满⾜贪⼼算法的两个性质：贪⼼选择性质和最优⼦结构性质，贪⼼算法就可以出⾊地求出问题的整体最优解。即使某些问题，贪⼼算法不能求得整体的最优解，贪⼼算法也能求出⼤概的整体最优解。如果你的要求不是太⾼，贪⼼算法是⼀个很好的选择。最优⼦结构性质是⽐较容易看出来的，但是贪⼼选择性质就没那么容易了，这个时候需要证明。证明往往使⽤数学归纳法。例题⼀代码(C++) // Minimun Created by 陈龙// Copyright © 2019 陈龙. All rights reserved.//#include using namespace std;int main(int argc, const char * argv[]) { int t[