绪论

算法和程序

• 算法是解决问题的一种方法或一个过程
• 算法是若干指令的有穷序列:
  • 性质： 输入、输出、确定性、有限性
• 算法是顺序执行
• 算法是对计算机上执行的计算过程的具体描述
• 程序时算法用某种程序设计语言的具体实现（可不满足有限性）
• 算法复杂性 = 算法所需要的计算机资源
• 时间T 空间S 规模n

分治法

算法介绍：
分治法所能解决的问题一般具有以下几个特征：

• 该问题的规模 缩小 到一定的程度就可以 容易地解决；
• 该问题可以 分解 为若干个规模较小的相同问题，即该问题具有最优子结构性质
• 利用该问题分解出的子问题的解可以 合并 为该问题的解；
• 该问题所分解出的各个子问题是 相互独立的，即子问题之间不包含公共的子问题。

$$
T(n)=
\begin{cases}
O(1) & n=1 \
kT(n/m)+f(n) & n>1
\end{cases}
\分治法时间复杂度
\T(n)=[n^{log_m k}]+\sum_{j=0}^{n}k^jf(n/m^j)
\迭代法求得方程解
$$

k： 子问题个数

n：问题规模

n/m: 子问题规模

f(n): 分解问题，合并问题所需的单位时间

算法	k	m	时间复杂度
大整数乘法	3	2	n^1.59
Strassen矩阵乘法	7	2	n^2.81
棋盘覆盖	4	2	n^2
循环赛日程安排	k	2	n^{log_2k}

• 算法的分析与实现：

1. 大整数乘法

• 使用分治法：
  $$
  有对于分为两段的二进制数(n位)\
  令：
  X=A\ 2^{n/2}+B，Y=C\ 2{n/2}+D\
  故：
  XY=AC2^n+(AD+BC)2^{n/2}+BD\
  $$
  发现：必有 4次n/2位整数乘法 ，3次2n位整数加法，2次移位算法，公用O(n)步运算。

  最大子问题规模n/2 -> m=2, 子问题个数4次 ->k=4

  复杂度与普通方法无差异（n^2）
  $$
  运用AD+BC=((A-B)(C-D)+AC+BD)\
  改进为：
  XY=AC2^n+((A-B)(C-D)+AC+BD)2^{n/2}+BD\
  $$
  该方法：

  仅仅需要3次n/2位整数乘法

  -> m = 2 , k = 3

2. Strassen 矩阵乘法

• 使用分治法：
  $$
  将矩阵分解为4个大小相等的子矩阵，每个子矩阵都是n/2的方阵\
  \left[
  \begin{array}{c|c}
  C_{11}&C_{12} \ \hline
  C_{21}&C_{22}
  \end{array}

  \right]

  \left[
  \begin{array}{}
  A_{11}&A_{12} \
  A_{21}&A_{22}
  \end{array}
  \right]
  \left[
  \begin{array}{}
  B_{11}&B_{12} \
  B_{21}&B_{22}
  \end{array}
  \right]\
  可得：\
  C_{11}=A_{11}B_{11}+A_{12}B_{21}\
  C_{12}=A_{11}B_{12}+A_{12}B_{22}\
  C_{21}=A_{21}B_{11}+A_{22}B_{21}\
  C_{22}=A_{21}B_{12}+A_{22}B_{22}\
  但算法复杂度依旧为8个规模为n/2的乘法->复杂度(n^4)\
  改进方法：\
  M_1=A_{11}(B_{12}-B_{22})\
  M_2=(A_{11}+A_{12})B_{22}\
  M_3=(A_{21}A_{22})B_{11}\
  M_4=A_{22}(B_{21}-B_{11})\
  M_5=(A_{11}+A_{22})(B_{12}+B_{22})\
  M_6=(A_{12}-A_{22})(B_{21}+B_{22})\
  M_7=(A_{11}-A_{21})(B_{11}+B_{12})\
  再经过若干次加减法得出结果
  该方法7个规模为n/2的乘法->复杂度(n^{log_27}=n^{2.81})
  $$

3. 棋盘覆盖

• 覆盖2k×2k 个方格组成的棋盘中除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
• 当k>0时，将2k×2k棋盘分割为 4 个2k-1×2k-1 子棋盘。
• 特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。
• 为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。
• 递归地使用这种分割，直至棋盘简化为棋盘1×1。

void chessBoard(int tr, int tc, int dr, int dc, int size)
{
    // tr 棋盘左上角， dr 特殊方格
    if (size == 1) return;
    int t = tile++,  // L型骨牌号
    s = size/2;  // 子棋盘大小
    // 覆盖左上角子棋盘
    if (dr < tr + s && dc < tc + s) // 特殊方格在此棋盘中
        chessBoard(tr, tc, dr, dc, s);
    else { // 此棋盘中无特殊方格
        board[tr + s - 1][tc + s - 1] = t; // 用 t 号骨牌覆盖右下角
        chessBoard(tr, tc, tr+s-1, tc+s-1, s);
    } // 覆盖其余方格
    // 覆盖右上角子棋盘
    // 覆盖左下角子棋盘
    // 覆盖右下角子棋盘
}

• 问题规模n/2, 4 次 -> O(n^2)

4.循环赛日程

• n = 2^k 个运动员进行网球循环赛，设计一个日程表：

  • 每个选手间相互比一次
  • 每个选手一天只能比赛依次
  • n-1天

• 按分治策略，将所有的选手分为两半

• n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。

• 递归地用对选手进行分割，直到只剩下2个选手时，让这2个选手进行比赛。

Void Table(int a[][],int begin,int end)
{    
    int n=end-begin;//待安排比赛的队数
    if(n<=2)  //安排两队比赛;
    else {    
        Table(a，begin，begin＋n/2); 
        Table(a,begin+n/2＋1，end);
        Merge(a);        
    }
}

• 复杂度k = k, m = 2

动态规划

算法思想：

• 基本思想将待求解问题分解成若干个子问题。
• 若子问题重复，保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。

基本要素：

• 最优子结构
• 重叠子问题

动态规划基本步骤：

• 分析最优值的性质，得到 最优值的递归定义
• 自底向上地计算 子问题的最优值，逐步得到原问题的最优值，并记录计算过程
• 由最优值的计算过程出 构造 原问题的最优解

算法	时间复杂度	空间复杂度
矩阵连乘
最长公共子序列
流水作业调度	nlogn	n
0-1背包问题
电路布线问题

• 算法问题与分析

1. 矩阵连乘

$$
将A_iA_{i+1}…..A_j记作A_{i,j}\
设最优解的最后一步为：A_{1,k}A_{k+1,n}\
最优结构：A_{1,k}、A_{k+1,n}应当分别为该子式的最优解\
——————————\
建立递归关系：设计算A[i:j] ， 1<=i<=j，所需最小乘数m[i,j]\
问题最优值：m[1,n]\
m[i,j]=
\begin{cases}
0 & i=j\
\underset{i<=k<j}\min{m[i,k]+m[k+1,j]+p_{i-1}p_kp_j} & i<j
\end{cases}\
A_i的维数为p_{i-1}p_i\
k为最佳顺序中两个子序列的中间断开点
$$

2. 最长公共子序列

$$
c[i][j]=
\begin{cases}
0 & i=0,j=0\
c[i-1][j-1]+1 & i,j>0;x_i=y_j\
max{c[i][j-1],c[i-1][j] } & i,j>0;x_i ≠ y_j
\end{cases}\
c[i][j]记录两序列的最长公共子序列长度
$$

3. 流水作业调度

n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。

流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少
$$
Johnson法则：min{b_{Π(i)},a_{Π(j)}}>=min{b_{Π(j)},a_{Π(i)}}
$$
所有 满足Johnson法则的调度 均为 最优调度

算法：
(1)令N_1={i | a_i < b_i}, N_2={i|a_i>=b_i}

(2)令N_1中作业依据a_i非减序排序，N_2中作业按b_i非增序列排序

(3)N_1 、 N_2构成满足Johnson法则最优调度

算法复杂度：

T:O(nlogn)

S:O(n)

4. 0-1背包

• 问题描述
  • 给定n种物品和一背包。
  • 物品i的重量是wi，
  • 其价值为vi，
  • 背包的容量为C。
  • 问应如何选择装入背包的物品，使得装入背包中物品的 总价值最大?

$$
m[i,j]=
\begin{cases}
max{m(i+1,j),m(i+1,j-w_i)+v_i} & j>w_i\
m(i+1,j) & 0<=j<w_i
\end{cases}\
j:背包容量\
i:物品\
m(i,j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。
$$

5.电路布线问题

• 问题描述

• 在一块电路板的上、下两端分别有n个接线柱。根据电路设计，要求用导线(i,π(i)) 将上端接线柱i与下端接线柱π(i)相连。

• 电路布线问题要确定将哪些连线安排在一层上，使得该层上有尽可能多的连线。即求Nets = ｛i，π(i)，1 ≤ i ≤ n｝的最大不相交子集。

$$
当i = 1,\
Size(1,j)=
\begin{cases}
0 & j < Π(1)\
1 & j >= Π(1)
\end{cases}\
当i > 1,\
Size(i,j)=
\begin{cases}
Size(i-1,j) & j < Π(i)\
max{Size(i-1,j),Size(i-1,Π(i)-1)} & j >= Π(i)
\end{cases}\
Size(n,n):最优值
$$

贪心算法

算法核心：局部最优解

• 最优子结构
• 贪心选择

算法	算法时间复杂度
最优装载
（0-1）背包装载
活动安排
多机调度

• 问题分析

1. 最优装载

• 问题分析

• 有一批集装箱要装上一艘载重量为c的轮船。

• 其中集装箱i的重量为Wi。

• 最优装载问题要求确定在装载体积不受限制的情况下，

• 将尽可能多的集装箱装上轮船。

  • 问题实质,0-1背包，价值vi皆为1,但此题用贪心法求解

• 算法：

  • 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。依此策略直到背包装满为止。

2. 活动安排

• 安排最大相容量

• 算法：

  • 将所有活动按结束时间排序，得到活动集合E={e1,e2…e_n}；
  • 先将e1选入结果集合A中，即A={e1}；
  • 依次扫描每一个活动e_i：
    • 如果e_i的 开始 时间 晚于 最后一个选入A的活动e_j的 结束 时间，则将e_i 选入 A中，否则放弃e_i；

3. 多机调度

• 要求给出一种作业调度方案，
• 使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。
• 算法：
  • 采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。
  • 当n<=m时，只要将机器i的[0, ti]时间区间分配给作业i即可，算法只需要O(1)时间。
  • 当n>m时，首先将n个作业依其 所需的处理时间 从大 到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为O(nlogn)。

回溯法

我简称为DFS

算法核心：

• 针对问题，定义解空间
• 确定易于搜索的解空间结构
• 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索

剪枝函数：

• 用约束函数在扩展节点处剪去不满足约束的子树。

• 用限界函数剪去得不到最优解的子树

算法	时间复杂度
最优装载问题*
批处理作业调度
n后
图m着色
旅行售货员

• 算法问题分析

1. 装载问题

• 有一批共n个集装箱
• 要装上2艘载重量分别为c1和c2的轮船，
• 其中集装箱i的重量为wi，且

$$
\sum_{i=1}^{n}w_i<=c_1+c_2
$$

• 首先将第一艘轮船尽可能装满；

• 将剩余的集装箱装上第二艘轮船。

• 算法：(2^n)

  • 约束函数（选择装入当前元素）：

  $$
  \sum_{i=1}^{n}w_ix_i<=c_1
  $$

  * 限界函数（不选择装入当前元素）：cw +r <= bestw
  * Betstw为当前已经计算出的最优装载重量。
  * Cw是装载到目前为止的总量。
  * r为剩余集装箱的重量。

• 执行过程
  1、从树根开始，计算当前载重量；
  2、判断其左子树（装入）是否满足约束条件，满足则继续深度优先搜索左子树，重复2；
  3、判断其右子树是否满足限界条件（是否可能含有最优解），满足则深度优先搜索右子树，重复2；
  4、到达叶子，则找到一个解；搜索完解空间树，得到最优解。

2. 批处理作业调度

• 算法描述：
  • 给定n个作业的集合{1,2,…n}。
  • 每个作业必须先由机器1处理，然后由机器2处理。
  • 作业i需要机器j的处理时间为tji。
  • 对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。
  • 所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。
• 解释：
  • 流水作业调度的最终目标是要求完成所有任务的时间最短，所以把最后一个任务的完成时间作为标准；
  • 而批处理作业调度的目的是要让每一个作业都尽快得到处理，所以要把每个作业的完成时间之和作为标准。
• 算法:O（n!）
  • 初始化（起始状态）；
    从第一个作业开始

    找待安排的作业
    如果当前结果比最小时间和小
        继续试探下一个作业安排
        如果已经是全部任务安排完成
              得到一个解
              撤掉该子，继续寻找下一个可能解
        否则（未到最后）
              准备处理下一个作业
    否则
         回溯到上一个顶点，并重新安排任务

3. n皇后问题

• 算法：

  1、从空棋盘起，逐行放置棋子。

  2、在一个布局中放下一个棋子，即推演到另一个布局。

  3、如果某一行中没有可合法放置棋子的位置，则回溯到上一行，重新布放上一行的棋子。

4. 图的m着色

• 问题描述：
  • 给定无向连通图G和m种不同的颜色。
  • 用这些颜色为图G的各顶点着色，每个顶点着一种颜色。
  • 是否有一种着色法使G中每条边的2个顶点着不同颜色?
• 算法 O（nm^n）
  初始化（起始状态）；
  从第一个顶点开始

  由当前顶点安排下一个顶点可设置的颜色
  如果找到了可以设置的颜色
      置顶点颜色
      如果已经是最后一个顶点
            得到一个解
            回溯，继续寻找下一个解
      否则（未到最后）
            准备处理下一个顶点
  否则（没有找到可以设置的颜色）
       回溯到上一个顶点，并去除该顶点的颜色

5. 旅行售货员

• 问题描述

  • 有一个售货员要开车到N个指定的城市去推销货物，
  • 他必须经过全部N个城市并且每个城市仅经过一次。
  • 现在他有一张n个城市的地图并知道各个城市之间的公路里程wi，
  • 试问他应该如何选取最短的行程从家里出发对N个城市旅行一遍并再回到家中

• 算法：O（n!）

  初始化（起始状态）；
  从图的第一个顶点开始

  由当前顶点找下一个邻接的顶点
  如果比最小代价小
      放当前顶点城市到最短路径中
      如果已经是最后一个顶点
            得到一个解
            撤掉该子，继续寻找下一个解
      否则（未到最后）
            准备处理下一个邻接顶点
  否则
       回溯到上一个顶点，并去除该顶点的分支

分支限界法

我简称为BFS（或最小耗费优先）

求解目标：

• 回溯法是找出解空间树种满足约束条件的所有解
• 分支限界法是找出满足约束条件的一个解，或者最优解

基本思想：

• 在扩展节点处，先生成其所有的儿子节点（分支），然后再从当前节点的活结点表中选择下一个扩展节点
• 扩展节点选择：在每一个活结点出，计算一个函数优先值（优先级），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的节点作为扩展节点

分类：

• 队列式（BFS）
• 优先队列式（通过函数计算值，丢到priority_queue中）

算法	时间复杂度
0-1背包
装载问题
旅行售货员

• 算法描述

1. 0-1背包

• 算法：
  • 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。
  • 在使用优先队列分支限界法中，节点的优先级由
    • 已装袋的物品价值加上
    • 剩下的 最大单位重量价值 的物品 装满剩余容量的价值和

初始化，将物品按照单位价值的从大到小顺序排列；
从第一个物品开始
左儿子加入后可否满足控制约束
将顶点i加入到最大优先队列中
修改最大价值,修改上界条件
否则检查右儿子可否满足条件
将右儿子加入优先队列
修改上界条件
取下一扩展结点
当队列为空时
输出当前记录的路径

2. 装载问题

• 算法:

队列式分支限界法
算法描述：
未搜索到树的结束
检查左儿子结点是否满足约束条件
左儿子加入扩展队列
根据当前修改当前最优解（可装载的最大重量）
右儿子结点总是可行的，加入队列
取下一扩展结点
判断是否同层结点尾部（－1）
如果队空返回最优解（可装载的最大重量）
加入同层结点尾部标志
取下一扩展结点
进入下一层

3. 旅行售货员