22. 基本的图算法 本章介绍图的表示和搜索。 许多的图算法在一开始都会先通过搜索来获得图的结构,其他一些图算法则是对基本的搜索加以优化。 可以说,图的搜索技巧是整个图算法领域的核心。 图的表示 G=(V,E) G = ( V , E ) 图G由结点的集合V 和 边的集合E 组成 可以用两种方法表示,一种是邻接链表(下图b),一种是邻接矩阵(下图c)。 邻接链表一般用于表示稀疏图(边数 |E| | E | 远小于 |V|2 | V | 2 ),默认都使用邻接链表表示。在稠密图( |E| | E | 接近 |V|2 …

2018年6月30日 0条评论 0点热度 阅读全文

16. 贪心算法 求解最优化问题的算法通常需要经过一系列的步骤,在每个步骤都面临多种选择。对于许多最优化问题,使用动态规划算法来求最优解有些杀鸡用牛刀了,可以使用更简单、更高效的算法.贪心算法就是这样的算法,它在每一步都做出当时看起来最佳的选择。也就是说,它总是做出局部最优的选择,寄希望这样的选择能导致全局最优解。 活动选择问题 我们的第一个例子是一个调度竞争共享资源的多个活动的问题,目标是选出一个最大的互相兼容的活动集合。假定有一个 n 个活动的集合 S=a1,a2,...,an S = a 1 , a 2 , …

2018年3月20日 0条评论 0点热度 阅读全文

16. 贪心算法 求解最优化问题的算法通常需要经过一系列的步骤,在每个步骤都面临多种选择。对于许多最优化问题,使用动态规划算法来求最优解有些杀鸡用牛刀了,可以使用更简单、更高效的算法.贪心算法就是这样的算法,它在每一步都做出当时看起来最佳的选择。也就是说,它总是做出局部最优的选择,寄希望这样的选择能导致全局最优解。 活动选择问题 我们的第一个例子是一个调度竞争共享资源的多个活动的问题,目标是选出一个最大的互相兼容的活动集合。假定有一个 n 个活动的集合 S=a1,a2,...,an S = a 1 , a 2 , …

2018年3月20日 0条评论 0点热度 阅读全文