注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

小木舟的博客

笔墨生活随想,记录似水年华。

 
 
 

日志

 
 

贪婪算法(Greedy Algorithm) - Flex实现  

2011-12-16 16:27:42|  分类: 课程学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
贪婪算法(Greedy Algorithm) - Flex实现 - 小木舟 - 小木舟的博客 

1. 概念贪心算法(Greedy Algorithm) - Flex实现 - 小木舟 - 小木舟的博客

贪婪算法(Greedy Algorithm),又称为贪心算法,它是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致最终结果是最好或最优的算法。所谓的“贪婪”,体现于每次在所有的候选项中都专挑最好或者最佳的。

2. 特性

贪婪算法每一步的选择都必须满足以下三个条件:

  - 可行的:满足问题的约束条件。

  - 局部最优:当前状态中所有可行选择中最佳的局部选择。

  - 不可取消:也称不可回退,即选择一旦做出,在后面的步骤中就无法改变。

贪婪算法不可回退的特性让它区别于动态规划。动态规划会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。

3. 适用场景

贪婪算法在最优子结构的问题中最为有效。最优子结构的意思是局部最优解能解决全局最优解,也即是说,问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。一般来讲,贪婪法只能应用于最优化问题,对于其他的问题,贪婪法通常得不到所要求的答案。最优化问题,例如求最小生成树、哈夫曼编码、单起点最短路径等。

4. 几个最优化问题

     求最小生成树(Minimum Spanning Tree

最小生成树的概念详见这里。求最小生成树的方法有Prim算法、Kruskal算法等。

Prim算法Prim算法是求一个给定的加权连通图最小生成树的问题的一种算法,它通过一系列不断扩张的子树来构造一棵最小生成树。算法伪码如下图:

贪心算法(Greedy Algorithm) - Flex实现 - 小木舟 - 小木舟的博客

  Kruskal算法:把一个加权连通图G=<V,E>的最小生成树看作是一个具有|V|-1条边的无环子图,并且边的权重和是最小的。该算法通过对子图的一系列扩展来构造一棵最小生成树,这些子图总是无环的。算法伪码如下图:

贪心算法(Greedy Algorithm) - Flex实现 - 小木舟 - 小木舟的博客

  其中,Kruskal算法需要判断新添加进来的边是否会导致新的子图出现回路,在具体算法程序的实现中,使用了高效的并查算法union-find来判断是否存在回路。

—     单起点最短路径问题

单起点最短路径问题是指对于加权连通图的一个称为起点的给定顶点,求出它到所有其他顶点之间的一系列最短路径。要求的是一组路径,每条路径都从起点出发通向图的一个不同起点。

解决单起点最短路径问题最著名的算法是Dijkstra算法,但该算法只能应用于不含负权重的图,它的算法思想是:按照从给定起点到图中顶点的距离,顺序求出最短的路径。首先,它求出从起点到最接近起点的顶点之间的最短路径,然后求出第二近的,以此类推。该算法的伪码和Prim算法的相类似,区别在于顶点的最短权重标记:Prim指的是顶点到树的最短距离,Dijkstra指的是顶点到起始点的最短距离。

—     哈夫曼树(Huffman Tree

哈夫曼树是一棵最优二叉树,而相应的哈夫曼编码则是不等长编码,它是一种重要的文件压缩方法。

哈夫曼算法的思想:

l  初始化n个单节点的树,并为它们标上字母表中的字符。把每个字符的概率记在树根中,用来指出树的权重。

l  重复下面的步骤,直到只剩一颗单独的树。找到两棵权重最小的树。把它们作为新树中的左右子树,并把其权重之和作为新的权重记录在新树的根中。

5. Flex实现的程序

 —       开发环境

贪心算法(Greedy Algorithm) - Flex实现 - 小木舟 - 小木舟的博客

 —       源码以及演示程序

源码:http://jasonstudio.googlecode.com/svn/trunk/GreedyTechnique/

    l  演示程序:http://jasonstudio.googlecode.com/svn/trunk/GreedyTechnique/bin-release/GreedyTechnique.html

    l  程序主要用以演示,因此功能写得不完整,操作需要遵循以下简单流程:

     Prim算法、Kruskal算法、Dijkstra算法三个程序的使用:

贪心算法(Greedy Algorithm) - Flex实现 - 小木舟 - 小木舟的博客
 
  Huffman算法的操作:


贪心算法(Greedy Algorithm) - Flex实现 - 小木舟 - 小木舟的博客

—       程序效果截图

贪心算法(Greedy Algorithm) - Flex实现 - 小木舟 - 小木舟的博客

—       参考

小木舟推荐阅读:
  评论这张
 
阅读(1098)| 评论(2)
推荐

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017