【算法设计与分析】01 算法涉及的研究内容概述

1 算法的研究内容

• 算法的研究内容主要包括三点：

1. 计算复杂性理论
2. 问题复杂度概念
3. 算法设计与分析

其中我们主要学习的内容是算法的设计与分析。

在学习算法的过程中，还需要学习相关的概念：

1. 算法的伪码表示
2. 算法及其时间复杂度的定义
3. 几类重要函数的性质
4. 有关函数渐进的届的定理
5. 时间复杂度函数的表示：函数渐进的界

以上五点会在后面的文章中逐一学习。

2 算法设计的两个例子

2.1 调度问题

• 问题：有n项任务，每项任务加工时间已知，从 0时刻开始陆续安排到一台机器上加工，每个任务的完成时间是从 0 时刻到任务加工截止的时间。
• 求：总完成时间 最短的安排方案（所有任务完成时间之和）。

实例：
任务集 S = {1, 2, 3, 4, 5}，
加工时间: t₁=3, t₂=8, t₃=5, t₄=10, t₅=15

• 贪心法的解：

算法：按加工时间(3,8,5,10,15) 从小到大安排

解：加工产品的顺序：1, 3, 2, 4, 5 。

总的完成时间为：

t = 3+(3+5)+(3+5+8)+(3+5+8+10)+(3+5+8+10+15)
= 3×5 + 5×4 + 8×3 + 10×2 + 15
= 94

（注意规律）

针对上面的加工调度问题，在数学中有一整套建模的流程来求解。

问题建模：

1. 输入：任务集：S={1,2,3，…，n}，第j项任务加工时间：t_j $\in$∈ Z⁺ , j=1，2…，n
2. 输出：调度I，S的排列为：i₁，i₂，…，i_n
3. 目标函数：I的完成时间。t(I)= ${\sum }_{k=1}^N(n-k+1)t_{i_k}$∑k=1N​(n−k+1)tik​​
4. 解 I* ：使得t(I*)达到最小，即：t(I *)=min{t(I) | I为S的排列}

对于上述调度问题的贪心算法，对于所有输入实例都得到最优解，可以给出如下的证明过程：

证明：假设调度f的第i，j项任务相邻且有逆序，即t_i > t_j ,交换任务i和j得到调度g，

在算法的设计过程中，各种各样的算法设计都需要有严格的证明验证所有实例都可以通过该算法达到最终的解。上面解决调度问题的时候，是凭直觉来使用贪心算法，但是直觉往往不正确。如下面的例子。

反例：

有4 件物品要装入背包, 物品重量和价值如下:

背包重量限制是 6，问如何选择物品，使得不超重的情况下装入背包的物品价值达到最大?

直觉的解法是贪心算法：单位重量价值大的优先，总重量不超过6.

按照 $\frac{Vi}{Wi}$W i V i ​ 从大到小排序，1,2,3,4

​ $\frac{7}{3}$37​ > $\frac{9}{4}$49​> $\frac{9}{5}$59​ > $\frac{2}{2}$22​

• 贪心法的解： { 1, 4 }，重量 5，价值为 9
• 更好的解： { 2, 4 }，重量 6，价值 11

2.2 算法设计的步骤

所以在进行一个算法的设计时，需要以下几个步骤：

1. 问题建模
2. 选择什么算法，如何描述这个算法？
3. 这个算法是否对所有实例都得到最优解？如何证明？
4. 如果不是，能否找到反例

每一个算法的设计，都需要遵循上述四个规则。

2.3 投资问题

• 问题：m元钱，投资n个项目，效益函数f_i (x)，表示第i个项目投资x元钱的效益，i=1,2，…，n。
• 求：如何分配，每个项目的钱数，使得总效益最大。

实例：5 万元，投资给 4 个项目，效益函数：

x	f1(x)	f2(x)	f3(x)	f4(x)
0	0	0	0	0
1	11	0	2	20
2	12	5	10	21
3	13	10	30	22
4	14	15	32	23
5	15	20	40	24

首先对这个问题进行数学建模：

• 输入：n，m，f_i (x)，i=1,2，…，n，x = 1,2, …, m 。
• 解：n维向量<x₁, x₂, … , x_n >，x_i 是第i个项目的钱数，使得下述条件满足：

目标函数：max ${\sum }_{i=1}^n{f}_i\left(x\right)$∑i=1n​fi​(x)

约束条件： ${\sum }_{i=1}^n{x}_i=m$∑i=1n​xi​=m ，x_i $\in$∈ n;

上述就是一个数学的建模过程，最终的算法设计就是针对上述数学模型进行求解域优化。

在我们学习算法设计之前，先给出这道题的一个蛮力算法：

1. 对所有满足下述条件的向量<x₁,x₂,…,x_n>

   x₁+ x₂ + … + x_n = m ； x_i 为非负整数, i = 1, 2 , …, n 。

2. 计算相应的效益：

   f₁(x₁) + f₂(x₂) + … + f_n(x_n)

从中确认效益最大的向量。

实例计算：

解： s=<1,0,3,1>,
最大效益： 11+30+20 = 61

以上就是使用蛮力算法得出的额结果，结果肯定是对的，但是效率肯定不高。

• 蛮力算法的效率：

方程 x₁ + x₂ + … + x_n = m 的非负整数解
< x₁, x₂, …, x_n > 的个数估计：

可行解表示成 0-1 序列： m 个1,n-1个 0

例如：n=4，m=7。可行解的一个为：<1, 2, 3, 1> ⇔ 序列 1 0 1 1 0 1 1 1 0 1

该解得序列的个数是输入规模的指数函数：

C(m+n-1,m)

= $\frac{(m+n-1)!}{m!(n-1)!}$m!(n−1)!(m+n−1)!​

= Ω ((1+ε )^m+n-1)

指数级是一个很大的数量级！！！有没有更好的算法？ 在后面的学习中，会学习到更好的算法。

3 总结

问题求解的关键：

1. 建模：对输入参数和解给出形式化或者半形式化的描述
2. 设计算法：采用什么算法设计技术？以及它的正确性：是否对所有实例都得到正确的解？
3. 分析算法：效率