1 算法简介
1.1 算法的定义
算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。
1.2 算法的特性
1、有穷性（Finiteness）：算法必须能在执行有限个步骤后终止。
2、确定性（Definiteness）：算法的每一步骤必须有确切的含义。
3、输入项（Input）：一个算法有零个或多个输入，这些输入取自某个特定的对象集合。
4、输出项（Output）：一个算法有一个或多个输出，以反映对输入数据加工后的结果。
5、可行性（Effectiveness）：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
1.3 算法的表示
1、自然语言
2、流程图
3、程序设计语言
4、伪代码
1.4 算法设计
常用的算法设计策略有：分治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等。
1.5 算法分析
算法分析技术的主要内容：正确性、可靠性、简单性、易理解性、时间复杂度和空间复杂度等。
2 算法设计之常见算法设计策略
2.1 分治法
2.1.1 基本思想
分治法的基本思想：将一个难以直接解决的大问题，分解成一些规模较小的子问题，这些子问题相互独立且与原问题相同，然后各个击破，分而治之。
分治法常常与递归结合使用：通过反复应用分治，可以使子问题与原问题类型一致而规模不断缩小，最终使子问题缩小到很容易求出其解，由此自然导致递归算法。
人们从大量实践中发现，在使用分治法时，最好均匀划分。这种使子问题规模大致相等的做法源自一种平衡子问题的思想，它几乎总是比使子问题规模不等的做法好。
一般来说，分治算法在每一层递归上都有3个步骤。
(1) 分解。将原问题分解成一系列子问题。
(2) 求解。递归地求解各子问题。若子问题足够小，则直接求解。
(3) 合并。将子问题的解合并成原问题的解。
2.1.2 典型实例
1 归并排序
归并排序算法是成功应用分治法的一个完美的例子，其基本思想是将待排序元素分成大小大致相同的两个子序列，分别对这两个子序列进行排序，最终将排好序的子序列合并为所要求的序列。
归并排序算法完全依照上述分治算法的3个步骤进行。
(1) 分解。将n个元素分成各含n2个元素的子序列。
(2) 求解。用归并排序对两个子序列递归地排序。
(3) 合并。合并两个已经排好序的子序列以得到排序结果。
归并排序算法的C代码如下：
// 其中，A是数组，p、q和r是下标，满足p≤q void MergeSort(int A[], int p, intr){ int q; if(p q=(p+r) / 2; MergeSort(A, p, q); MergeSort(A, q+1, r); Merge(A, p, q, r); } } void Merge(int A[], int p, int q, int r){ int nl=q-p+1, n2=r-q, i, j, k; int L[50],R[50]; for(i=0;i< nl;i++) L[i] = A[p+i]; for(j=0;j R[j] = A[q+j+1]; L[n1] = INT_MAX; R[n2] = INT_MAX; i=0; j=0; for(k=p; k if(L[i] < R[j]){ A[k]=L[i]; i++; } else{ A[k]=R[j]; j++; } } } Merge 显然可在O(n)时间内完成，因此合并排序算法对n个元素进行排序所需的计算时间T(n)满足： T(n)={O(n),n≤12T(n/2)+O(n),n>1T(n)=\begin{cases}O(n),&n≤1\\2T(n/2)+O(n),&n>1\end{cases}T(n)={O(n),2T(n/2)+O(n),n≤1n>1 解此递归式可知T(n)=O(n log n)。 2 最大子段和问题 给定由n个整数(可能有负整数)组成的序列 a1，a2，… ,an，求该序列形如∑k=ijak\sum_{k=i}^{j}{a_k}∑k=ijak的子段和的最大值。当序列中所有整数均为负整数时，其最大子段和为0。依此定义，所求的最大值为 max{0,max1≤i≤j≤n∑k=ijak}max\{0,max_{1≤i≤j≤n}\sum_{k=i}^{j}{a_k}\}max{0,max1≤i≤j≤n∑k=ijak} 。例如，当(a1，a2，a3，a4，a5，a6) = -1,11,-4,13,-7,-3)时，最大子段和为 ∑k=24ak=20\sum_{k=2}^{4}{a_k}=20∑k=24ak=20。 最大子段和问题的分治策略如下： (1) 分解。如果将所给的序列A[1…n]分为长度相等的两段A[1…n/2]和A[n/2+1…n]，分别求出这两段的最大子段和，则A[1…n]的最大子段和有3种情形。 ① A[1…n]的最大子段和与A[1…n/2]的最大子段和相同。 ② A[1…n]的最大子段和与A[n/2+1…n]的最大子段和相同。 ③ A[1…n]的最大子段和为∑k=ijak\sum_{k=i}^{j}{a_k}∑k=ijak，且1≤i≤n/2，n/2+1≤j≤n。 (2) 求解。①和②这两种情形可递归求得。对于情形③，容易看出，A[n/2]与A[n/2+1]在最优子序列中。因此可以在A[1…n/2]中计算出s1=max1≤i≤n/2∑k=in/2akmax_{1≤i≤n/2}\sum_{k=i}^{n/2}{a_k}max1≤i≤n/2∑k=in/2ak ，并在A[n/2+1…n]中计算出s1 = maxn/2≤j≤n∑k=n/2jakmax_{n/2≤j≤n}\sum_{k=n/2}^{j}{a_k}maxn/2≤j≤n∑k=n/2jak 。则s1+s2即为出现情形③的最优值。 (3) 合并。比较在分解阶段的3种情况下的最大子段和，取三者之中的较大者为原问题的解。 据此可设计出求解最大子段和的分治算法如下： // 对于长度为n的序列，可以调用 MaxSubSum (Array, 0, n-1) 来获得其最大子段和。 // 其中，Array为数组，left和right表示数组下标。 int MaxSubSum(int *Array, int left, int right) { int sum = 0; int i,j; if(left ==right){ //分解到单个整数,不可继续分解 if(Array[left] > 0) sum=Array[left]; else sum=0; }else{ //从left和right的中间分解数组 //划分的位置 int center = (left + right) / 2; //情形1 int leftsum = MaxSubSum(Array,left,center); //情形2 int rightsum = MaxSubSum(Array,center+1,right); //情形3 int s1=0; int lefts = 0; for(i = center,i >= left;i--){ lefts = lefts + Array[i]; if(lefts > s1) s1 =lefts; } int s2 = 0; int rights =0; for(j=center + 1;j <=right;j++){ rights = rights + Array[j]; if(rights > s2) s2 = rights; } sum =s1+s2; //比较三种情形的最大子段和，得出最终结果 //情形1 if(sum < leftsum) sum = leftsum; //情形2 if(sum < rightsum) sum =rightsum; } return sum; } 分析算法时间复杂度如下：对应分解中的①和②两种情形，需要分别递归求解；对应情形③，两个并列for循环的时间复杂度为O(n)，因此得到下列递归式：T(n)={O(n),n≤12T(n/2)+O(n),n>1T(n)=\begin{cases}O(n),&n≤1\\2T(n/2)+O(n),&n>1\end{cases}T(n)={O(n),2T(n/2)+O(n),n≤1n>1 ，解此递归式可知T(n)=O(n log n)。 2.2 动态规划法 2.2.1 基本思想 动态规划法的基本思想： 与分治法类似，也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。然而，不同子问题的数目常常只有多项式量级。如果能够保存已解决的子问题的答案，在需要时再找出已求得的答案，这样就可以避免大量的重复计算，从而得到多项式时间的算法。为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每个解都对应于一个值，我们希望找到具有最优值(最大值或最小值)的那个解。当然，最优解可能会有多个，动态规划算法能找出其中的一个最优解。 设计一个动态规划算法，通常按照以下几个步骤进行。 (1) 找出最优解的性质，并刻画其结构特征。 (2) 递归地定义最优解的值。 (3) 以自底向上的方式计算出最优值。 (4) 根据计算最优值时得到的信息，构造一个最优解。 步骤(1) ~ (3)是动态规划算法的基本步骤。在只需要求出最优值的情形下，步骤(4)可以省略。 若需要求出问题的一个最优解，则必须执行步骤(4)。此时，在步骤(3)中计算最优值时，通常需记录更多的信息，以便在步骤(4)中根据所记录的信息快速构造出一个最优解。 对于一个给定的问题，若其具有以下两个性质，可以考虑用动态规划法来求解。 (1) 最优子结构。如果一个问题的最优解中包含了其子问题的最优解，就说该问题具有最优子结构。当一个问题具有最优子结构时，提示我们动态规划法可能会适用，但是此时贪心策略可能也是适用的。 (2) 重叠子问题。重叠子问题指用来解原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题。即当一个递归算法不断地调用同一个问题时，就说该问题包含重叠子问题。此时若用分治法递归求解，则每次遇到子问题都会视为新问题，会极大地降低算法的效率，而动态规划法总是充分利用重叠子问题，对每个子问题仅计算一次，把解保存在一个在需要时就可以查看的表中，而每次查表的时间为常数。 2.2.2 典型实例 1 0-1背包问题 有n个物品，第i个物品价值为viv_ivi，重量为wiw_iwi，其中viv_ivi和wiw_iwi均为非负数，背包的容量为W，W为非负数。现需要考虑如何选择装入背包的物品，使装入背包的物品总价值最大。 该问题可以形式化描述如下：目标函数为max∑i=1nviximax\sum_{i=1}^{n}v_ix_imax∑i=1nvixi，约束条件为∑i=1nwixi≤W\sum_{i=1}^{n}w_ix_i≤W∑i=1nwixi≤W ，满足约束条件的任一集合(x1, x2, …,xn)是问题的一个可行解，问题的目标是要求问题的一个最优解。 下面根据动态规划的4个步骤求解该问题： (1) 刻画0-1背包问题的最优解的结构。可以将背包问题的求解过程看作是进行一系列的决策过程，即决定哪些物品应该放入背包，哪些物品不放入背包。如果一个问题的最优解包含了物品n，即xn=1x_n=1xn=1，那么其余x1x_1x1，x2x_2x2，x3x_3x3 … xnx_nxn一定构成子问题1，2，3 … (n-1) 在容量为W−wnW-w_nW−wn时的最优解。如果这个最优解不包含物品n，即xn=0x_n=0xn=0，那么其余x1x_1x1，x2x_2x2，x3x_3x3 … xnx_nxn一定构成子问题1，2，3 … (n-1) 在容量为 W 时的最优解。 (2) 递归定义最优解的值。根据上述分析的最优解的结构递归地定义问题最优解。设 c[i, w] 表示背包容量为 w 时 i 个物品导致的最优解的总价值，得到下式。显然，问题要求 c[i,w]={0,i=0或w=0c[i−1,w],wi>wmax{c[i−1,w−wi]+vi,c[i−1,w]},i>0且wi (3) 计算背包问题最优解的值。基于上述递归式，以自底向上的方式计算最优解的值，代码如下： int** KnapsackDP(int n, int W, int* Weights, float* Values) { int i,w; //为二维数组申请空间 int** c = (int **)malloc(sizeof(int *)*(n+1)); for(i=0; i<=n; i++) c[i]= (int *)malloc(sizeof(int)*(W+1)); //初始化二维数组 for(w=0;w<=W;w++) c[0][w]=0; for(i=1;i<=n;i++){ c[i][0]=0; for(w=1;w<=W;w++){ if(Weights[i-1]<=w){//如果物品重量小于背包剩余重量 if(Values[i-1] + c[i-1][w-Weights[i-1] > c[i-1][w]{ //重量为w的背包中放入该物品 c[i][w]=Values[i-1] + c[i-1][w-Weights[i-1]]; }else{ //重量为w的背包中不放入该物品 c[i][w]=c[i-1][w] } }else{ c[i][w]=c[i-1][w]; } } } return c; } 上述C代码的时间复杂度为 O(n W)。 (4) 根据计算的结果构造问题最优解根据上一步计算的c数组很容易构造问题的最优解。判断c[i, w]与c[i-1, w]的值是否相等，若相等，则说明xix_ixi=0，否则为1。得到最优解的C代码如下： void OutputKnapsackDP(int n, int W, int *Weights, float *Values, int *c){ int x[n]; int i; for(i=n;i>1;i--){ if(c[i][W]-c(i- 1][W])//重量为w的最优选择的背包中不包含该物品 x[i-1]=0; else{ x[i-1]=1; W=W-Weights[i-1]; //更新背包目前的最大容量 } } if([1][W]==0) //第一个物品不放入背包 x[0]=0; else//第一个物品放入背包 x[0]=1; for(i=0;i if(x[i]==1) printf("Weigh: %d, Value: %f\n", Weights[i], Values[i]; } 构造最优解的时间复杂度为O(n)。 2 最长公共子序列（LCS） 子序列和子串的区别： 子序列：一个给定的序列的子序列，就是将给定序列中零个或多个元素去掉之后得到的结果。 子串：给定串中任意个连续的字符组成的子序列称为该串的子串。 同理，最长公共子序列（longest common sequence）和最长公共子串（longest common substring）也不同。 最长公共子序列问题定义：给定序列X=x1x2⋅⋅⋅xmX=x_1x_2···x_mX=x1x2⋅⋅⋅xm，和序列Y=y1y2⋅⋅⋅ynY=y_1y_2···y_nY=y1y2⋅⋅⋅yn，求这两个序列的最长公共子序列。 如果用穷举法求解该问题，列举出X的所有子序列，一检查其是否是Y的子序列，并随时记录所发现的公共子序列，最终求出最长公共子序列，时间复杂度为O(2mn2^m n2mn)，是指数级的时间复杂度，对于长序列来说不可行。 动态规划法可以有效地求解最长公共子序列问题： (1) 刻画最长公共子序列问题的最优子结构。 设X=x1x2...xmX=x_1x_2...x_mX=x1x2...xm和Y=y1y2,,,ynY=y_1y_2,,,y_nY=y1y2,,,yn，是两个序列，Z=z1z2...zkZ=z_1z_2...z_kZ=z1z2...zk是X和Y的一个最长公共子序列。则 ①如果xm=ynx_m=y_nxm=yn，那么zk=xm=ynz_k=x_m=y_nzk=xm=yn，且Zk−1Z_{k-1}Zk−1是Xm−1X_{m-1}Xm−1和Yn−1Y_{n-1}Yn−1的一个最长公共子序列。 ②如果xm≠ynx_m≠y_nxm=yn，那么zk≠xmz_k≠x_mzk=xm，且ZZZ是Xm−1X_{m-1}Xm−1和YYY的一个最长公共子序列。 ③如果xm≠ynx_m≠y_nxm=yn，那么zk≠ynz_k≠y_nzk=yn，且ZZZ是XXX和Yn−1Y_{n-1}Yn−1的一个最长公共子序列。 (2) 递归定义最优解的值。 第一步说明了LCS的特征，我们可以发现，假设我需要求Xm−1X_{m-1}Xm−1和YYY的LCS 或 XXX和Yn−1Y_{n-1}Yn−1的LCS，一定会递归地并且重复地把如Xm−1X_{m-1}Xm−1和Yn−1Y_{n-1}Yn−1的 LCS 计算几次。所以我们需要一个数据结构来记录中间结果，避免重复计算。 设l[i,j]l[i,j]l[i,j]表示序列XiX_iXi和YjY_jYj的最长公共子序列的长度，如果i=0或j=0，则其中有一个序列长度为0，因此LCS长度为0，由LCS的最优子结构可导出以下递归式。 l[i,j]={0,i=0或j=0l[i−1,j−1]+1,i,j>0或xi=yjmax{l[i−1,j],l[i,j−1]},i,j>0或xi≠yj l[i,j]= \begin{cases} 0 &,i=0或j=0\\ l[i-1,j-1]+1 &,i,j>0或x_i=y_j\\ max\{l[i-1,j],l[i,j-1]\} &,i,j>0或x_i≠y_j \end{cases} l[i,j]=⎩⎨⎧0l[i−1,j−1]+1max{l[i−1,j],l[i,j−1]},i=0或j=0,i,j>0或xi=yj,i,j>0或xi=yj (3) 计算最优解的值。 根据上述递归式自底向上地求出最优解的值。将l[i,j]l[i,j]l[i,j]的值存储在表l[1..m,1..n]l[1..m,1..n]l[1..m,1..n]中，以行为主序从左到右计算表lll中的元素，同时维持表b[1..m,1..n]b[1..m,1..n]b[1..m,1..n]，用其中的元素b[i,j]b[i,j]b[i,j]记录使得l[i,j]l[i,j]l[i,j]取最优值的最优子结构。以下给出该算法的C代码，分别用strl和str2表示序列X和Y。 int** Lcs_Length(const char* str1, const char* str2, int str1_length, int str2_length){ int i,j; // 为矩阵l、b分配空间 int** 1 = (int **)malloc(sizeof(int *)*(strl_length + 1)); int** b = (int **)malloc(sizeof(int *)*(str1_length + 1)); for(i=0; i<=strl_length; i++){ l[i] = (int *)malloc(sizeof(int)*(str2_length + 1)); b[i] = (int *)malloc(sizeof(int)*(str2_length + 1)); } //初始化矩阵 for(i=1;i<=str1_length;i++) l[i][0]=0; for(j=0;j<=str2_length;j++) l[0][j]=0; //一行一行地填写矩阵 for(i=1;i<=strl_length;i++){ for(j=1;j<=str2_length;j++){ if(str1[i-1]==str2[j-1]{ l[i][j] = l[i-1][j-1] + 1; b[i][j] = 0; //0代表指向左上方的箭头 }else if(l[i-1][j]>=l[i][j-1]{ 1[i][j] = l[i-1][j]; b[i][i] = 1; //1代表指向上方的箭头 }else{ 1[i][j] = l[i][j-1]; b[i][i] = 2; //2表向左方的箭头 } } } return b; } 从上述C代码可知，算法的时间复杂度为O(mn)。根据上述算法，已知X=ABCBDAB 和 Y=BDCABA，则对应的表l和b如表所示。 首先，xm=ynx_m=y_nxm=yn时，初始化表格： j0123456iYjY_jYjBDCABA0XiX_iXi00000001A02B03C04B05D06A07B0然后，xm≠ynx_m≠y_nxm=yn时，填充表格： j0123456iYjY_jYjBDCABA0XiX_iXi00000001A0↑0↑0↑0↖1←1↖12B0↖1←1←1↑1↖2←23C0↑1↑1↖2←2↑2↑24B0↖1↑1↑2↑2↖3←35D0↑1↖2↑2↑2↑3↑36A0↑1↑2↑2↖3↑3↖47B0↖1↑2↑2↑3↖4↑4(4) 构造最优解。 用表b中的信息构造X和Y的一个LCS。从b[m, n]开始，在表中沿着箭头的方向跟踪，当b[i,j]="↖"时，表示xi=yjx_i=y_jxi=yj；为LCS中的元素，c代码如下所示，分别用str1和str2表示序列X和Y。在上图所示的例子中，过程OutputLCS将产生以下输出：BCBA。 void OutputLcs(const char *str1,const int** b,int str1 length, int str2 1length){ if(str1_length|| str2_length == 0) //两个字符串中任何一个长度为零 return; if(b[str1_length][str2_length] == 0){ //箭头指向左上 OutputLcs(str1, b, str1_length-1, str2_length-1); printf("%c",strl[str1_length-1]); }else if(b[str1_length][str2_length] == 1) //箭头指向上 OutputLcs(str1, b, str1_length-1, str2_length); else //箭头指向左 OutputLcs(strl, b, str1_length, str2_length-1) } 时间复杂度：构建c[i][j]表需要O(mn)，输出1个LCS的序列需要O(m+n)。 2.3 贪心法 2.3.1 基本思想 贪心法的基本思想： 和动态规划法一样，贪心法也经常用于解决最优化问题。与动态规划法不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。 换而言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不能保证总能获得全局最优解，但通常能得到较好的近似最优解。举一个简单的贪心法例子，平时购物找钱时，为使找回的零钱的硬币数最少，从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小面值的币种，这就是在采用贪心法。这种方法在这里总是最优，是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如果只有面值分别为1、5和11单位的硬币，而希望找回总额为15单位的硬币，按贪心算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币。但最优的解答应是3个5单位面值的硬币。 对于一个给定的问题，若其具有以下两个性质，可以考虑用贪心法来求解。 (1)最优子结构。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。问题具有最优子结构是该问题可以采用动态规划法或者贪心法求解的关键性质。 (2)贪心选择性质。指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。这是贪心法和动态规划法的主要区别。证明一个问题具有贪心选择性质也是贪心法的一个难点。 2.3.2 典型实例 1 活动选择问题 活动选择问题是指若干个具有竞争性的活动要求互斥使用某一公共资源时如何选择最大的相容活动集合。 假设有一个需要使用某一资源(如教室等)的n个活动组成的集合S={a1,a2,...,an}S=\{a_1,a_2,...,a_n\}S={a1,a2,...,an}，该资源一次只能被一个资源占用。每个活动aia_iai有一个开始时间sis_isi和结束时间fif_ifi，且0≤si≤fi≤∞0≤s_i≤f_i≤∞0≤si≤fi≤∞。一旦被选择后，活动aia_iai就占据半开时间区间[si,fi)[s_i,f_i)[si,fi)。如果两个活动aia_iai和aja_jaj的时间区间互不重叠，则称活动aia_iai和aja_jaj是兼容的。活动选择问题就是要选择出一个由互相兼容的活动组成的最大子集合。 考虑表中的活动集合，其中各活动已经按结束时间的单调递增顺序进行了排序。从表中可以看到，子集{a3,a9,a11}\{a_3,a_9,a_{11}\}{a3,a9,a11}由相互兼容的活动组成。然而，它不是最大的子集，子集{a1,a4,a8,a11}\{a_1,a_4,a_8,a_{11}\}{a1,a4,a8,a11}更大。事实上，{a1,a4,a8,a11}\{a_1,a_4,a_8,a_{11}\}{a1,a4,a8,a11}是一个最大的相互兼容活动子集。另外，还有一个最大子集是{a2,a4,a9,a11}\{a_2,a_4,a_9,a_{11}\}{a2,a4,a9,a11}。 活动i1234567891011sis_isi130535688212fif_ifi4567891011121314经分析，该问题具有最优子结构，可以用动态规划法求解。但同时该问题还具有贪心选择性质，因此可以用贪心法更简单地求解。 定义集合Sij={ak∈S:fi≤sk≤fk≤sj}S_{ij}=\{a_k∈S:f_i≤s_k≤f_k≤s_j\}Sij={ak∈S:fi≤sk≤fk≤sj}。为了完整地表示问题，加入两个虚拟活动a0a_0a0和an+1a_{n+1}an+1，其中，f0=0f_0=0f0=0，sn+1=∞s_{n+1}=∞sn+1=∞，这样S=S0,n+1S=S_{0,n+1}S=S0,n+1。 【定理】对于任意非空子问题SijS_{ij}Sij，设ama_mam是SijS_{ij}Sij中具有最早结束时间的活动。那么， (1) 活动ama_mam在SijS_{ij}Sij的某个最大兼容活动子集中。 (2) 子问题SimS_{im}Sim为空，所以选择ama_mam将使SmjS_{mj}Smj为唯一可能非空的子问题。 假设对n个活动按其结束时间单调递增进行了排序，排序的时间复杂度为O(nlgn)。下面给出解决活动选择问题的贪心算法的递归形式和选代形式。 int OptimalSubset[100]; // 递归贪心算法（递归活动选择器） int RecursiveActivitySelector(int* s, int* f, int index, int n){ //s[0]和f[0]为0,活动开始时间和结束时间从下标1开始存储 int m = index +1; static int activity number = 0; while(m<=n && s[m]<=f[index])//寻找开始时间晚于index结束的活动 m++; if(m<=n){ OptimalSubset[activity_numbert++] = m;//选择找到的活动 RecursiveActivitySelector(s,f,m,n);//以活动m的结束时间为基准继续寻找 }else return activity_number; } // 迭代贪心算法（贪婪活动选择器） int GreedyActivitySelector(int *s, int *f, int n){ int activity_number = 0; OptimalSubset[activity_numbert++] = 1;//选择活动1 int index = 1; int m; for(m=2;m<=n;m++){ if(s[m]>=f[index]){//寻找开始时间晚于index结束的活动 OptimalSubset[activity_number++] = m; //选择找到的活动 index = m;//继续寻找 } } return activity_number; } 根据分析，递归贪心算法和迭代贪心算法都能在O(n)的时间复杂度内完成。 注：迭代是在局部内存进行重复计算，递归需要展开栈空间进行每一步的函数现场存储和结果存储。 2 背包问题 背包问题的定义与0-1背包问题类似，但是每个物品可以部分装入背包，即在0-1背包问题中，xi=0x_i=0xi=0或者xi=1x_i=1xi=1；而在背包问题中，0≤xi≤10≤x_i≤10≤xi≤1。 为了更好地分析该问题，考虑一个例子：n=5，W=100，下表给出了各个物品的重量、价值和单位重量的价值。假设物品已经按其单位重量的价值从大到小排好序。 物品i12345wiw_iwi3010205040viv_ivi6520306040vi/wiv_i/w_ivi/wi2.121.51.21为了得到最优解，必须把背包放满。现在用贪心策略求解，首先要选出度量的标准。 (1) 按最大价值先放背包的原则。 此时，先放物品1和4，获得价值65+60=125，背包还剩容量100-30-50=20，此时物品5是价值最大的，但其重量为40，不能全部放入背包。而且将物品2和3放入背包比把物品5的一半放入背包能获得更大的价值。因此把物品2放入背包，得到价值125+20=145，剩余容量20-10=10，此时可再放入物品3的1/3，得到总价值145+1.5×10=160，对应的解为{1，1，1/3，1，0}。 (2) 按最小重量先放背包的原则。 此时，将物品2、3、1和5放入背包中，刚好装满，得到价值20+30+65+40=155，对应的解为{1，1，1，0，1}。 (3) 按最大单位重量价值先放背包的原则。 此时，将物品1、2和3放入背包中，得到价值65+20+30=115，剩余容量100-30-10-20=40，此时可再放入物品4的4/5，得到总价值115+4/5X60=163，对应的解为{1, 1, 1, 4/5, 0}。可以证明，该解为问题的最优解，因此用贪心法求解背包问题，应根据该原则来放置物品。 假设对n个物品按其单位重量价值从大到小进行了排序，排序的时间复杂度为O(n lg n)。 下面给出用贪心法解决背包问题的C代码： // W表示背包的总容量，n表示物品个数，Weights表示重量数组，Values表示价值数组，x是每类物体装入的份额，属于[0,1] int * GreedyKnapsack(int n, int W, int* Weights, float* Values, float *VW){ int i; //分配空间及初始化 float* x = (float*)malloc(sizeof(float)*n); for(i=0;i x[i]=0; for(i=0;i if(Weights[i]<=W){//如果背包剩余容量可以装下该物品 x[i]=1; W=W-Weights[i]; } else break; if(i x[i] = W / (float)Weights[i]; } return x; } 2.4 回溯法 2.4.1 基本思想（深度优先） 问题的解空间：应至少包含问题的一个(最优)解。例如，对于有n种可选择物品的0-1背包问题，其解空间由长度为n的0-1向量组成。该解空间包含了对变量的所有可能的0-1赋值。当n=3时，其解空间是(0,0,0)，(0,0,1)，(0,1,0)，(0,1,1)，(1,0,0)，(1,0,1)，(1,1,0)，(1,1,1)。定义了问题的解空间后，还应将解空间很好地组织起来，使得用回溯法能方便地搜索整个解空间。通常将解空间表示为树或图的形式。例如，对于n=3时的0-1背包问题，其解空间用一棵完全二叉树表示。解空间树的第i层到第i+1层边上的标号给出了变量的值。从树根到叶子的任一路径表示解空间的一个元素。 回溯法的基本思想： 在确定了解空间的组织结构后，回溯法从开始结点(根结点)出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动(回溯)至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直到找到所要求的解或解空间中已无活结点时为止。 运用回溯法解题通常包含以下3个步骤： (1) 针对所给问题，定义问题的解空间。 (2) 确定易于搜索的解空间结构。 (3) 以深度优先的方式搜索解空间。 限界函数：限界函数的设计是回溯法的一个核心问题。设计限界函数的通用指导原则是尽可能多和尽可能早地“杀掉”不可能产生最优解的活结点。 2.4.2 典型实例 1 0-1背包问题 0-1背包问题的定义见动态规划法典型实例。 在该问题中，目标是为了得到最大的价值,因此可以“杀掉”那些不可能产生最大价值的活结点。那么，如何判断哪些结点扩展后不可能产生最大价值呢？考虑贪心策略，先对所有物品按其单位重量价值从大到小排序，对搜索空间树中的某个结点，已经确定了某些X(i)，1≤i≤k，而其他的X(i)，k+1≤i≤n待定。此时可以将0-1背包问题松弛为背包问题，求从该结点扩展下去，计算能获得的最大价值。若该价值比当前已经得到的某个可行解的值要小，则该结点不必再扩展。 若所有物品已经按其单位重量价值从大到小排序。假设前k(包含k)个物品是否放入背包已经确定，现在考虑在当前背包的剩余容量下，若是背包问题，那么能获得的最大价值是多少？即求背包中物品的价值上界。C代码如下： // W表示背包的总容量，n表示物品个数，Weights表示重量数组，Values表示价值数组，Weight表示获得最大价值时背包的重量，Profit表示背包获得的最大价值，X表示问题的最优解 // Profit Gained, Weight Used, k分别为当前已经获得的价值、背包的重量、已经确定的物品 float Bound(float* Values,int* Weights,float * VW,int n,int W,float Profit_Gained,int Weight_Used,int k){ int i; for(i=k+1;i if(Weight_Used+Weights[i]<=W){ Profit_Gained += Values[i]; Weight_Used += Weights[i]; }else{ Profit_Gained += VW[i]*(W-Weight_Used); Weight_Used = W; return Profit_Gained; } } return Profit_Gained; } // Values为物品的价值数组, Weights为物品的重量数组, VW为物品Values/Weights的数组, W为背包的最大容量 int * Knapsack(float* Values,int* Weights,float * VW,int n,int W){ int current_weight = 0; float current_profit = 0; int Weight = 0; float Profit = -1; int index =0; //为数组X、Y分配空间 int* X = (int*)malloc(sizeof(int)*n); int* Y = (int*)malloc(sizeof(int)*n); while(1){ while(index current_profit += Values[index]; current_weight += Weights[index]; Y[index]=1;index++; } if(index>=n){ Weight = current_weight; Profit = current_profit; index =n; int i; for(i=0;i X[i]=Y[i]; }else Y[index]=0; while(Bound(Values, Weights, VW, n, W, current_profit, current_weight, index) <= Profit){ while(index!=0 && Y[index]!=1){//向前回溯 index--; } if(index==0){ //输出结果 return X; } Y[index]=0; current_profit -= Values[index]; current_weight -= Weights[index]; } indext++; } } 假设n=8，W=110，物品的价值和重量如表所示。 物品i12345678viv_ivi1121313343535565wiw_iwi111212333434555则根据上述C代码得到如图所示的搜索空间树。 如图所示，树中的结点内若有数据，则上面表示背包当前的重量，下面表示背包当前的价值；结点内若无数据，则旁边的数据表示在现有的选择下背包能获得的价值的上界。X(i)=1和X(i)=0分别表示第i个物品放入和不放入背包中。 搜索过程： (1) 从第一个点开始向下扩展，扩展到将第四个点放入放入后，此时背包已经放入重量为56，价值为96。然后继续扩展，将第五个物品放入重量为89，价值为139。此时第六个物品无法继续放入，但是i=5的，也就是没有到达最后一个点，此时调用Bound()函数算出可能获得的最大的价值为164.66，那么继续向下扩展，但是无法放入物品了，继续调用Bound()判断是否向下扩展，直到最后一个物品也无法放入，确定此时搜索得到的可以获得的最大的价值为139，保存物品放入的选择。 (2) 然后开始回溯，回溯遇到第一个放入背包的物品对应的节点，将其取0（把物品拿出背包，进入右子树）。此时比较背包剩余重量，发现第六个物品可以放入背包，放入后背包重量为99，价值为149。但是，第七个物品无法继续放入，那么调用Bound()，发现可能获得162的价值，大于139，继续向下扩展，直到最后一个物品也无法放入，确定此时搜索得到的可以获得的最大的价值为149>139，更新可获得的价值，并且保存物品放入的选择。 (3) 继续回溯，直到回溯到根结点。此时的最大价值所对应的物品放入选择就是所求的解。此题解为159。 算法复杂度： 在最坏的情况下，所搜索的结果是一个满二叉树，此时相当于采用的就是穷举法，时间复杂度为O(2n)O(2^n)O(2n)，而每次决定是否要讲n个物品放入背包都要进行比较，这一步的时间复杂度为n，所以最坏情况下时间复杂度为O(n2n)O(n2^n)O(n2n)。 2 n皇后问题 问题描述：在一个nXn格的棋盘上放置n个皇后，使得任何两个皇后不能被放在同一行或同一列或同一条斜线上。 求解过程：从空棋盘开始，设在第1行至第m行都已经正确地放置了m个皇后，再在第m+1行上找合适的位置放第m+1个皇后，直到在第n行也找到合适的位置放置第n个皇后，就找到了一个解。接着改变第n行上皇后的位置，希望获得下一个解。另外，在任一行上有n种可选的位置。开始时，位置在第1列，以后改变时，顺次选择第2列、第3列、…、第n列。当第n列也不是一个合理的位置时，就要回溯，去改变前一行的位置。下图给出了回溯法求解4-皇后问题的搜索过程。 n皇后问题的限界函数可以根据问题的定义直接设计，即任意两个皇后不在同行、同列和同一斜线上，C代码如下： int Place(int* Column, int index){ int i; for(i=1;i int Column_differ = abs(Column[index] - Column[i]); int Row_differ = abs(index - i); if(Column[i]=Column[index] || Column_differ==Row_differ) return 0;// 有皇后与其在同列或同一斜线上 } return 1;// 没有皇后与其同行、同列或同对角线 } void N_Queue(int n){ int Column_Num[n+1]; int index = 1; int i; int answer_num = 0; for(i=1;i<=n;i++) Column_Num[i] = 0; while(index>0){ Column_Num[index]++; while(Column_Num[index]<=n && !Place(Column_Num,index)) //寻找皇后的位置 Column_Num[index]++; if(Column_Num[index]<=n){ if(index==n){ //最后一个皇后放置成功 answer_num++; for(i=1;i<=n;i++) Column_Num[index]++; }else{ //继续寻找下一个皇后的位置 index++; Column_Num[index] = 0; } }else index--; //当前皇后无法放置,回溯至上一个皇后 } } 2.5 分支限界法 2.5.1 基本思想（广度优先） 分支限界法的基本思想：类似于回溯法，分支限界法也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T，而分支限界法以广度优先或以最小耗费优先的方式搜索解空间树T。分支限界法的搜索策略是每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 分支限界法主要解决离散最优化的实际问题。 限界函数：与回溯法相似，限界函数的设计是分支限界法的一个核心问题。如何设计限界函数来有效地减小搜索空间是应用分支限界法要考虑的问题。 分支限界法的类型：根据从活结点表中选择下一扩展结点的不同方式，可将分支限界法分为几种不同的类型。最常用的有以下两种： (1) 队列式(FIFO，先进先出)分支限界法。队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选择下一个结点作为扩展结点。 (2) 优先队列式分支限界法。优先队列式分支限界法将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点作为扩展结点。优先队列中规定的结点优先级通常用一个与该结点相关的数值p来表示。结点优先级的高低与p值的大小相关。最大优先队列规定p值较大的结点优先级较高。在算法实现时，通常用一个最大堆来实现最大优先队列，用最大堆的Deletemax操作抽取堆中下一个结点成为当前扩展结点。类似地，最小优先队列规定p值较小的结点优先级较高。在算法实现时，常用一个最小堆来实现最小优先队列，用最小堆的Deletemin操作抽取堆中下一个结点成为当前扩展结点。 2.5.2 典型实例 1 0-1背包问题 n=3时0-1背包问题的一个实例：w=[16,15,15]，p=[45,25,25]，c=30，其解空间树如图所示。 用队列式分支限界法解此问题时，用一个队列来存储活结点表。算法从根结点A出发。 (1) 初始时活结点队列为空。 (2) 结点A是当前扩展结点，它的两个儿子结点B和C均为可行结点，故将这两个儿子结点按照从左到右的顺序加入活结点队列，并且舍弃当前扩展结点A。 (3) 按照先进先出的原则，下一个扩展结点是活结点队列的队首结点B。扩展结点B得到其儿子结点D和E，由于D是不可行结点，故被舍去。E是可行结点，被加入活结点队列。此时活结点队列中的元素是C和E。 (4) C成为当前扩展结点，它的两个儿子结点F和G均为可行结点，因此被加入活结点队列。此时活结点队列中的元素是E，F，G。 (5) 扩展下一个结点E，得到结点J和K，J是不可行结点，因而被舍去。K是一个可行的叶子结点，表示所求问题的一个可行解，其价值为45。此时活结点队列中的元素是F和G。 (6) 当前活结点队列的队首结点F成为下一个扩展结点。它的两个儿子结点L和M均为叶子结点。L表示获得价值为50的可行解，M表示获得价值为25的可行解。 (7) G是最后一个扩展结点，其儿子结点N和O均为可行叶子结点，N表示获得价值为25的可行解，O表示获得价值为0的可行解。最后活结点队列为空，算法终止。算法搜索得到最优解的值为50，对应的解为(0,1,1)。 2.6 概率算法 2.6.1 基本思想 概率算法的基本思想：前面讨论的算法对于所有合理的输入都给出了正确的输出，概率算法将这一条件放宽，把随机性的选择加入到算法中。在算法执行某些步骤时，可以随机地选择下一步该如何进行，同时允许结果以较小的概率出现错误，并以此为代价，获得算法运行时间的大幅度减少。概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次，可能得到完全不同的效果。这两次求解所需的时间甚至所得到的结果可能会有相当大的差别。如果一个问题没有有效的确定性算法可以在一个合理的时间内给出解，但是该问题能接受小概率错误，那么采用概率算法就可以快速找到这个问题的解。 2.7 近似算法 2.7.1 基本思想 近似算法的基本思想：是放弃求最优解，而用近似最优解代替最优解，以换取算洁设计上的简化和时间复杂度的降低。