永春网站设计,wordpress进入后台,徐州人才网前程无忧,免费做海报的app文章目录1 算法的研究内容2 算法设计的两个例子2.1 调度问题2.2 算法设计的步骤2.3 投资问题3 总结在学习算法涉及与分析的内容之前#xff0c;先了解一下算法所涉及的几个大块的内容#xff0c;方便以后学习。1 算法的研究内容
算法的研究内容主要包括三点#xff1a;
计…
文章目录1 算法的研究内容2 算法设计的两个例子2.1 调度问题2.2 算法设计的步骤2.3 投资问题3 总结在学习算法涉及与分析的内容之前先了解一下算法所涉及的几个大块的内容方便以后学习。1 算法的研究内容
算法的研究内容主要包括三点
计算复杂性理论问题复杂度概念算法设计与分析
其中我们主要学习的内容是算法的设计与分析。
在学习算法的过程中还需要学习相关的概念
算法的伪码表示算法及其时间复杂度的定义几类重要函数的性质有关函数渐进的届的定理时间复杂度函数的表示函数渐进的界
以上五点会在后面的文章中逐一学习。
2 算法设计的两个例子
2.1 调度问题
问题有n项任务每项任务加工时间已知从 0时刻开始陆续安排到一台机器上加工每个任务的完成时间是从 0 时刻到任务加工截止的时间。求总完成时间 最短的安排方案所有任务完成时间之和。 实例 任务集 S {1, 2, 3, 4, 5} 加工时间: t13, t28, t35, t410, t515 贪心法的解
算法按加工时间(3,8,5,10,15) 从小到大安排
解加工产品的顺序1, 3, 2, 4, 5 。 总的完成时间为
t 3(35)(358)(35810)(3581015) 3×5 5×4 8×3 10×2 15 94
注意规律
针对上面的加工调度问题在数学中有一整套建模的流程来求解。
问题建模
输入任务集S{1,2,3…n}第j项任务加工时间tj ∈\in∈ Z , j12…n输出调度IS的排列为i1i2…in目标函数I的完成时间。t(I)∑k1N(n−k1)tik\sum_{k1}^N (n-k1)t_{i_{k}}∑k1N(n−k1)tik解 I* 使得t(I*)达到最小即t(I *)min{t(I) | I为S的排列}
对于上述调度问题的贪心算法对于所有输入实例都得到最优解可以给出如下的证明过程
证明假设调度f的第ij项任务相邻且有逆序即ti tj ,交换任务i和j得到调度g 在算法的设计过程中各种各样的算法设计都需要有严格的证明验证所有实例都可以通过该算法达到最终的解。上面解决调度问题的时候是凭直觉来使用贪心算法但是直觉往往不正确。如下面的例子。
反例
有4 件物品要装入背包, 物品重量和价值如下:
标号1234重量 wi3452价值 vi7992
背包重量限制是 6问如何选择物品使得不超重的情况下装入背包的物品价值达到最大?
直觉的解法是贪心算法单位重量价值大的优先总重量不超过6.
按照ViWi\frac{V~i~}{W~i~}W i V i 从大到小排序1,2,3,4
73\frac{7}{3}37 94\frac{9}{4}49 95\frac{9}{5}59 22\frac{2}{2}22
贪心法的解 { 1, 4 }重量 5价值为 9更好的解 { 2, 4 }重量 6价值 11
2.2 算法设计的步骤
所以在进行一个算法的设计时需要以下几个步骤
问题建模选择什么算法如何描述这个算法这个算法是否对所有实例都得到最优解如何证明如果不是能否找到反例
每一个算法的设计都需要遵循上述四个规则。
2.3 投资问题
问题m元钱投资n个项目效益函数fi (x)表示第i个项目投资x元钱的效益i1,2…n。求如何分配每个项目的钱数使得总效益最大。 实例5 万元投资给 4 个项目效益函数 xf1(x)f2(x)f3(x)f4(x)00000111022021251021313103022414153223515204024首先对这个问题进行数学建模
输入nmfi (x)i1,2…nx 1,2, …, m 。解n维向量x1, x2, … , xn xi 是第i个项目的钱数使得下述条件满足 目标函数max∑i1nfi(x)\sum_{i1}^n f_i (x)∑i1nfi(x) 约束条件∑i1nxim\sum_{i1}^n x_i m∑i1nxim xi ∈\in∈ n; 上述就是一个数学的建模过程最终的算法设计就是针对上述数学模型进行求解域优化。
在我们学习算法设计之前先给出这道题的一个蛮力算法 对所有满足下述条件的向量x1,x2,…,xn x1 x2 … xn m xi 为非负整数, i 1, 2 , …, n 。 计算相应的效益 f1(x1) f2(x2) … fn(xn)
从中确认效益最大的向量。
实例计算 解 s1,0,3,1, 最大效益 113020 61
以上就是使用蛮力算法得出的额结果结果肯定是对的但是效率肯定不高。
蛮力算法的效率
方程 x1 x2 … xn m 的非负整数解 x1, x2, …, xn 的个数估计
可行解表示成 0-1 序列 m 个1,n-1个 0 例如n4m7。可行解的一个为1, 2, 3, 1 ⇔ 序列 1 0 1 1 0 1 1 1 0 1
该解得序列的个数是输入规模的指数函数
C(mn-1,m)
(mn−1)!m!(n−1)!\frac{(mn-1)!}{m! (n-1)!}m!(n−1)!(mn−1)! Ω ((1ε )mn-1)
指数级是一个很大的数量级有没有更好的算法 在后面的学习中会学习到更好的算法。
3 总结
问题求解的关键
建模对输入参数和解给出形式化或者半形式化的描述设计算法采用什么算法设计技术以及它的正确性是否对所有实例都得到正确的解分析算法效率
