以简单组合优化为例讨论计算复杂性

此为课题组所指导本科生和低年级硕士生学习组合优化问题汇报
所用教材：北京大学屈婉玲教授《算法设计与分析》
课程资料：https://www.icourse163.org/course/PKU-1002525003
承诺不用于任何商业用途，仅用于学术交流和分享

• 更多内容请关注课题组官方中文主页：https://JaywayXu.github.io/zh-cn/

1. 简单TSP(1.4)

• 问题描述：有$n$个城市, 已知任两个城市之间的距离. 求一条每个城市恰好经过 1 次的回路,使得总长度最小.
• 实例：
  
• 输入：有穷个城市的集合 C = { c 1 , c 2 , … , c n } C=\left\{c_1, c_2, \ldots, c_n\right\} C={c1​,c2​,…,cn​}, 距离$d\left(c_i,c_j\right)=d\left(c_j,c_i\right)\in {\mathbf{Z}}^{+},1\le i<j\le n$
• 解：$1,2\dots ,n$的排列$k_1,k_2,\dots ,k_n$使得:

$$\min \left\{\sum _{i=1}^{n-1}d\left(c_{k_i},c_{k_{i+1}}\right)+d\left(c_{k_n},c_{k_1}\right)\right\}$$

• 现状：至今没找到有效的算法

2. 背包问题（knapsack Problem）(5.7)

• 一个旅行者随身携带一个背包. 可以放入背包的物品有$n$种, 每种物品的重量和价值分别为$w_i,v_i$. 如果背包的最大重量限制是$b$, 每种物品可以放多个. 怎样选择放入背包的物品以使得背包的价值最大？不妨设上述$w_i,v_i,b$都是正整数.

建模

• 解是$⟨x_1,x_2,\dots ,x_n⟩$, 其中$x_i$是装入背包的第$i$种物品个数
• 目标函数$\max {\sum }_{i=1}^n{v}_i{x}_i$
• 约束条件${\sum }_{i=1}^n{w}_i{x}_i\le b,x_i\in \mathrm{N}$
• 线性规划问题: 由线性条件约束的线性函数取最大或最小的问题
• 整数规划问题: 线性规划问题的变量$\mathbf{x}$都是韭负整数

2.1. 0-1背包(1.4)

*$0-1$背包问题: 有$\mathbf{n}$个件物品要装入背包,第$i$件物品的重量$w_i$, 价值$v_i,i=1,2,\dots ,n$. 背包最多允许装入的重量为$\mathbf{B}$，问如何选择装入背包的物品, 使得总价值达到最大? （每种物品只能装一件）

• 实例：n=4, B=6， 物品的重量和价值如下：
  $$\begin{array}{ccccc}\text{ 标号 }& 1& 2& 3& 4\\ \text{ 重量 }{\mathbf{w}}_{\mathbf{i}}& 3& 4& 5& 2\\ \text{ 价值 }{\mathbf{v}}_{\mathbf{i}}& 7& 9& 9& 2\end{array}$$

问题建模

• 问题的解：0-1向量$<x_1,x_2,\dots ,x_n>$$x_i=1\iff$物品$i$装入背包
• 目标函数：$\max {\sum }_{i=1}^n{v}_i{x}_i$
• 约束条件：${\sum }_{i=1}^n{w}_i{x}_i\le B$,$x_i=0,1,i=1,2,\dots ,n$

2.2. 简单最优装载问题(7.4)

• 问题描述：$n$个集装箱$1,2,\dots ,n$装上轮船, 集装箱$i$的重量$w_i$, 轮船装载重量限制为$C$, 无体积限制. 问如何装使得上船的集装箱最多？不妨设每个箱子的重量$w_i\le C$.
• 问题分析：该问题是$0-1$背包问题的子问题. 集装箱相当于物品, 物品重量是$w_i$, 价值$v_i$都等于 1 , 轮船载重限制$C$相当于背包重量限制$\mathbf{b}$.

问题建模

• 设$<x_1,x_2,\dots ,x_n>$表示解向量,$x_i=0,1$,$x_i=1$当且仅当第$i$个集装箱装上船

• 目标函数$\max {\sum }_{i=1}^n{x}_i$

• 约束条件${\sum }_{i=1}^n{w}_i{x}_i\le C，x_i=0,1i=1,2,\dots ,n$

2.3 背包问题分类(5.7)

• 物品数受限背包: 第$i$种物品最多用$n_i$个 0 -1背包问题:$x_i=0,1,i=1,2,\dots ,n$
• 多背包问题:$m$个背包, 背包$j$装入最大重量$B_j,j=1,2,\dots ,m$. 在满足所有背包重量约束条件下使装入物品价值最大.
• 二维背包问题: 每件物品有重量${\mathbf{w}}_i$和体积${\mathbf{t}}_{\mathbf{i}},\mathbf{i}=1,2,\dots ,n$, 背包总重不超过$\mathbf{b}$,体积不超过$V$, 如何选择物品以得到最大价值。

3. 简单调度问题

3.1 双机调度(1.4)

• 问题描述：双机调度问题: 有$n$项任务, 任务$i$的加工时间为$t_i,t_i\in {\mathbf{Z}}^{+},i=1,2,\dots ,n$. 用两台相同的机器加工, 从 0 时刻开始计时, 完成时间是后停止加工机器的停机时间. 问如何把这些任务分配到两台机器上, 使得完成时间达到最小?
• 实例：假设有任务集合 任务集  S = { 1 , 2 , 3 , 4 , 5 , 6 } \text { 任务集 } S=\{1,2,3,4,5,6\}  任务集 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$。
• 实例解：设有一解：机器 1 的任务:$1,2,4$，机器 2 的任务:$3,5,6$，则完成时间为： max ⁡ { 3 + 10 + 2 , 6 + 1 + 7 } = 15 \max \{3+10+2,6+1+7\}=15 max{3+10+2,6+1+7}=15

双机调度问题建模

1. 问题描述：

该问题属于经典的双机调度问题（Two-Machine Scheduling Problem），目标是将任务分配给两台机器，使得完成时间（即两台机器中最晚的完成时间）最小。

2. 模型建模：

1. 决策变量：
   定义 0-1 决策变量$x_i$，其中：

   • $x_i=1$表示任务$i$被分配到机器 1；
   • $x_i=0$表示任务$i$被分配到机器 2；
   • $i=1,2,\dots ,n$，其中$n$是任务的数量。

2. 目标函数：
   目标是最小化机器的最大完成时间（Makespan），即：

$$\min \left(\max \left(\sum _{i=1}^n{x}_i{t}_i,\sum _{i=1}^n(1-x_i)t_i\right)\right)$$

• ${\sum }_{i=1}^n{x}_i{t}_i$表示分配给机器 1 的总加工时间；
• ${\sum }_{i=1}^n(1-x_i)t_i$表示分配给机器 2 的总加工时间；
• 最大值函数$\max$取两台机器中加工时间较大的那个作为目标最小化的值。

3. 约束条件：
   • 每个任务$i$都必须分配给一台机器上：
     x i ∈ { 0 , 1 } , i = 1 , 2 , … , n x_i \in \{0, 1\}, \quad i = 1, 2, \dots, n xi​∈{0,1},i=1,2,…,n
   • 加工时间是整数非负值：
     $t_i\in {\mathbf{Z}}^{+},i=1,2,\dots ,n$

当然，也可以不妨设机器 1 的加工时间$\le$机器 2 的加工时间令$T=t_1+t_2+\dots +t_n,D=\lfloor T/2\rfloor$, 机器 1 的加工时间不超过$D$, 且达到最大.

另一种建模方式

问题描述：

我们有$n$项任务，每项任务$i$的加工时间为$t_i$，两台相同的机器开始工作，目的是将任务分配给两台机器，使得满足约束条件的同时完成时间最小。完成时间是后停止加工的机器的停机时间。

目标：

根据图片中的约束，目标是最大化机器 1 的加工时间，但其总加工时间不能超过$D=\lfloor \frac{T}{2}\rfloor$，其中$T=t_1+t_2+\cdots +t_n$。

模型建模：

1. 决策变量：
   定义 0-1 决策变量$x_i$：

   • $x_i=1$表示任务$i$被分配到机器 1；
   • $x_i=0$表示任务$i$被分配到机器 2；
   • 其中$i=1,2,\dots ,n$，$n$是任务的数量。

2. 目标函数：
   目标是最大化机器 1 的加工时间，但不能超过$D$：
   $\max \left({\sum }_{i=1}^n{x}_i{t}_i\right)$
   满足：
   $$D=\lfloor \frac{T}{2}\rfloor ,T=t_1+t_2+\cdots +t_n$$
   其中$T$是所有任务总的加工时间。

3. 约束条件：

   • 约束 1：机器 1 的总加工时间不能超过$D$：
     $$\sum _{i=1}^n{x}_i{t}_i\le D$$
   • 约束 2：机器 1 和机器 2 共同完成所有任务，总任务时间应为$T$：
     $$\sum _{i=1}^n{x}_i{t}_i+\sum _{i=1}^n(1-x_i)t_i=T$$
   • 决策变量的取值限制：
     x i ∈ { 0 , 1 } , i = 1 , 2 , … , n x_i \in \{0, 1\}, \quad i = 1, 2, \dots, n xi​∈{0,1},i=1,2,…,n

总结：

该模型的目标是在机器 1 的加工时间尽量大的前提下，不超过给定的阈值$D$，剩余的任务则分配到机器 2。通过这个建模方法，任务被合理分配，以实现优化目标。

3.2 最小延迟调度(7.5)

• 问题描述：客户集合$A,\forall i\in A,t_i$为服务时间（即需要为客户i服务的工时）,$d_i$为要求完成时间（即客户要求的任务完成DDL）,$t_i,d_i$为正整数. 一个调度$f:A\to \mathrm{N},f(i)$为客户$i$的开始时间. 求最大延迟达到最小的调度（每个任务的延迟-即为其实际开始时间+工时-约定的DDL。而所有任务中最大的延迟即为这个问题的最大延迟。目标是使这个任务集合的最大延迟最小）, 即求$f$使得：

min ⁡ f { max ⁡ i ∈ A { f ( i ) + t i − d i } } ∀ i , j ∈ A , i ≠ j , f ( i ) + t i ≤ f ( j ) or  f ( j ) + t j ≤ f ( i ) \begin{aligned} & \min _f\left\{\max _{i \in A}\left\{f(i)+t_i-d_i\right\}\right\} \\ & \forall i, j \in A, i \neq j, f(i)+t_i \leq f(j) \\ & \text { or } f(j)+t_j \leq f(i) \end{aligned} ​fmin​{i∈Amax​{f(i)+ti​−di​}}∀i,j∈A,i=j,f(i)+ti​≤f(j) or f(j)+tj​≤f(i)​

• 实例：

1. 按照任务的顺序进行安排，例如：
   

• 在任务顺序 A = { 1 , 2 , 3 , 4 , 5 } A = \{1, 2, 3, 4, 5\} A={1,2,3,4,5}下，每个任务的执行时间$T=⟨5,8,4,10,3⟩$，截止时间$D=⟨10,12,15,11,20⟩$。我们根据以下步骤计算每个任务的完成时间和延迟。

完成时间$f_1(i)$：

任务$i$的完成时间是前面所有任务的累计执行时间：

• $f_1(1)=5$
• $f_1(2)=5+8=13$
• $f_1(3)=13+4=17$
• $f_1(4)=17+10=27$
• $f_1(5)=27+3=30$

延迟 L ( i ) = max ⁡ { f 1 ( i ) − D i , 0 } L(i) = \max\{f_1(i) - D_i, 0\} L(i)=max{f1​(i)−Di​,0}：

延迟是完成时间与截止时间的差，如果差为负则延迟为 0。

• 任务 1: L ( 1 ) = max ⁡ { 5 − 10 , 0 } = max ⁡ { − 5 , 0 } = 0 L(1) = \max\{5 - 10, 0\} = \max\{-5, 0\} = 0 L(1)=max{5−10,0}=max{−5,0}=0
• 任务 2: L ( 2 ) = max ⁡ { 13 − 12 , 0 } = max ⁡ { 1 , 0 } = 1 L(2) = \max\{13 - 12, 0\} = \max\{1, 0\} = 1 L(2)=max{13−12,0}=max{1,0}=1
• 任务 3: L ( 3 ) = max ⁡ { 17 − 15 , 0 } = max ⁡ { 2 , 0 } = 2 L(3) = \max\{17 - 15, 0\} = \max\{2, 0\} = 2 L(3)=max{17−15,0}=max{2,0}=2
• 任务 4: L ( 4 ) = max ⁡ { 27 − 11 , 0 } = max ⁡ { 16 , 0 } = 16 L(4) = \max\{27 - 11, 0\} = \max\{16, 0\} = 16 L(4)=max{27−11,0}=max{16,0}=16
• 任务 5: L ( 5 ) = max ⁡ { 30 − 20 , 0 } = max ⁡ { 10 , 0 } = 10 L(5) = \max\{30 - 20, 0\} = \max\{10, 0\} = 10 L(5)=max{30−20,0}=max{10,0}=10

最大延迟：

所有任务的延迟为 { 0 , 1 , 2 , 16 , 10 } \{0, 1, 2, 16, 10\} {0,1,2,16,10}，其中最大延迟为 16（任务 4）。

更优的调度方法：按截止时间从前到后安排

按照截止时间从前到后排序的任务调度

数据：

• 任务集合： A = { 1 , 2 , 3 , 4 , 5 } A = \{1, 2, 3, 4, 5\} A={1,2,3,4,5}
• 执行时间：$T=⟨5,8,4,10,3⟩$
• 截止时间：$D=⟨10,12,15,11,20⟩$
• 排序后任务顺序：$1,4,2,3,5$

完成时间$f_2(i)$：

• $f_2(1)=5$,$f_2(2)=15$,$f_2(3)=23$,$f_2(4)=27$,$f_2(5)=30$

延迟 L ( i ) = max ⁡ { f 2 ( i ) − D i , 0 } L(i) = \max\{f_2(i) - D_i, 0\} L(i)=max{f2​(i)−Di​,0}：

• L ( 1 ) = max ⁡ { 5 − 10 , 0 } = 0 L(1) = \max\{5 - 10, 0\} = 0 L(1)=max{5−10,0}=0
• L ( 4 ) = max ⁡ { 15 − 11 , 0 } = 4 L(4) = \max\{15 - 11, 0\} = 4 L(4)=max{15−11,0}=4
• L ( 2 ) = max ⁡ { 23 − 12 , 0 } = 11 L(2) = \max\{23 - 12, 0\} = 11 L(2)=max{23−12,0}=11
• L ( 3 ) = max ⁡ { 27 − 15 , 0 } = 12 L(3) = \max\{27 - 15, 0\} = 12 L(3)=max{27−15,0}=12
• L ( 5 ) = max ⁡ { 30 − 20 , 0 } = 10 L(5) = \max\{30 - 20, 0\} = 10 L(5)=max{30−20,0}=10

结果：

• 各任务延迟： { 0 , 11 , 12 , 4 , 10 } \{0, 11, 12, 4, 10\} {0,11,12,4,10}
• 最大延迟： 12（任务 3）

4. RNA二级结构预测（6.6）

• RNA的一级结构是由核苷酸（A、C、G、U）组成的线性序列
  *$A-C-C-G-C-C-U-A-A-G-C-C-G-U-C-C-U-A-A-G-$
• 而二级结构描述了这些核苷酸之间的碱基配对形成的二维拓扑结构。这些配对大多数遵循沃森-克里克配对规则（A-U 和 C-G），也可能存在少量其他配对形式（如G-U）。
• RNA二级结构通常由发夹环、内环、茎和多分支环等结构组成，这些特征在RNA分子功能中起关键作用。
  

匹配原则

匹配结构

• 给定RNA的一条链（一级结构）, 预测它的可能的稳定的二级结构。
• 稳定二级结构满足的条件
• 生物学条件: 具有最小自由能
• 简化条件：具有最多的匹配对数
• 问题: 给定RNA链, 求具有最多匹配对数的二级结构, 即最优结构.

NP-hard问题

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

P=NP?

P=NP 问题的解释

背景：

1. P 类问题：P（Polynomial time）是多项式时间可解问题的集合，代表了那些可以在多项式时间内被求解的决策问题。也就是说，对于给定输入，可以在合理的时间内（即，时间复杂度是输入规模的某个多项式）找到解决方案的所有问题。

   • 例子：排序问题（如快速排序）、图的最短路径问题（如 Dijkstra 算法）等。

2. NP 类问题：NP（Nondeterministic Polynomial time）是非确定性多项式时间问题的集合，代表了那些解法可以在多项式时间内验证的问题。也就是说，如果我们给出一个候选解，可以在多项式时间内验证这个解是否正确。

   • 例子：旅行商问题、整数分解、数独等问题。对于这些问题，可能我们不知道如何快速找到解，但一旦给出解，验证这个解是否正确是比较快的。

P vs NP 问题：

• P 表示所有可以在多项式时间内求解的问题。
• NP 表示所有可以在多项式时间内验证的问题。

P=NP 的含义是：是否所有能够在多项式时间内验证正确解的问题，也能在多项式时间内找到解？

换句话说：

• P = NP：如果某个问题的解能够快速验证（属于 NP 类问题），那么它也能被快速求解（属于 P 类问题）。
• P ≠ NP：有些问题虽然解的验证很快（属于 NP 类问题），但找到解的过程非常慢，甚至可能没有有效的多项式时间算法。

为什么这个问题重要？

• 如果 P = NP，那么很多目前被认为非常困难的问题（如密码学中的整数分解、旅行商问题等）将变得可以高效解决。这将对计算机科学、密码学、经济学等各个领域产生巨大影响。
• 如果 P ≠ NP，则说明有很多问题虽然解可以快速验证，但无法高效求解，这解释了为什么我们无法找到某些问题的快速解法。

目前的状况：

• 目前，大多数计算机科学家认为 P ≠ NP，但这一点尚未被证明。因此，P vs NP 问题仍然是一个悬而未决的难题，也是克雷数学研究所的七大千禧年问题之一，如果有人证明了 P = NP 或 P ≠ NP，便可以获得一百万美元的奖励。

举例：

假设你有一个很复杂的密码锁（例如由一组数字组成），这个锁只有一个正确的密码。你不知道如何高效地找到密码（这属于 NP 类问题），但是如果有人告诉你正确的密码，你可以立即检查这个密码是否能打开锁（这是验证问题）。问题是：你能不能既快速验证，又快速找到正确的密码？