货郎问题与计算复杂性理论

双机调度

双机调度问题：有n项任务, 任务 i 的加工时间为$t_i , t_i ∈Z^+$ti​,ti​∈Z+, i=1,2,…,n. 用两台相同的机器加工，从0时刻开始计时，完成时间是后停止加工机器的停机时间. 问如何把这些任务分配到两台机器上，使得完成时间达到最小？
实例: 任务集 S ={1,2,3,4,5,6}
$t_1=3, t_2=10, t_3=6, t_4=2, t_5=1, t_6=7$t1​=3,t2​=10,t3​=6,t4​=2,t5​=1,t6​=7

解：机器 1 的任务：1, 2, 4
机器 2 的任务：3, 5, 6
完成时间 ： max{ 3+10+2, 6+1+7 }=15

双机调度建模

解: 0-1向量$<x_1, x_2, ..., x_n>, x_i=1$<x1​,x2​,...,xn​>,xi​=1表示任务 i
分 配到第一台机器，i =1,2,…,n.

不妨设机器1的加工时间 ≤ 机器2的加工时
间令$T=t_1+t_2+...+t_n, D=\left \lfloor T/2 \right \rfloor$T=t1​+t2​+...+tn​,D=⌊T/2⌋ ，机器1的加工
时间不超过D，且达到最大.

如何对该问题建模?目标函数与约束条件是什么？

---

NP-hard问题

• 这样的问题有数千个，大量存在于各个应用领域.

• 至今没有人能够证明对于这类问题不存在多项式时间的算法.
• 至今没找到有效算法：现有的算法的运行时间是输入规模的指数或更高阶函数.
• 从是否存在多项式时间算法的角度看，这些问题彼此是等价的. 这些问题的难度处于可有效计算的边界.

---

Algorithm + Data Structure= Programming

好的算法

• 提高求解问题的效率
• 节省存储空间

算法设计技术
算法分析方法
问题复杂度分析
计算复杂性理论

算法的研究目标

• 问题→建模并寻找算法
• 算法→算法的评价
• 算法类→问题复杂度估计
• 问题类→能够求解的边界

算法研究的重要性

算法设计与分析技术在计算机科学与技术领域有着重要的应用背景
算法设计分析与计算复杂性理论研究是计算机科学技术的核心研究领域

• 1966-2005期间，Turing奖获奖50人, 其中10人以算法设计, 7人以计算理论、自动机和复杂性研究领域的杰出贡献获奖
• 计算复杂性理论的核心课题“P=NP?”
  是本世纪 7个最重要的数学问题之一

提高学生素质和分析问题解决问题的能力，培养计算思维

---

小结

• NP-hard问题的几个例子：货郎问题
0-1背包问题、双机调度问题等
• NP-hard问题的计算现状
• 计算复杂性理论的核心——NP完全理论
• 算法研究的主要内容及重要意义

算法及其时间复杂度

问题及实例

• 问题
需要回答的一般性提问，通常含若干参数

• 问题描述
定义问题参数(集合,变量,函数,序列等)
说明每个参数的取值范围及参数间的关系
定义问题的解
说明解满足的条件(优化目标或约束条件)

• 问题实例
参数的一组赋值可得到问题的一个实例

---

算法

• 算法
有限条指令的序列
这个指令序列确定了解决某个问题的一系列运算或操作
• 算法 A 解问题 P
把问题 P 的任何实例作为算法 A 的输入每步计算是确定性的
A 能够在有限步停机输出该实例的正确的解

---

基本运算与输入规模

• 算法时间复杂度: 针对指定基本运算,计数算法所做运算次数
• 基本运算: 比较, 加法, 乘法, 置指针, 交换…
• 输入规模：输入串编码长度
通常用下述参数度量：数组元素多少，调度问题的任务个数，图的顶点数与边数等.
• 算法基本运算次数可表为输入规模的函数
• 给定问题和基本运算就决定了一个算法类

---

输入规模

• 排序：数组中元素个数 n
• 检索：被检索数组的元素个数 n
• 整数乘法：两个整数的位数 m, n
• 矩阵相乘：矩阵的行列数 i, j, k
• 图的遍历：图的顶点数 n, 边数 m
…

---

基本运算

• 排序: 元素之间的比较
• 检索: 被检索元素 x与数组元素的比较
• 整数乘法: 每位数字相乘(位乘) 1 次
m位和n位整数相乘要做mn次位乘
• 矩阵相乘: 每对元素乘 1 次
i×j矩阵与 j×k 矩阵相乘要做 i jk 次乘法
• 图的遍历: 置指针
…

---

算法的两种时间复杂度

对于相同输入规模的不同实例，算法的基本运算次数也不一样，可定义两种时间复杂度

最坏情况下的时间复杂度 W(n)
算法求解输入规模为 n 的实例所需要的最长
时间

平均情况下的时间复杂度 A(n)
在给定同样规模为 n 的输入实例的概率分布
下，算法求解这些实例所需要的平均时间

---

A(n) 计算公式

平均情况下的时间复杂度 A(n)
设 S 是规模为 n 的实例集
实例 I∈S 的概率是 $P_I$PI​
算法对实例 I 执行的基本运算次数是 $t_I$tI​

$A(n) =\sum_{I\in S} P_It_I$A(n)=∑I∈S​PI​tI​

在某些情况下可以假定每个输入实例概率相等

---

例子：检索

检索问题
输入：非降顺序排列的数组 L，元素数为 n； 数 x
输出： j
若 x 在 L中，j 是 x 首次出现的下标；
否则 j = 0
基本运算：x 与 L中元素的比较

---

顺序检索算法

j=1, 将x与L[j]比较. 如果 x=L[j]，则算法停止，输出 j；如果不等，则把 j 加1，继续x与L[j]的比较，如果 j>n，则停机并输出0.

实例:

1

2

3

4

5

x = 4，需要比较 4 次
x = 2.5，需要比较 5 次

---

最坏情况的时间估计

不同的输入有 2n + 1个，分别对应：
x = L[1], x = L[2], … , x = L[n]
x<L[1], L[1]<x<L[2], L[2]<x<L[3], … , L[n]<x
最坏情况下时间：W(n) = n
最坏的输入：x 不在 L中或 x = L[n]要做 n 次比较

---

改进顺序检索算法

j=1, 将 x与L[j]比较. 如果 x=L[j]，则算法停止，输出 j；如果 x >L[j]，则把 j 加1，继续 x与 L[j]的比较；如果 x < L[j]，则停机并输出0. 如果 j >n，则停机并输出 0.

实例:

1

2

3

4

5

x = 4，需要比较 4 次
x = 2.5，需要比较 3 次

时间估计

最坏情况下：W(n) = n

平均情况下
输入实例的概率分布：假设 x 在 L 中每个
位置与空隙的概率都相等

改进检索算法平均时间复杂度是多少?

小结：

• 算法最坏和平均情况下的时间复杂度定义
• 如何计算上述时间复杂度