计算机算法设计与分析

大家好，欢迎来到IT知识分享网。

一、算法概述

（一）、算法与程序

1、算法定义:

• 算法是指解决问题的一种方法或一个过程。
• 算法是若干指令的有穷序列，其中每一条指令表示一个或多个操作。
• 算法是求解一个问题类的无二义性的有穷过程。

算法设计的任务是对各类具体问题设计良好的算法及研究设计算法的规律和方法。常用的算法有:穷举搜索法、递归法、回溯法、贪心法、分治法等。

---

2、算法性质

• 输入:有0个或多个外部提供的量作为算法的输入。
• 输出:算法产生至少一个量作为输出。
• 确定性:组成算法的每条指令是清晰，无歧义的。
• 有限性:算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。
• 可行性:一个算法是能行的。

---

3、算法的描述方式

自然语言、数学语言、伪代码、程序设计语言、流程图、表格、图示…

---

4、伪代码的例子

• 类C、C++、Java
• 允许使用自然语言
• 忽略数据结构、变量说明
• 忽略模块、异常等细节

---

5、程序与算法

（1）程序 :

算法用某种程序设计语言的具体实现

（2）程序设计包括：

（3）程序(Program)与算法区别和联系

• 程序是算法用某种程序设计语言的具体实现。
• 程序中的指令必须是机器可执行的，而算法中的指令则无此限制。
• 程序可以不满足算法的有限性。
  • 例如：操作系统，是一个在无限循环中执行的程序，因而不是一个算法。
  • 操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。

---

6、问题求解(Problem Solving)

（二）、算法复杂性分析

• 正确性(correctness)
• 可读性（readability)
• 健壮性（robustness)
• 效率和低存储量（( time and space efficiency)
  • 与问题规模紧密相关
  • 效率和低存储量需求是对一个算法的复杂性进行衡量的标准

---

1、算法复杂性

（1）算法复杂性=算法所需要的计算机资源

• 复杂性函数: C=F(N,I,A)
• C——复杂性
• N——问题的规模
• l一—算法的输入
• A——算法本身
• (通常，让A隐含在复杂性函数名当中)

（2）算法复杂性=算法所需要的计算机资源

时间复杂度主要指CPU使用的时间，空间复杂度主要指内存使用的量

• 算法的时间复杂性（ time complexity)
  • 需要时间资源的量称为时间复杂性
  • 记为:T=T(N, I)
• 算法的空间复杂性(space complexity)
  • 需要的空间资源的量称为空间复杂性
  • 记为:S=S(N, I)

（3）三种情况的时间复杂性分析

• 最坏情况下的时间复杂性:.

  $T_{max}(N)=\underset{I\in D_N}{\max }T(N,I)=\underset{I\in D_N}{\max }{\sum }_{i=1}^k{t}_i{e}_i(N,I)={\sum }_{i=1}^k{t}_i{e}_i(N,I^{\ast })=T(N,I^{\ast })$

• 最好情况下的时间复杂性:
  $T_{max}(N)=\underset{I\in D_N}{\min }T(N,I)=\underset{I\in D_N}{\min }{\sum }_{i=1}^k{t}_i{e}_i(N,I)={\sum }_{i=1}^k{t}_i{e}_i(N,\tilde{I})=T(N,\tilde{I})$
  
• 平均情况下的时间复杂性:
  $T_{avg}(N)={\sum }_{I\in D_N}P(I)T(N,I)={\sum }_{I\in D_N}P(I){\sum }_{i=1}^k{t}_i{e}_i(N,I)$
  其中$D_N$是规模为$N$的合法输入的集合；$I^{\ast }$是$D_N$中使$T(N,I^{\ast })$达到$T_{max}(N)$的合法输入;$\tilde{I}$是中使$T(N,\tilde{I})$达到$T_{min}(N)$的合法输入；而$P(I)$是在算法的应用由出现输入$I$的概率。
  
  
• 三种情况下的复杂性中，可操作性最好，最有实际价值的是最坏情况下的时间复杂性。
• 如果只考虑某种特定情况，如最好或最坏情况的时间复杂性，输入的“$I$”就是一个常量，可省略。因而有: $T=T(N,I)\to T=T(N)$
• 利用某一算法处理一个问题规模为n的输入所需的时间，称为该算法的时间复杂性。记为$T(n)$

  (1) 最坏情况下的时间复杂性
    T m a x ( n ) = max ⁡ { T ( I ) ∣ s i z e ( I ) = n } T_{max}(n)=\max \{ T(I) | size(I)=n \} Tmax​(n)=max{
  T(I)∣size(I)=n}
  (2) 最好情况下的时间复杂性
    T m i n ( n ) = min ⁡ { T ( I ) ∣ s i z e ( I ) = n } T_{min}(n) = \min\{ T(I) | size(I)=n\} Tmin​(n)=min{
  T(I)∣size(I)=n}
  (3) 平均情况下的时间复杂性
   $T_{avg}(n):{\sum }_{size(I)=n}p(I)T(I)$
  其中I是问题的规模为n的实例，p(I)是实例I出现的概率
  
  
  
  
  
  
  
  

例：顺序查找

i=1; while(i<=n&&L[i]!=x)i++; if(i>n)i=0; printf(i); 

$T(L[i]=ii\in [i\dots n]T(L[i]=ni>n$
$T_{avg}(n):{\sum }_{size(I)=n}p(I)T(I)=(n+1)/2$
T m a x ( n ) = max ⁡ { T ( I ) ∣ s i z e ( I ) = n } = n T_{max}(n)=\max\{ T(I) | size(I)=n \}=n Tmax​(n)=max{
T(I)∣size(I)=n}=n
$T_{min}(n)=1$

---

2、算法分析的基本准则

(1) for / while循环

• 循环体内计算时间*循环次数;

(2）嵌套循环

• 循环体内计算时间*所有循环次数;

(3）顺序语句

• 各语句计算时间相加;

(4) if-else语句

• if语句计算时间和else语句计算时间的较大者。

---

3、渐进时间复杂性

（1）定义

• $T(n)\to \infty ,asn\to \infty ;$
• $(T(n)-t(n))/T(n)\to 0,asn\to \infty ;$
• $t(n)$是$T(n)$的渐近性态，为算法的渐近复杂性。
• 在数学上，$t(n)$是$T(n)$当$n\to \infty$时的渐近表达式。

当n趋近无穷时，T(n)渐近于t(n)

（2）符号：

• $O$符号——渐进上界记号(读作大O)

• 若极限为非0正常数，则函数f(n)和g(n)增长速度至多相差常数倍，或称为同一级别;
• 若极限为0，说明随着n的增大，函数f(n)的增长要比g(n)的增长慢得多。
• 试图求出最小的g(n)，使得$f(n)=O(g(n))$。
• $\Omega$符号——渐进下界记号
• $\Theta$符号——渐进确界记号

---

4、渐进阶的高低

• 当数据集的规模很大时，要在现有的计算机系统上运行具有比O (nlogn)复杂度还高的算法是比较困难的。
• 指数时间算法只有在n取值非常小时才实用。
• 要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度，而不是（仅仅依靠）提高计算机的速度。

---

5、渐进记号的运算规则

---

6、复杂性分析小结

• 三种复杂性函数，最常用的是最坏情况下的复杂性函数
• 渐进复杂性，略去低阶项，简化分析
• 3种渐进分析符号，最常用的是O符号（表示最坏情况下的渐进复杂性）
• 渐进阶越高，复杂性越高
• 掌握渐进符号的运算规则

时间复杂度递推公式：

分治法将规模为n的问题分成k个规模为n／m的子问题：
$T(n)=\{\begin{array}{r}O(1)n=1\\ kT(n/m)+f(n)n>1\end{array}$ ==》$T(n)=n^{lo{g}_{m}k}+{\sum }_{j=0}^{lo{g}_{m}n-1}{k}^{j}f(\frac{n}{m^j})$

各排序算法时间复杂度比较

---

---

---

二、递归与分治策略

引言

1、分治的思想

• 将一个难以直接解决的大问题分割成一些规模较小的相同问题，各个击破，分而治之。 在分解的过程中，如果子问题的规模仍然不够小，则再划分为多个子问题，如此递归地进行下去，直到问题规模足够小，很容易求出其解为止。

2、递归与分治

• 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
• 在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然由此引出递归算法。

---

---

（一）、递归（ recursion ）

1、递归的概念

（1）递归算法（ recursive algorithm ）

直接或间接地调用自身的算法

（2）递归函数（ recursive function ）

用函数自身给出定义的函数

---

2、递归应用

（1）递归的三种类型

• 问题的定义是递归的
  • 如求阶乘、Ackerman函数
• 问题的求解过程是递归的
  • 如汉诺塔问题、八皇后问题
• 问题采用的数据结构是递归的
  • 如二叉树的遍历

（2）例子——阶乘函数

• 边界条件——确定递归到何时终止
• 递归方程——大问题如何分解为小问题

//求解阶乘函数的递归算法 long Fac ( long n ) { 
                     if ( n <= 1) return 1; else return n * Fac (n-1); } 

（3）例子——Fibonacci数列

//第n个Fibonacci数可递归地计算如下： int fibonacci(int n) { 
                     if (n <= 1) return 1; return fibonacci(n-1)+fibonacci(n-2); } 

（4）例子——Ackerman函数

• 前2例中的函数都可以找到相应的非递归方式定义：

  $n!=1\cdot 2\cdot 3\cdot \cdot \cdot \cdot \cdot \cdot （n-1）\cdot n$
  $F(n)=\frac{1}{\sqrt{5}}\left({\left(\frac{1+\sqrt{5}}{2}\right)}^{n+1}-{\left(\frac{1-\sqrt{5}}{2}\right)}^{n+1}\right)$
  但Ackerman函数却无法找到非递归的定义。
  
  

• 当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。
• Ackerman函数A(n，m)定义如下：

  $\{\begin{array}{r}A(1,0)=2\\ A(0,m)=1m\ge 0\\ A(n,0)=n+2n\ge 2\\ A(n,m)=A(A(n-a,m),m-1)n,m\ge 1\end{array}$

  • Ackerman函数无法写出非递归定义式
  • A(n,m)的自变量m的每一个值都定义了一个单变量函数；
  • M=0时，A(n,0)=n+2
    M=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*n
    M=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2^n 。
    M=3时，类似的可以推出 $\begin{array}{c}\underbrace{2^{2^{2^{\cdots }}}}\\ n\end{array}$
    M=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。
    
    
    
    

（4）排列问题

设计一个递归算法生成n个元素$r_1,r_2,\dots ,r_n$的全排列。例如R={a,b,c}的全排列：abc,acb,bac,bca,cab,cba 共6个。
设:
   R = { r 1 , r 2 , … , r n } R=\{r_1,r_2,…,r_n\} R={
r1​,r2​,…,rn​}是要进行排列的n个元素， R i = R − { r i } R_i=R-\{r_i\} Ri​=R−{
ri​}。
  集合R中元素的全排列记为$perm(R)$。
  $(r_i)perm(R_i)$表示在全排列$perm(R_i)$的每一个排列前加上前缀得到的排列。

R的全排列可归纳定义如下：

• 当n=1时，$perm(R)=(r)$，其中r是集合R中唯一的元素；
• 当n>1时，$perm(R)$由$(r_1)perm(R_1),(r_2)perm(R_2),\dots ,(r_n)perm(R_n)$构成。

//perm 的递归算法如下: void perm(int list[],int k,int m){ 
                     int i; if(k==m){ 
                     for(i=0;i<=m;i++) printf("%c ", list[i]); }else{ 
                     for(i=k;i<=m;i++){ 
                     swap(& list[k],& list[i]); perm(list,k+1,m); swap(& list[k],& list[i]); } } } 

（5）正整数划分问题

• 将正整数n表示成一系列正整数之和：

    $n=n_1+n_2+\dots +n_k,其中n_1\ge n_2\ge \dots \ge n_k\ge 1,k\ge 1。$

• 正整数n的这种表示称为正整数n的划分。
• 求正整数n的不同划分个数。

解：
 例如正整数6有如下11种不同的划分：
6；
5+1； 最大数5
4+2，4+1+1； 最大数4
3+3，3+2+1，3+1+1+1；最大数3
2+2+2，2+2+1+1，2+1+1+1+1； 最大数2
1+1+1+1+1+1。
 设最大数为m,将最大加数 $n_i$ 不大于m的划分个数记作q(n,m)。
(1) q(n,1)=1,n<=1;
 当最大加数$n_i$不大于1时，任何正整数n只有一种划分形式
(2) q(n,m)=q(n,n),m>n;
 最大加数n1实际上不能大于n。因此，q(1,m)=1。
(3) q(n,n)=1+q(n,n-1);
 正整数n的划分由m=n的划分和m≤n-1的划分组成。
(4) q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;
 正整数n的最大加数n1不大于m的划分由n1=m的划分和n1≤m-1 的划分组成。
因此，可以建立q(n,m)的如下递归关系:
$q(n,m)=\{\begin{array}{r}1n=1或m=1\\ q(n,n)n<m\\ 1+q(n,n-1)n=m\\ q(n,m-1)+q(n-m,m)n>m>1\end{array}$
正整数n的划分数p(n)=q(n,n)。

（6）Hanoi塔问题

void hanoi(int n, int a, int b, int c){ 
                     if (n > 0) { 
                     hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); } } 

---

3、递归小结

（1）优点

（2）缺点

运行效率较低（运行过程中调用自身），耗费的计算时间还是占用的存储空间都比非递归算法要多；

---

---

（二）、分治法（Divide and Conquer）

1、分治法总体思想

1. 将要求解的较大规模的问题分割成k个更小规模的与原问题相同的子问题。
2. 对这k个子问题分别求解。
3. 如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
4. 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。

---

2、分治法的适用条件

分治法所能解决的问题的特征：

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

第3条特征：能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。
第4条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。

---

3、分治法的求解步骤

分治模式在每一层递归上都有三个步骤：

（1）分解（Divide）

• 将原问题分解成一系列子问题；

（2）解决（Conquer）

• 递归的解各个子问题，若子问题足够小，则直接求解；

（3）合并（Combine）

• 将子问题的结果合并成原问题的解。

---

4、分治算法的基本设计模式

divide-and-conquer(P){ 
                           if ( | P | <= n0) adhoc(P); //解决小规模的问题 divide P into smaller subinstances P1,P2,...,Pk;//分解问题 // 分解问题 for (i=1,i<=k,i++) yi=divide-and-conquer(Pi); //递归的解各子问题 return merge(y1,...,yk); //将各子问题的解合并为原问题的解 } // 其中adhoc(P)为基本子算法，直接解小规模问题P 

---

5、问题规模的分割原则

• 在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。
• 这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。
• 思考：为什么？

---

6、分治法的复杂性分析

• 一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。
  • 设分解阀值n0=1 ，且adhoc解规模为1的问题耗费1个单位时间。
  • 再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。
  • 用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有： $T(n)=\{\begin{array}{r}O(1)n=1\\ kT(n/m)+f(n)n>1\end{array}$
    通过迭代法求得方程的解：$T(n)=n^{lo{g}_{m}k}+{\sum }_{j=0}^{lo{g}_{m}n-1}{k}^{j}f(\frac{n}{m^j})$
    

    注意：递归方程及其解只给出$n$等于$m$的方幂时$T(n)$的值，但是如果认为$T(n)$足够平滑，那么由n等于m的方幂时$T(n)$的值可以估计$T(n)$的增长速度。通常假定$T(n)$是单调上升的，从而当$m^i\le n<m^{i+1}$时，$T(m^i)\le T(n)<T(m^{i+1})$。

• 在分析复杂性时，通常会得到递归不等式:

  $T(n)<=\{\begin{array}{r}O(1)n=1\\ kT(n/m)+f(n)n>1\end{array}$
  注意： 在讨论最坏情况下的复杂性时，用等号或者小于等于号没有本质区别。
  

---

---

（三）、二分搜索技术

1、问题

给定已按升序排好序的$n$个元素$a[0:n-1]$，现要在这n个元素中找出一特定元素$x$。

---

2、分析

（1）该问题的规模缩小到一定的程度就可以容易地解决；
分析： 如果$n=1$即只有一个元素，则只要比较这个元素和$x$就可以确定$x$是否在表中。因此这个问题满足分治法的第一个适用条件
（2）该问题可以分解为若干个规模较小的相同问题;
分析： 比较x和a的中间元素$a[mid]$，若$x=a[mid]$，则$x$在$L$中的位置就是$mid$；如果$x<a[mid]$，由于$a$是递增排序的，因此假如$x$在$a$中的话，$x$必然排在$a[mid]$的前面，所以我们只要在$a[mid]$的前面查找$x$即可；如果$x>a[i]$，同理我们只要在$a[mid]$的后面查找$x$即可。无论是在前面还是后面查找$x$
，其方法都和在$a$中查找$x$一样，只不过是查找的规模缩小了。
（3）分解出的子问题的解可以合并为原问题的解；
（4）分解出的各个子问题是相互独立的。

 分析： 很显然此问题分解出的子问题相互独立，即在$a[i]$的前面或后面查找$x$是独立的子问题，因此满足分治法的第四个适用条件。

---

3、代码

int BinarySearch(Type a[], int x, int l, int r) { 
                                 while (l<=r){ 
                                 int m = (l+r)/2; if (x == a[m]) return m; if (x < a[m]) r = m-1; else l = m+1; } return -1; } 

---

4、作业

（1）二分搜索算法的复杂度分析

（2）给定a，用二分法设计出求$a^n$的算法（假设$n=2^k$）。

思路：
 拆分：

   $a^{2^{k-1}}$    $a^{2^{k-1}}$
  $a^{2^{k-2}}$ $a^{2^{k-2}}$ $a^{2^{k-2}}$ $a^{2^{k-2}}$
… … … … … … … …
$a^{2^{k-k}}$………………………$a^{2^{k-k}}$

---

---

（四）、大整数的乘法

1、什么是大整数?

$=2^{63}-1$ ？
$2n，n=$ ？

• 超出硬件表示范围；浮点表示不精确、受限
• 此时，乘、除法运算不能看作只消耗一个单位时间的基本运算
• 位操作才是基本运算，算法复杂度应考查位操作次数

---

2、两个二进制大整数的乘法运算

• 小学的方法：摆竖式

$O(n^2)$

• 考虑两个n位整数相乘的时间复杂度$O(n^2)$
• 两个n位二进制大整数的乘法运算 （假设n是2的幂）

分治法:
(1)
   X=A B
  Y=C D

$XY=AC{2}^n+(AD+BC)2^{n/2}+BD$
AC AD BC BD 是四个子问题
$T(n)=\{\begin{array}{r}O(1)n=1\\ 4T(n/2)+O(n)n>1\end{array}=O(n^2)$

• 与小学方法相比，效率没有改善！
• 为了降低时间复杂度，必须减少乘法次数

(2)变换成三个子问题

细节问题： 两个XY的复杂度都是O(nlog3)，但考虑到A+B,C+D可能得到m+1位的结果，使问题的规模变大，故选择第1种XY方案。
Expected node of symbol group type, but got node of type cr $=O(n^{log3})=O(n^{1.59})$

(3)

• 如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。
• 最终，这个思想导致了快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算法。对于大整数乘法，它能在O(nlogn)时间内解决。
• 是否能找到线性时间的算法,目前为止还没有结果。

---

---

（五）、Strassen矩阵乘法

1、传统算法

（1）定义及计算方法

两个n×n矩阵A和B的乘积矩阵C中元素C[i,j]定义为: $c[i][j]={\sum }_{k=1}^{n}A[i][k]B[k][j]$
若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩阵C的 个元素所需的计算时间为$O(n^3)$。

（2）算法代码

两个矩阵相乘的经典算法若设 Q=MN其中，M是n1n1矩阵，N是n2*n2矩阵。当n1=n2时有：

 for(i=1;i<=n1;++i){ 
                                       for(j=1;j<=n2;++j){ 
                                       q[i][j]=0; for(k=1;k<=n1;++k) q[i][j]+=m[i][k]*n[k][j]; } } 

---

2、分治法

（1）
将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：

由此可得：
（8个子问题）
$T(n)=\{\begin{array}{r}O(1)n=2\\ 8T(n/2)+O(n^2)n>2\end{array}=O(n^3)$
没有改进
（2）将其分成7个子问题
等同于：
Expected node of symbol group type, but got node of type cr

（3）

• Hopcroft和Kerr已经证明(1971)，计算2个２×２矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算2×2矩阵的7次乘法这样的方法了。或许应当研究３×３或５×５矩阵的更好算法。
• 在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 $O(n2.376)$
• 是否能找到O(n2)的算法？

---

---

（六）、快速排序

1、快速排序原理过程演示

---

---

（七）、归并排序

1、归并排序过程

2、代码

public class MergeSort { 
                                            public static void mergeSort(int[] arr) { 
                                            if (arr == null || arr.length < 2) { 
                                            return; } mergeSort(arr, 0, arr.length - 1); } public static void mergeSort(int[] arr, int l, int r) { 
                                            if (l == r) { 
                                            return; } int mid = l + ((r - l) >> 1); mergeSort(arr, l, mid); mergeSort(arr, mid + 1, r); merge(arr, l, mid, r); } public static void merge(int[] arr, int l, int m, int r) { 
                                            int[] help = new int[r - l + 1]; int i = 0; int l1 = l; int r1 = m + 1; while (l1 <= m && r1 <= r) { 
                                            help[i++] = arr[l1] < arr[r1] ? arr[l1++] : arr[r1++]; } while (l1 <= m) { 
                                            help[i++] = arr[l1++]; } while (r1 <= r) { 
                                            help[i++] = arr[r1++]; } for (int j = 0; j < help.length; j++) { 
                                            arr[l + j] = help[j]; } } } 

---

---

---

三、贪心（Greedy）算法

引言

贪心策略基本思想

从问题的初始状态出发，通过若干次的贪心选择得出问题的最优解或近似优解的一种解题策略。

• 贪心算法总是作出在当前看来最好的选择。 也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。
• 当然，希望贪心算法得到的最终结果也是整体最优的。
• 虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。 如单源最短路径问题，最小生成树问题等。
• 在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

（一）、贪心算法

1、贪心算法定义

指的是从对问题的某一初始解出发,一步一步的攀登给定的目标,尽可能快地去逼近更好的解。当达到某一步,不能再攀登时,算法便终止。

---

2、贪心算法特点

贪心算法总是做出在当前看来是最好的选择,它并不是从总体最优上加以考虑,他所作出的选择只是在某种意义上的局部最优选择。能够得到的解不一定是最优解。

---

3、贪心算法的基本要素

（1）贪心选择性质

是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。 贪心算法通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，做出贪心选择后，原问题简化为规模更小的类似子问题。必须证明每一步所作的贪心选择最终导致问题的整体最优解。 

（2）最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 

---

4、贪心解题步骤

1. 从问题的某个初始解出发
2. 采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模
3. 将所有部分解综合起来，得到问题最终解

---

---

（二）、贪心算法范例

1、活动安排问题

（1）问题：

（2）思考

i	1	2	3	4	5	6	7	8	9	10	11
S[i]	1	3	0	5	3	5	6	8	8	2	12
f[i]	4	5	6	7	8	9	10	11	12	13	14

（3）解决

//事先有排序算法 //各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列  void GreedySelector(int n, Type s[], Type f[], bool A[]) { 
                                                    A[1]=true; int j=1; for (int i=2;i<=n;i++) { 
                                                   //发现一个活动的起始时间比当前活动的结束时间晚——局部最优 if (s[i]>=f[j]) { 
                                                    A[i]=true; j=i; } else A[i]=false; } } 

（4）证明过程

第一步：总存在以贪心选择开始的最优活动安排方案
设E= {1,2，…, n}为所给的活动集合，且E中活动按照结束时间非减序排列，故 活动1具有最早完成时间。
首先，证明活动安排问题有一个最优解以贪心选择开始，即该最优解中包含活动1.
设A属于E是所给活动安排问题的一个最优解，且A中活动也按结束时间非减序排列，A中的第一个活动是k.
若k=1,则A就是一个以贪心选择开始的最优解； 若k>1,则设B=A-{k}U{1}。
由于f1<fk, 且A中活动都是相容的，故B中的活动也是相容的，且B和A中活动个数相等，所以B也是最优的。即B是以贪心选择活动1开始的最优活动安排。
第二步：证明活动安排问题具有最优子结构性质
在做了第一步贪心选择活动1后，原问题简化为对E中所有与活动1相容的活动进行活动安排的子问题。
即若A是原问题的最优解，则A’=A-{1}是活动安排问题E’={i属于E:si>=f1}的最优解。
反证法： 假设E’有一个解B’，包含比A’更多的活动 B=B’ U{1}，则B比A包含更多的活动 这与A的最优性矛盾
结论：每一步所做的贪心选择都将原问题简化为一个更小的与原问题具有相同形式的子问题。

（5）总结

---

2、最优装载

（1）问题

 有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。

（2）对最优装载问题进行形式化描述

• 用一个向量（x1,x2,x3,…,xn）,表示装的个数多少
• 约束条件：xi ∈{ 0,1 }

  

• 目标函数：

（3）算法描述

• 最优装载问题可用贪心算法求解。
• 采用重量最轻者先装的贪心选择策略
• 可产生最优装载问题的最优解。

void Loading(int x[], Type w[], Type c, int n) { 
                                                     int t[n+1]; Sort(w, t, n);//对w进行排序，将排序后的角标存入t，而w不变 for (int i = 1; i <= n; i++) x[i] = 0; for (int i = 1; i <= n && w[t[i]] <= c; i++) { 
                                                     x[t[i]] = 1; c -= w[t[i]]; } } 

（4）最优装载的贪心选择性质

• 设集装箱依其重量从小到大排序，(x1, x2, …, xn)是最优装载问题的一个最优解。
• 又设 (第一个选择的集装箱序号)
• 如果给定的最优装载问题有解，则 1<=k<=n
  1. 当k=1时， (x1, x2, …, xn)是满足贪心选择性质的最优解
  2. 当k>1时，取y1=1,yk=0,yi=xi, 则
     
     (用另外一个选择序列Y代替，其中仅将x1与xk调换)
     
     
  • 故，(y1, y2, …, yn)是所给最优装载问题的可行解。
  • 由知， (y1, y2, …, yn)是满 足贪心选择性质的最优解。

（5）最优装载的最优子结构性质

---

3、（分数）背包问题

（1）问题

0-1背包问题：
给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
（在选择装入背包的物品时，对每种物品i只有2种选择，即不装入（0）或装入背包（1）背包。 不能将物品i装入背包多次，也不能只装入部分的物品i。 ）
分数背包问题：
与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。
这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。

（2）选择贪心标准

• 影响背包效益值的因素：
  – 背包的容量M
  – 放入背包中物品的质量及其可能带来的效益值
  • 因此：

  
  
  

在背包容量占用速率和背包效益值的增长速率之间取得平衡。 即每次选择装入背包的物品，应满足它所占用背包的每一单位容量能获得当前最大的单位效益。

• 贪心标准的选择一：

• 贪心标准的选择二：

• 贪心标准的选择三：

 - 满足最优子结构性质 - 满足贪心选择性质 - 以单位质量价值做为量度标准进行选择时，相当于把每一个物品都分割成单位块，单位块的利益越大，显然,物品装入背包后，背包获取总效益越大。 

结论：

 - 以单位质量价值作为贪心标准求解(分数)背包问题能够得到一个最优解。 

（3）解决

void Knapsack(int n,float M,float v[], float w[],float x[]) { 
                                                      Sort(n,v,w); int i; for (i=1;i<=n;i++) x[i]=0; float c=M; for (i=1;i<=n;i++) { 
                                                      if (w[i]>c) break; x[i]=1; c-=w[i]; } if (i<=n) x[i]=c/w[i]; } 

算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O（nlogn）

（4）0-1背包无法使用贪心求最优解问题

---

4、哈夫曼编码

（1）什么是Huffman编码

• 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。
• 其压缩率通常在20%～90%之间。
• 哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。
• 给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。

等长编码:

可变长编码 :

前缀编码:
 对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，这种编码称为前缀(编)码
最优前缀编码:
 平均码长或文件总长最小的前缀编码称为最优的前缀编码

（2）算法构建

略

---

5、单源最短路径

（1）问题

（2）算法的基本思想

（3）问题描述

（4）代码

void Dijkstra(int n,int v, type dist[],int prev[],type**c) { 
                                                        bool s[maxint]; for(i=1;i<=n;i++) { 
                                                        s[i]=false; dist[i]=c[v][i]; if (dist[i]==maxint) prev[i]=0; else prev[i]=v; } s[v]=true; dist[v]=0; for(j=1;j<n;j++){ 
                                                        temp=maxint; u=v; for(j=1;j<=n;j++) { 
                                                        if(!s[j]&&dist[j]<temp) { 
                                                        u=j; temp=dist[j]; } for(j=1;j<=n;j++){ 
                                                        if(!s[j]&&c[u][j]<maxint) { 
                                                        newdist=dist[u]+c[u][j]; if(newdist< dist[j]) { 
                                                        dist[j]=newdist;prev[j]=u; } } } } } } 

（5）Dijkstra算法的正确性：

1. 贪心选择性质
2. 最优子结构性质

（6）计算复杂性：

 对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要O(n)时间。这个循环需要执行n-1次，所以完成循环需要O(n2)时间。算法的其余部分所需要时间不超过O(n2)。

---

6、最小生成树

（1）问题提出

• 要在n个城市间建立通信联络网
  • 顶点——表示城市
  • 权——城市间建立通信线路所需花费代价
• 希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小———最小代价生成树

（2）问题分析

（3）最小生成树性质

 设G=(V，E)是一个连通网络，U是顶点集V的一个非空子集。若(u，v)是G中所有的一个端点在U(u∈U)里、另一个端点不在U(即v∈V-U)里的边中，并且是具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边(u，v)。

（4）Prim算法

用普里姆算法 void PRIM( MGraph G,VertexType u) //从第u个顶点出发 { 
                                                         k=LocateVex(G,u); for (j=0; j<G.vexnum; j++) if(j!=k) closedge[j]={ 
                                                        u, G.arcs[k][j].adj}; closedge[k].lowcost=0; //初始U={u} for (i=1; i<G.vexnum; i++) // 循环n-1次，每次求出最小生成树的一条边 { 
                                                         k=minnum(closedge); printf(closedge[k].adjvex,G.vexs[k]); //输出生成树的边 closedge[k].lowcost=0; // 将 k 并入U 中 for (j=0; j<G.vexnum; j++) // 修改 lowcost[ ] 和closest[ ] if (G.arcs[k][j].adj< closedge[j].lowcost) //新顶点并入后重新选择最小边 lowedge[j]={ 
                                                        u, G.arcs[k][j].adj}; } } 

（5）Kruskal算法基本思想

1. 首先将G的n个顶点看成n个孤立的连通分支。
2. 将所有的边按权从小到大排序。
3. 然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：
   1. 当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；
   2. 如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。
4. 这个过程一直进行到只剩下一个连通分支时为止。

• 关于集合的一些基本运算可用于实现Kruskal算法。
• 按权的递增顺序查看等价于对优先队列执行removeMin运算。可以用堆实现这个优先队列。
• 对一个由连通分支组成的集合不断进行修改，需要用到抽象数据类型并查集UnionFind所支持的基本运算。
• 当图的边数为e时，Kruskal算法所需的计算时间是$O(eloge)$。当 $e=\Omega (n^2)$时，Kruskal算法比Prim算法差，但当$e=(n^2)$时，Kruskal算法却比Prim算法好得多。

（6）总结

---

7、多机调度问题

（1）介绍

 这个问题是NP完全问题，到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。

（2）解决

四、动态规划

（一）、动态规划算法

1、基本思想

保存已解决的子问题的答案，在需要时再找出已求得的答案，避免大量重复计算，从而得到多项式时间算法。

动态规划总体思想

2、动态规划基本步骤

• 找出最优解的性质，并刻划其结构特征。
• 递归地定义最优值。
• 以自底向上的方式计算出最优值。
• 根据计算最优值时得到的信息，构造最优解。

3、比较动态规划与分治法

例：Fibonacci序列问题

int Fibonacci(n) { 
                                                          F[1]=1; F[2]=1; for(i=3;i<=n;i++) F[i]=F[i-1]+F[i-2]; return F[n]; } 

4、动态规划算法的基本要素

（1）最优子结构性质

（2）重叠子问题

（二）、动态规划范例

1、矩阵连乘

略

2、备忘录方法

略

3、最长公共子序列问题

（1）问题

 子序列：给定序列$X=x_1,x_2,\dots ,x_m$，另一序列$Z=z_1,z_2,\dots ,z_k$，若存在一个严格递增下标序列$i_1,i_2,\dots ,i_k$使得对于所有j=1,2,…,k有：$z_j=x_{i_j}$，则Z是X的子序列。
 公共子序列：给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
问题：求找出一个最长公共子序列。

（2）递归表达式

（3）算法

void LCSLength(int m,int n, char *x,char *y, int **c, int **b) { 
                                                          for (int i = 0; i <= m; i++) c[i][0]=0; for (int i = 1; i <= n; i++) c[0][i]=0; for (int i = 1; i <= m; i++){ 
                                                          for (int j = 1; j <= n; j++) { 
                                                          if (x[i]==y[j]) { 
                                                          c[i][j]=c[i-1][j-1]+1; b[i][j]=‘↖’; }else if (c[i-1][j]>=c[i][j-1]) { 
                                                          c[i][j]=c[i-1][j]; b[i][j]=‘↑’; }else { 
                                                          c[i][j]=c[i][j-1]; b[i][j]= ‘←’; } } } } 

时间复杂度：O（n+m）

4、0-1背包问题

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

Void knapsack(int *v, int *w,int c,int n,int **m)//m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值，即最大价值和。 { 
                                                          int jMax=min(w[n]-1,c); for(j=0;j<=jMax; j++) m[n][j]=0;//第n个物品无法装入 for(j=w[n]; j<=c; j++) m[n][j]=v[n];//装入第n个物品 for(i=n-1;i>1;i--){ 
                                                          jMax=min(w[i]-1,c); for(j=0;j<= jMax;j++) //无法装入第i个物品 m[i][j]=m[i+1][j]; for(j= w[i];j<=c;j++) //可以装入第i个物品 m[i][j]=max(m[i+1][j], m[i+1][j- w[i]]+v[i]); } m[1][c]=m[2][c]; if(c>=w[1]) //可以装入第1个物品 m[1][c]=max(m[1][c], m[2][c- w[1]]+v[1]); } 

5、投资问题

Invest(m,n,f[n][m],g[n][m],d[n][m]){ 
                                                          //d[i][j]：前i项工程投资额为j时，向第i项工程的投资额 //向前i项工程投资额为j时，f[i][j]获得最大收益 for(j=0;j<=m;j++){ 
                                                          //只投资第1项工程，投资额为j时，获得最大收益 f[1][j]=g[1][j]; d[1][j]=j; } for(i=2;i<=n;i++){ 
                                                          for(j=0;j<=m;j++){ 
                                                          f[i][j]=0; for(k=0;k<=j;k++){ 
                                                          s=f[i-1][j-k]+g[i][k]; if(s>f[i][j]) { 
                                                          f[i][j]=s; d[i][j]=k; } } } } } 

时间复杂度分析：$O(n{m}^2)$
空间复杂度分析 :$O(nm)$

五、回溯法

（一）、回溯算法

1、定义

回溯法（也称试探法）：将问题候选解按某一顺序逐一枚举和试探的过程。

2、三种可能的情况：

• 发现当前候选解不可能是可行解或最优解，则直接选下一个候选解 回溯
• 当前候选解除了不满足问题规模的要求外，满足所有其他要求，则继续扩大当前候选解规模 试探
• 满足包括问题规模在内的所有要求，则该候选解就是问题的一个可行解或最优解 解

3、概述

• 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。
• 算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。
• 如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

可行解：满足约束条件的解。解空间中的一个子集 。
最优解：使目标函数取极值（极大或极小）的可行解，一个或少数几个 。

4、基本思想

• 确定了解空间的组织结构后，回溯法就从开始结点(根节点)出发，以深度优先的方式搜索整个解空间。
• 深度优先的问题状态生成法：
  • 对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。
  • 完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子(若有)
  • 在一个扩展结点变成死结点之前，它一直是扩展结点
• 回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。

扩展结点:一个正在产生儿子的结点称为扩展结点
活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点
死结点:一个所有儿子已经产生的结点称做死结点

5、问题的解空间

问题的解空间： 对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。
例：n=3的0-1背包问题

问题的解向量：回溯法希望一个问题的解能够表示成一个n元式（x1,x2, …, xn）的形式。
显约束：对分量xi的分量限定。
隐约束：为满足问题的解而对不同分量之间施加的约束。

6、回溯法步骤

剪枝函数：

7、算法框架

（1）递归回溯

回溯法对解空间作深度优先搜索，因此，在一般情况下用递多一点。

（2）迭代回溯

采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。

（3）子集树

子集树：当所给问题是从n个元素的集合S中找出S满足某种性质的子集时，相应的解空间树称为子集树。如：n个物品的0-1背包问题所相应的解空间树。
遍历子集树需$O(2^n)$计算时间。

（4）排列数

排列树：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。如：旅行售货员问题的解空间树。
遍历排列树需要O(n!)计算时间。

（二）、范例学习

1、n皇后问题

（1）问题

（2）分析

• 解向量：$(x_1,x_2,\dots ,x_n)$
• 显约束：$x_i=1,2,\dots ,n$（所在列）
• 隐约束：
  • 不处于同一正、反对角线： |i-j| != |xi-xj| (如何推算？)

  不同列： xi !=xj

（3）递归算法

bool Queen::Place(int k) { 
                                                          for (int j=1;j<k;j++) if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false; return true; } void Queen::Backtrack(int t)//t行 { 
                                                          if (t>n) sum++;输出解； else{ 
                                                          for (int i=1;i<=n;i++) { 
                                                          x[t]=i;//设定列值，选取扩展结点 if (Place(t)) Backtrack(t+1);//试探第t+1行 } } } 

（4）非递归算法

backtrack(){ 
                                                          X[1]=0; int k=1; While(k>0){ 
                                                          x[k]+=1; while((x[k]<=n)&&!(place(k))) x[k]+=1; if(x[k]<=n) if(k==n) sum++;输出解； else{ 
                                                          k++; x[k]=0; } else { 
                                                          x[k]=0; k--; } } } Place(int k){ 
                                                          for(int j=1;j<k;j++){ 
                                                          if((abs(k-j)==aba(x[j]-x[k])) ||(x[j]==x[k])) return false; } return true; } 

(5)4皇后的状态空间树

2、图的m着色问题

（1）问题

 给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。
 若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。

（2）分析

（3）算法

void backtrack(int t){ 
                                                         //递归算法 //t->节点t if(t>n){ 
                                                          sum++; //输出解 // for(int i=1;i<=n;i++) //cout<<x[i]<<" "; }else{ 
                                                          for(int i=1;i<=m;i++){ 
                                                          x[t]=i; if(ok(t)) backtrack(t+1);//试探第t+1个节点 x[t]=0; } } } bool ok(int k){ 
                                                          for(int j=1;j<=n;j++){ 
                                                          if(a[k][j]&&(x[j]==x[k]))//如果两图相连并且颜色相同 return false; return true; } M_coloring(int n, int m, int g[][]) { 
                                                          //非递归算法1 for(i=1;i<=n;i++) x[i]=1; k=1; do{ 
                                                          if(x[k]<=m){ 
                                                          for (i=1;i<k;i++) { 
                                                          if(g[i][k]==1 and x[i]==x[k]) break; } if(i<k) x[k]++; else k++; }else{ 
                                                          x[k]=1; k=k-1; if(k>=1) x[k]++; } }while(k<=n and k>=1) if(k>n) 输出解； if(k<1) 无解； } M_coloring(int n, int m, int g[ ][ ]){ 
                                                          //非递归算法2 for(i=1;i<=n;i++) x[i]=0; k=1; while(k>0){ 
                                                          x[k]=x[k]+1; while(x[k]<=m&&!color(k)) x[k]=x[k]+1; if(x[k]<=m){ 
                                                          if(k==n){ 
                                                          输出x[ ]; break; }else //试探 k++; }else{ 
                                                         //回溯 x[k]=0; k=k-1; } } } Bool Color(k){ 
                                                          for(i=1;i<=n;i++) if(g[i][k]==1 and x[i]==x[k]) return(false); return(true); } 

3、 0-1背包问题

上界函数bound(): 当前价值cw+剩余容量可容纳的最大价值<=当前最优价值bestp。

解向量：$(x_1,x_2,\dots ,x_n)$
显约束：$x_i=1,0$
隐约束： ∑ i = 1 n w i x i < = c   ,   x i ∈ { 0 , 1 } , 1 < = i < = n \sum ^n_{i=1}{w_ix_i<=c} \ ,\ x_i\in\{0,1\},1<=i<=n ∑i=1n​wi​xi​<=c , xi​∈{
0,1},1<=i<=n
目标函数：${\sum }_{i=1}^n{v}_i{x}_i$

其它：装载问题\旅行商问题\迷宫问题\子集和数问题

六、分支限界法

1、概述

• 一种求解离散最优化问题的计算分析方法，又称分枝定界法。
• 这种方法通常仅需计算和分析部分允许解，即可求得最优解。
• 同回溯法一样适合解决组合优化问题。

2、分支限界法的基本思想

分支限界法与回溯法

• 求解目标不同：

回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

• 搜索方式的不同:

回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费(或最大效益)优先的方式搜索解空间树。

基本思想

• 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
• 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
• 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。
• 这个过程一直持续到找到所需的解或活结点表为空时为止。

常见的两种分支限界法

• 队列式(FIFO)分支限界法：
  • 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
• 优先队列式分支限界法：
  • 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。