算法期末整理

一算法概述

二递归与分治策略

三动态规划

四贪心算法

五回溯法

六分支限界法

七随机化算法

八线性规划与网络流

一算法概述

算法的概念

通俗地讲，算法是指解决问题的一种方法或一个过程。更严格地讲，算法是由若干条指令组成的有穷序列。

算法的性质

1.输入：有0个或多个由外部提供的量作为算法的输入。

2.输出：算法产生至少一个量作为输出。

3.确定性：组成算法的每条指令是清晰的，无歧义的。

4.有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。

程序与算法不同，程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质4。例如，操作系统是一个在无限循环中执行的程序，因而不是一个算法。

描述算法的多种方式：自然语言方式，表格方式，伪代码等。

算法复杂性的高低体现在运行该算法所需要的计算机资源的多少上，所需资源越多，该算法的复杂性越高；反之，所需资源越少，该算法的复杂性越低。对计算机资源，最重要的是时间和空间资源。算法的复杂性有时间复杂性和空间复杂性。

算法复杂性是算法运行需要的计算机资源的量。算法复杂性只依赖于要解的问题的规模、算法的输入和算法本身的函数。

最坏情况、最好情况和平均情况下的时间复杂度从某个角度反映算法的效率，各有局限性，各有用处。可操作性最好且最有实际价值的是最坏情况下的时间复杂度。

渐进符号

类似a=b

类似a<=b

类似a>=b

类似a<b

二递归与分治策略

直接或间接地调用自身的算法称为递归算法。

阶乘函数可以递归的表示

int factorial(int n){
    if(n==0) 
        return 1;
    return n*factorial(n-1);
}

斐波那契数列可以递归的表示

int fibonacci(int n){
    if(n<=1)
        return 1;
    return fibonacci(n-1)+fabonacci(n-2);
}

排列问题

Perm(t){
    if(t==n)
        print
    else
        for i= t~n    //让每个都做一下排头，然后把剩下的全排列，就变成了一个全新的全排列。
             Swap(a[t],a[i]);
             Perm(t+1);
             Swap(a[t],a[i]);    //交换回来，以便下一次全排列
}

汉诺塔问题

void hanoi(int n,int a,int b,int c){//参数b是目标塔座，参数c是辅助塔座
    //hanoi函数的任务是把n个圆盘通过辅助c塔,从a塔全搬到目标b塔

    if(n>0){    //如果n=0,此时没有圆盘需要移动了
        hanoi(n-1,a,c,b);
        //如果想把第n个移到目标，就需要把上面的n-1个挪走到辅助塔座

        move(a,b);    // move 是一个圆盘从指定塔到另一个指定塔的移动
        //执行完hanoi(n-1,a,c,b)之后，就可以移动第n个到目标塔座了

        hanoi(n-1,c,b,a);
        //这个时候在把辅助塔座上n-1个放到目标塔座的第n个上面

        //此时n个汉诺塔的转移全部完成
    }
}

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。

二分搜索算法，采用分治策略，可在最坏情况下用O(logn)的时间完成搜索任务。

二分法的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与x比较。如果x=a[n/2]，则找到x，算法终止；如果x<a[n/2]，则只在数组a的左半部继续搜索x；如果x>a[n/2]，则只在数组a的右半部继续搜索x。

int BinarySearch(int a[],int x,int n){
    int left = 0;
    int right = n-1;

    while(left <= right){
    
    int mid=(left+right)/2;

    if(x==a[middle])
        return middle;
    if(x>a[middle])
        left=middle+1;
    else
        right=middle-1;
    }
    return -1;
}

Strassen 矩阵乘法 (分治法 + 减少矩阵乘法次数)，矩阵乘法耗费的时间要比矩阵加(减)法耗费的时间多得多，要想改进矩阵乘法的计算时间复杂性，必须减少乘法运算。

棋盘覆盖问题

import java.util.Scanner;

public class Main {
    static int tile = 1;

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int k = sc.nextInt();
        int dr = sc.nextInt(); // 特殊方格所在行
        int dc = sc.nextInt(); // 特殊方格所在列

        int[][] Board = new int[(int) Math.pow(2, k)][(int) Math.pow(2, k)];
        Board[dr][dc]=0;
        ChessBoard(Board, 0, 0, dr, dc, Board.length);

        for (int i = 0; i < Board.length; i++) {
            for (int j = 0; j < Board.length; j++) {
                System.out.print(Board[i][j] + "\t");
            }
            System.out.println();
        }
    }
    public static void ChessBoard(int Board[][],int r_0,int c_0,int dr,int dc,int size){
        int s;
        int t;
        if (size==1) return;
        t=tile++;
        s=size/2;
        if (dr<=r_0+s-1 && dc<=c_0+s-1)
           ChessBoard(Board,r_0,c_0,dr,dc,s);
        else{
            Board[r_0+s-1][c_0+s-1]=t;
            ChessBoard(Board,r_0,c_0,r_0+s-1,c_0+s-1,s);
        }
        if (dr<=r_0+s-1 && dc>=c_0+s)
           ChessBoard(Board,r_0,c_0+s,dr,dc,s);
         else{
            Board[r_0+s-1][c_0+s]=t;
            ChessBoard(Board,r_0,c_0+s,r_0+s-1,c_0+s,s);
        }
         if (dr>=r_0+s && dc<c_0+s) //判断特殊方格是否在左下角子棋盘
           ChessBoard(Board,r_0+s,c_0,dr,dc,s);
         else //用t号骨牌覆盖右上角继续覆盖此子棋盘
         {
             Board[r_0 + s][c_0 + s - 1] = t;
             ChessBoard(Board, r_0 + s, c_0, r_0 + s, c_0 + s - 1, s);
         }
         if (dr>=r_0+s && dc>=c_0+s) //判断特殊方格是否在右下角子棋盘
           ChessBoard(Board,r_0+s,c_0+s,dr,dc,s);
         else //用t号骨牌覆盖左上角继续覆盖此子棋盘
         {
             Board[r_0+s][c_0+s]=t;
             ChessBoard(Board,r_0+s,c_0+s,r_0+s,c_0+s,s);
         }
    }
}

合并排序

合并排序算法是用分治策略实现对n个元素的进行排序的算法，其基本思想是：将待排序元素分成大小大致相同的两个子集合，分别对两个子集合进行排序，最终将排好的子集合合并成要求的排好序的集合。

MergeSort(int a[],int left,int right){    //left从左面指，right从右面指
//MergeSort的作用是给数组a做合并排序
    if(left<right){
        int i=(left+right)/2;    //i取中间
        MergeSort(a,left,i);     //对左面合并排序
        MergeSort(a,i+1,right);  //对右面合并排序
        Merge(a,b,left,i,right);    //排完序后合并到数组b,数组b是一个中间数组
        Copy(a,b,left,right);    //因为是给数组a排序，所以把数组b原封不动挪到数组a
    }
}

快速排序算法是基于分治策略的另一个排序算法。其基本思想是，对于输入的子数组a[p:r]，按以下三个步骤进行排序。

分解：以a[p]为基准元素将a[p:r]划分成3段a[p:q-1]，a[q]和a[q+1:r]，使a[p:q-1]中的任何一个元素小于等于a[q]，而a[q+1:r]中任何一个元素大于等于a[q]。下标q在划分过程中确定。

递归求解：通过递归调用快速排序算法，分别对a[p:q-1]和a[q+1:r]进行排序。

合并：由于对a[p:q-1]和a[q+1:r]的排序使就地进行的，因此在a[p:q-1]和a[q+1:r]都已排好的序后，不需要执行任何计算，a[p:r]则已排好序。

void QuickSort(int a[],int p,int r){
//QuickSort的功能是对a数组下标p到r的部分进行快速排序
    if(p<r){    //当p=r,就要排的数了
        int q=Partition(a,p,r); 
        //取下标q,从而分成左右两部分
        //比a[q]小的放左边，大的放右边

        QuickSort(a,p,q-1);        //对左边的进行排序
        QuickSort(a,q+1,r);        //对右边的进行排序
    }

    不停的递归调用，拆成两部分，直到要排的只有一个数（或不存在）就停止
}

三动态规划

动态规划的基本要素：最优子结构性质，重叠子问题性质

动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干子问题，先求解子问题，再结合这些子问题的解得到原问题的解。与分治法不同的是，适合用动态规划求解的问题经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，以致最后解决原问题需要耗费指数级时间。然而，不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，在需要时再找出已求得的答案，这样可以避免大量的重复计算，从而得到多项式时间算法。（所以动态规划又叫填表法）

动态规划适用于解最优化问题，通常4个步骤：

1.找出最优解的性质，并刻画其结构特征。

2.递归地定义最优解。

3.自底向上的方式计算最优值。

4.根据计算最优值时得到的信息构造最优解。

最优子结构：问题的最优解包含了其子问题的最优解。

重叠子问题：递归自顶向下解问题时，每次产生的子问题不总是新问题，有些子问题被反复计算。动态规划对每个子问题只解一次，然后将解保留在一个表格中。

相同的子问题反复出现，并且不同子问题的个数相对较小时，用动态规划算法是有效的。

矩阵连乘问题

求需要的数乘次数最少

假设A1，A2，A3矩阵维数分别是10*100，100*5，5*50，

如果按((A1A2)A3)计算，3个矩阵连乘积需要数乘次数=10*100*5+10*5*50=7500

如果按(A1(A2A3))计算，3个矩阵连乘积需要数乘次数=100*5*50+10*100*50=75000

以此类推......

将矩阵连乘积A1*A2*...*An记为A[i:j]。

所以A[1:n]的计算量就是A[1:k]的计算量加上A[k+1:An]的计算量，再加上A[1:k]和A[k+1:n]相乘的计算量。

那么A[1:n]如果是最优的，A[1:k]和A[k+1:n]这俩必须也是最优的。

设A[i,j]所需的最少乘次数为m[i][j]。

其中k还未定，k的位置有j-i种可能，k是这j-i个位置中使计算量达到最小的那个位置。

但是这样的话，许多子问题被重复计算多次。

所以还有记录最优断开位置的数组s和记录输入参数的数组p。

void MatrixChain(int *p, int n, int **m, int **s){
    for(int i=1;i<=n;i++)
        m[i][i]=0;    
        //填表，只有一个矩阵，都没有矩阵和它乘，数层数次数等于0
        //也就是表的对角线都填0
    for(int r=2;r<=n;r++){
        for(int i=1;i<=n;i++){
            int j=i+r-1;
            //对角线向上平移r格得新的斜线，开始走这条新斜线，这个斜线上列比行多r-1（r从2到n）
            //r最开始是2，j比i多1，总共两个矩阵相乘求连乘次数
            //当r=n已经把表填完了，两个for嵌套循环结束
            //很明显这是自底向下的

            m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];    //m[i][j]最开始的初值
            //默认是i处断开，m[i][j]=0+m[i+1][j]+p[i-1]*p[i]*p[j]
            //左边乘次数0，右边乘次数m[i+1][j]
            //左右相乘次数p[i-1]*p[i]*p[j]
            
            s[i][j]=i;    //s[i][j]最开始的初值

            for(int k=i+1;k<j;k++){    //for循环之后，最优值t赋给m[i][j]
                int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                if(t<m[i][j]){
                    m[i][j]=t;
                    s[i][j]=k;    //i和j之间断开处为s[i][j](也就是k)的时候得到最优值
                }
            }
        }
    }
}

计算次序如下图，可以看出是自底向上。最开始填表解决的是简单问题，最后得到复杂问题的解。

备忘录方法

与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。

最长公共子序列

一个给定序列的子序列是在该序列中删除若干元素后得到的序列。

最长公共子序列具有最优子结构的性质。

递归结构/递归关系

计算最优值：最长公共子序列的长度c[m][n]（X长度m,Y长度n）

void LCSLength(int m, int n, char *x, char *y ,int **c,int **b){
    int i,j;
    for(i=1;i<=m;i++)
        c[i][0]=0;    //j=0的位置都填0，因为Xi和一个空序列的公共子序列肯定空。
    for(i=1;i<=n;i++)
        c[0][i]=0;    //同理，i=0的位置都填0
    for(i=1;i<=m;i++){
        for(j=1;j<=n;j++){
            if(x[i]==y[j]){
                c[i][j]=c[i-1][j-1]+1;    
                b[i][j]=1;    //b[i][j]用来记录c[i][j]的值是由哪个子问题得到的。
                //1是Xm=Yn,则Zk=Xm=Yn,且Zk-1是Xm-1和Yn-1的最长公共子序列，也就是上上图的圈1和上图的中间那行。
            }    //下面是为了找c[i][j]的取值，也就是c[i-1][j]和c[i][j-1]中更大的那个，此时Xi和Yi的最后一个元素不相等。Xi和Yj的最长公共子序列应该和Xi-1和Yj的最长公共子序列或Xi和Yj-1的最长公共子序列相等，要求长度最长，取两者中较大的
                else if(c[i-1][j]>=c[i][j-1]){
                c[i][j]=c[i-1][j];
                b[i][j]=2;
                //2是上上图的圈2 和 上图的第三行更大的是c[i-1][j]
            }
            else{
                c[i][j]=c[i][j-1];
                b[i][j]=3;
                //3是上上图的圈3 和 上图的第三行更大的是c[i][j-1]
            }
        }
    }
}

构造最长公共子序列

//刚刚的代码只求了长度，下面的代码可以打印最长公共子序列

void LCS(int i,int j, char *x, int **b){
    if(i==0||j==0)    到头返回
        return;
    if(b[i][j]==1){
        LCS(i-1,j-1,x,b);    //x[i]和y[j]相等，输出任意一个都行
        cout<<x[i];          //相同元素的输出，最后一定会把公共子序列的元素都输出出来。
    }
    else if(b[i][j]==2)
        LCS(i-1,j,x,b);    //这种情况是Z是Xi-1和Yj的最长公共子序列 
    else
        LCS(i,j-1,x,b);    //这种情况是Z是Xi和Yj-1的最长公共子序列
}

最大字段和

没画重点，不写。

四贪心算法

顾名思义，贪心算法总是做出在当前看来是最好的选择。也就是说，贪心算法并不从整体最优上加以考虑，所做的选择只是在某种意义上的局部最优选择。

虽然贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题能产生整体最优解，如最小生成树问题、图的单源最短路径问题等。

贪心算法的基本要素：

1.最优子结构性质：一个问题的最优解包含其子问题的最优解。

2.贪心选择性质：所求问题可以的整体最优解可以通过一系列局部最优的选择(即贪心选择)来达到。

贪心算法和动态规划算法都要求问题具有最优子结构性质。背包问题（可以装一部分，不一定全部装入）可以用贪心算法求解，而0-1背包问题（要么装，要么不装）不能用贪心算法求解。

对于0-1背包问题，贪心选择之所以不能得到最优解是因为，在这种情况下，无法保证最终能将背包装满，部分闲置的背包空间使每千克背包空间的价值降低了。事实上，考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，再做出最好选择。由此可导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。动态规划确实可以有效解决0-1背包问题。

活动安排问题

活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

各活动的起始时间和结束时间存储于数组s和f中，且按时间排序的非减序列。

void GreedySelector(int n, int s[], int f[], bool A[]){
    A[1]=true;
    //活动1要，因为是最早结束的，留给后面活动的时间多
    int j=1;    //记录活动1的下标，方便后面活动2的开始时间和活动1的结束时间做比较
    for(int i=2;i<=n;i++){    //n个活动
        if(s[i]>=f[j]){    //活动2的开始时间和活动1的结束时间做比较
            //一种情况，时间没撞，该活动可以被安排进来
            A[i]=true;
            //活动2的开始时间比活动1的结束时间晚，时间没撞，活动2可以被安排进来
            //以此类推，活动i的开始时间比活动j的结束时间晚，时间没撞，活动i可以被安排进来
            j=i;
            //活动i被安排进来，更新活动i的下标，用活动i的结束时间和下一个活动开始时间比较
        }
        else    //另一种情况，时间撞了，该活动不被安排进来
            A[i]=false;
    }
}

背包问题（与0-1背包的区别看前面）

//n个物品 M背包容量 v[i]物品i的价值 w[i]物品i重量 x[i]物品i是否装进去
void Knapsack(int n, float M, float v[], float w[], float x[]){
    Sort(n,v,w);    //给n个物品按照单位价值进行降序排序
    int i;
    for(i=1;i<=n;i++)
        x[i]=0;    //默认每一个都不装
    float c=M;    //c是背包剩余容量，等于背包总容量M
    for(i=1;i<=n;i++){    //从价值比较大的物品开始找
        if(w[i]>c)    如果第i个物品不能装下（重量比背包剩余容量大），跳出for循环而不是开始下一轮新的for循环
            break;
        x[i]=1;    //如果第i个物品能装下（重量比背包剩余容量大），装物品i，x[i]=1表示装物品[i]
        c-=w[i];    //装了物品i之后背包剩余容量减少
    }
    if(i<=n)    //如果还有东西没装（break导致的）那就装c/w[i]，取值再0（没装）和1（全装）之间
        x[i]=c/w[i];

    //for如果没经过break,i=n+1，进不来上面的if,所有如果执行了上面的if，一定是break了
}

哈夫曼编码

哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方式

前缀码：对每个字符规定一个0，1串作为其代码，并要求任一字符的代码都不是其他代码的前缀。

最优前缀码的二叉树总是一棵完全二叉树，即树中任意结点都有两个儿子。

构造哈夫曼编码

有点多回头再弄

最小生成树

构造最小生成树的Prim和Kruskal算法都可以看作应用贪心算法设计策略的典型例子。尽管他们做贪心选择的方式不同，但他们都利用了下面的最小生成树性质（MST性质）。

两种方法构造最小生成树

Prim算法（加点法）

Kruskal算法（加边法）

五回溯法

回溯法有"通用的解题法"之称，可以系统地搜索一个问题的所有解或任意解，它是一个既带有系统性又带有跳跃性的搜索算法。在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树，算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解——如果肯定不包含，则跳过对以该结点为根大的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯法求问题所有解时，只要搜索到问题的一个解就可结束。这种以深度优先方式系统搜索问题解的算法称为回溯法，适合解组合数较大的问题。

回溯法的算法框架

1.问题的解空间

例如 0-1背包问题的解空间树

2.回溯法的基本思想

确定了解空间的组织结构后，回溯法从开始结点（根节点）出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新节点。这个新节点就成为新的结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为了死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点为止。

回溯法解旅行售货员问题

某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或总旅费）最小。

回溯法搜索解空间树时，通常采用两种策略来避免无效搜索，提高回溯法的效率。其一是用约束函数在扩展结点处剪去不满足约束的子树，其二是用限界函数剪去得不到最优解的子树。这两类函数统称为剪枝函数。

解0-1背包问题的回溯法用剪枝函数减去导致不可行解的子树。

解旅行售货员问题的回溯法，如果从根结点到当前扩展结点处的部分周游路线费用已经超过当前找到的最好的周游路线费用，则可以断定以该结点为根的子树中不含最优解，因此可将该子树剪去。

回溯法解题3个步骤：1.针对问题定义解空间；2.确定易于搜索的解空间结构；3.以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

3.递归回溯

void Backtrack(int t){    //t表示递归深度
    if(t>n)    //到叶节点
        Output(x);    //输出可行解
    else{
        for(int i=f(n,t);i<=g(n,t);i++){    //没到叶节点就要继续递归
            x[t]=h(i);
            if(Constraint(t)&&Bound(t)){    //剪枝函数
                Backtrack(t+1);
            }
        }
    }
}

4.迭代回溯

不考跳了

void IterativeBacktrack(void){
    int t=1;
    while(t>0){
        if(f(n,t)<=g(n,t)){
            for(int i=f(n,t);i<=g(n,t);i++){
                x[t]=h(i);
                if(Contraint(t)&&Bound(t)){
                    if(Solution(t))
                        Output(x);
                    else
                        t++;
                }
            }
        }
    }
}

用回溯法解题的一个显著特征是，在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根节点到当前扩展结点的路径。如果解空间树中从根节点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。

5.子集树与排列树

当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。例如n个物品的0-1背包问题所对应的解空间树就是一棵子集树。

当所给的问题是确定n个满足某种性质的排列时，相应的解空间树称为排序树。例如旅行售货员问题所对应的解空间树就是一棵排列树。

回溯法搜索子集树

//子集树0，1两个取值，表示解空间的某元素是要着还是不要着
void Backtrack(int t){    //t表示递归深度
    if(t>n)    //到叶节点
        Output(x);    //输出可行解
    else{    //没到叶节点就要继续递归
        for(int i=0;i<=1;i++){    //两个选择0，1。左子树0，右子树1
            x[t]=i;    //对于0-1背包问题来说，i=1放包里，i=0不放包里
            if(Constraint(t)&&Bound(t)){    //剪枝函数
                Backtrack(t+1);
            }
        }
    }
}

回溯法搜索排序树

void Backtrack(int t){    //t表示递归深度
    if(t>n)    //到叶节点
        Output(x);    //输出可行解
    else{     //没到叶节点就要继续递归
        for(int t;i<=n;i++){   
            Swap(x[t],x[i]);    //如果把把剪枝条件去掉，就和第二章递归的全排列问题一模一样！
            if(Constraint(t)&&Bound(t)){    //剪枝函数
                Backtrack(t+1);
            }
            Swap(x[i],x[t]);
        }
    }
}

n后问题

之前的笔记里面写过，子集树问题，和上面的代码差不多

n后问题回溯笔记-CSDN博客

0-1背包问题的回溯算法

有点多，回头补

六分支限界法

分支限界类似回溯法，也是在解空间上搜索问题解的算法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法的主要区别在于它们对当前扩展结点所采用的扩展方式不同。在分支限界法中，每个活结点只有一次机会成为扩展结点。活结点一旦称为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或者非最优解的儿子结点被舍弃，其余儿子结点，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这一过程一直持续到找到所需的解或活结点表为空为止。

从活结点表中选择下一扩展结点的不同方式导致不同的分支限界。最常见的有以下两种方式。

1.队列式(FIFO)分支限界法：队列先进先出的原则。

2.优先式队列分支限界法：p值较小优先级较高，最小费用优先的原则。

代码部分

这里目前还不明白，P183，老师说while里的很重要

这里也是，P186，while里面比较重要

七随机化算法

计算Π值的随机投点法

//按面积在圆里概率等于Π/4，投中圈内的点/总投点次数应该等于Π/4
double Darts(int n){
    static RandomNumber dart;    //随机投点的对象
    int k=0;    //开始在圆里的点只有0个,k=0
    for(int i-1;i<n;i++){    //随机投n个点
        double x=dart.fRandom();    随机x
        double y=dart.fRandom();    随机y
        if((x*x+y*y)<=1)    投中在1/4圆里，计数加一
            k++; 
    }
    return 4*k/double(n);    
}

计算定积分

double Darts(int n){
    static RandomNumber dart;
    int k=0;
    for(int i=1;i<=n;i++){
        double x=dart.fRandom();
        double y=dart.fRandom();
        if(y<=f(x))    //点在灰色区域
            k++;
    }
    return k/double(n);
}

主元素问题

之前写过笔记

主元素问题（蒙特卡罗方法）笔记-CSDN博客

RandomNumber rnd;
bool Majority(char *T,int n){
    int i=rnd.Random(n)+1;
    char x=T[i];
    int k=0;
    for(int j=1;j<=n;j++)
        if(T[j]==x)
            k++;
    return (k>n/2);
}