最近复习了算法导论部分内容,感觉好陌生啊。记得研一老师只上了算法入门,其余的章节班级分组学习讲解,我只记得我们那一组负责的内容,有关图论、Dijkstra之类的。这两天看了动态、贪心算法,感觉这个真的很不错,以前只忙于准备自己的章节,也没有细细学习和体会。
总体感觉(个人的理解,不一定准确),动态规划的核心步骤是分析问题,描述出解的递推公式,这个类似于高中学得数列只是更加复杂一些,毕竟数列大部分能笔算出来,而动态规划中就必须借助程序来解了。然后自底向上计算出解。所谓自底向上,从初始值开始计算各个值,并维护一个table来存储这些值,后面计算的值往往会用到前面计算的值,有点空间换时间的意思。
直接写例子吧,这个例子实际上用贪心算法更加简单易解,这里用动态规划实现旨在学习动态规划了。假设有n个活动集合S = {a1,a2,.....an},每个活动ai有开始时间si小于其结束时间fi,即ai活动的时间区间[si, fi),如果[si, fi)和[sj, fj)互不重叠,则称ai和aj两个活动为兼容,问题:选出一组最大(包含最多的活动个数)的一组兼容活动。
1.首先为简化问题,我们对集合S以结束时间先后排序,即有
f0 < f1 < f2 ... < fn+1 时间复杂度为 nlg(n)
2.找最优子结构:
定义 S(ij)是S中活动的子集,其中每个活动在ai结束之后开始,且在aj开始之前结束。并引入虚拟活动a0与an+1,f0 = 0, sn+1 = NaN(暂且表示无穷大吧)。Sij = empty(暂且表示空集)。于是有:
a) 当 i >= j 时,Sij = empty
b) 假设Sij的解包含ak,即有fi <= sk < fk <= fj,则 Sij = Sik ∪ ak ∪ Skj
若用Cij表示Sij的活动个数,有Cij = Cik + 1 + Ckj
3. 于是有递归解:
Cij = 0 如果 Sij = empty
Cij = max{Cik + Ckj + 1} i < k < j,ak属于Sij 如果Sij != empty
用C[i][j]来记录中间计算的Cij的值,A[i][j]来记录中间计算的Sij集合,所以可以写出算法了:
SELECT_ACTIVITY(s,f,n)
for i <- 0 to n+1
do for j <- 0 to i
do c[i][j] <- 0;
A[i][j] <- empty;
//一半的table值已填满,然后以与对角线平行一行一行填写剩下的半个table
for t <- 1 to n+1
do for i <- 0 to n+1-t
do j = i + t;
if f[i] >= s[j] //第i个活动结束之前第j个活动已开始
then c[i][j] <- 0;
A[i][j] <- empty;
else
for k <- i+1 to j-1
do
if s[k] >= f[i] and f[k] <= s[j]
then
if c[i][j]< c[i][k] + c[k][j] + 1
then c[i][j] <- c[i][k] + c[k][j] + 1;
A[i][j] <- A[i][k] ∪ k ∪ A[k][j];
这个本是贪心算法的一个例子,这里是学习动态规划,所以用了比贪心算法繁琐的解法。呵呵,明天将伪代码改称java代码实现并分析之。
分享到:
相关推荐
通过分析和运行“动态规划代码”,我们可以深入理解这些算法的工作原理,进一步提升编程能力和问题解决技巧。这些代码实例对于初学者来说是宝贵的教育资源,也是专业人士进行算法研究和实践的重要参考资料。
《算法分析与设计教案》是王晓东教授针对算法分析与设计这一重要计算机科学主题编写的教学资料,旨在帮助学生深入理解和掌握算法的核心概念、设计方法以及分析技巧。在这个压缩包中,包含的主要文件名为“计算机算法...
8. 贪心算法:介绍了一类局部最优解能导致全局最优解的算法策略,如霍夫曼编码和活动选择算法。 9. 回溯法和分支限界法:用于解决组合优化问题,如八皇后问题和旅行商问题。 10. 分治策略:通过将大问题分解为小...
活动选择问题(Activity Selection Problem)是组合优化中的一个问题,涉及到安排一系列活动,每个活动都有一个开始时间和结束时间,并且在任何给定时间只能进行一个活动。如果题目描述的含义是:在一组活动集合S中...
《数据结构与算法分析——Java语言描述》是一本深度探讨数据结构和算法的书籍,它以Java编程语言为载体,详细阐述了各种重要的数据结构及其相关的算法实现。这本书对于计算机科学的学习者,尤其是软件开发者来说,是...
8. **贪心算法**:贪心算法在局部最优解的基础上寻找全局最优解,如霍夫曼编码、活动选择问题等。 9. **回溯法与分支限界**:这些是解决约束满足问题和组合优化问题的有效方法,如八皇后问题、旅行商问题等。 10. ...
在C++中,贪心法可用于解决如最小生成树(Kruskal's 或 Prim's 算法)、活动选择、背包问题等。在课件中,你可以期待看到如何用C++伪代码来描述这些贪心算法的实现。 **动态规划法** 动态规划(Dynamic ...
《算法分析与设计》期末考试复习题涉及到多个关键知识点,主要涵盖了算法设计策略、算法分析方法以及特定算法的实现。以下是这些知识点的详细说明: 1. **动态规划**: - 动态规划算法通常用于解决具有最优子结构...
- 贪心算法在每一步选择最优解,如霍夫曼编码、活动安排问题等。 3. **设计模式** - **工厂模式**:用于创建对象,提供一个接口创建一系列相关或相互依赖的对象,无需指定具体类。 - **单例模式**:确保一个...
《数据结构与算法分析:C语言描述》是一本深度探讨数据结构和算法的书籍,它以C语言作为实现工具,为读者提供了清晰、直观的代码示例,帮助读者理解和掌握这些核心概念。这本书的主要目标是使读者能够设计、分析和...
算法分析主要关注算法的时间复杂度和空间复杂度,时间复杂度描述了算法执行速度,而空间复杂度则反映了算法在运行过程中占用的内存。例如,排序算法有冒泡排序、插入排序、选择排序、快速排序、归并排序和堆排序等,...
- 冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序:各种常见排序算法及其时间复杂度分析。 - 查找算法:顺序查找、二分查找、哈希查找等。 4. **图算法**: - 深度优先搜索(DFS)和广度...
《数据结构与算法分析—C语言描述》是计算机科学领域一本经典的教材,主要面向那些希望深入理解数据结构和算法的读者。这本书通过C语言来阐述数据结构和算法的设计、实现与分析,帮助读者掌握如何有效地处理和组织...
数据结构与算法分析是计算机科学中的核心领域,它关乎如何高效地存储和处理数据,以及设计和实现解决问题的计算步骤。在C++编程语言中,数据结构和算法的实现提供了强大的工具,使得开发者能够构建高性能的软件系统...
数据结构与算法分析是计算机科学中的核心领域,它关乎如何高效地存储和处理信息,以及设计和实现高效的计算过程。这份“数据结构与算法分析学习笔记”由罗聪编著,包含了丰富的源代码实例,旨在帮助读者深入理解并...
例如,霍夫曼编码和活动选择问题。 8. **回溯法与分支限界法**:用于解决组合优化问题,如八皇后问题、N皇后问题等。它们通过尝试所有可能的解决方案,然后在遇到无效解时回退。 9. **数据结构**:数组、链表、栈...
综上所述,算法分析与设计涵盖了多种解决问题的策略和技术,包括递归、分治法、动态规划、贪心算法、回溯法、分支限界法以及计算模型与复杂度分析。通过对这些技术的学习和掌握,能够有效地解决实际中的复杂问题,并...
《数据结构与算法分析(Java语言描述版本)》是一本深度探讨数据结构和算法的权威著作,对于理解和掌握计算机科学的基础至关重要。这本书以其清晰的Java实现,为读者提供了丰富的实例和深入的理论解析,帮助读者在...
- 探索动态规划和贪心算法的区别,理解何时贪心策略适用,何时需要更全面的动态规划方法。 - 学习并练习使用C++ STL的高级特性,如迭代器、函数对象和模板元编程,以提高代码效率和可读性。 总之,这个压缩包提供...
8. **排序算法**:如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等,书中会分析它们的时间复杂度和适用场景。 9. **查找算法**:线性查找、二分查找、哈希查找等,以及它们在不同数据结构上的应用。...