智能算法调查
调查
调查一个智能算法的优点、缺点、适用范围、优化。要求尽量是组合算法。
贪心算法(又称贪婪算法)是指,在对问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。
优点:用贪婪法设计算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。
缺点:它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解,虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪婪法不要回溯。
适用范围: 贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
优化:对某问题能选择出最优量度标准后,用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到,根据当前状态做出在当前看来是最好的选择,即局部最优解选择,然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题,最终可得到问题的一个整体最优解。
实际案例:
结合调查的智能算法举出一个实例
0-1背包问题:有一个背包,背包容量是M=150。有7个物品,物品不可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
:目标函数:∑pi最大
约束条件是装入的物品总重量不超过背包容量:∑wi<=M(M=150)
⑴根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优?
⑵每次挑选所占重量最小的物品装入是否能得到最优解?
⑶每次选取单位重量价值最大的物品,成为解本题的策略。
值得注意的是,贪心算法并不是完全不可以使用,贪心策略一旦经过证明成立后,它就是一种高效的算法。
贪心算法还是很常见的算法之一,这是由于它简单易行,构造贪心策略不是很困难。可惜的是,它需要证明后才能真正运用到题目的算法中。
一般来说,贪心算法的证明围绕着:整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于例题中的3种贪心策略,都是无法成立(无法被证明)的,解释如下:
⑴贪心策略:选取价值最大者。
反例:W=30
物品:A B C
重量:28 12 12
价值:30 20 20
根据策略,首先选取物品A,接下来就无法再选取了,可是,选取B、C则更好。
⑵贪心策略:选取重量最小。它的反例与第一种策略的反例差不多。
⑶贪心策略:选取单位重量价值最大的物品。
反例:W=30
物品:A B C
重量:28 20 10
价值:28 20 10
根据策略,三种物品单位重量价值一样,程序无法依据现有策略作出判断,如果选择A,则答案错误。
【注意:如果物品可以分割为任意大小,那么策略3可得最优解】
对于选取单位重量价值最大的物品这个策略,可以再加一条优化的规则:对于单位重量价值一样的,则优先选择重量小的!这样,上面的反例就解决了。
分析
分析该算法在电力行业的应用
一个电厂的发电容量一定M,若干机组n,每个机组的发电量不同
,每个机组的收益为
,一部分机组投入生产就会得到
的收益,(0≦
≦1,
>0)采用怎样的生产方式才能使收益最大。
s.t
,
>0,
>0,
_1234567893.unknown
_1234567895.unknown
_1234567897.unknown
_1234567899.unknown
_1234567900.unknown
_1234567898.unknown
_1234567896.unknown
_1234567894.unknown
_1234567891.unknown
_1234567892.unknown
_1234567890.unknown