精华内容
下载资源
问答
  • 回溯法时间复杂度分析
    2022-09-05 22:42:25

    一、实验目的

            (1)理解回溯法的求解过程。

    (2)分析回溯法的时间复杂度,比较回溯法算法与其他算法的时间效率差异。

    (3)学会如何利用回溯法求解具体问题,了解动回溯法的应用范围及在实际应用中的局限性。

    二、实验任务

            (1)分析实验7.1中算法的时间复杂度。

    (2)采用动态规划算法求解实验7.1中的问题,分析其算法时间复杂度。

    (3)分析比较(1)和(2)两种算法的特点及适用范围。

    (4)实验比较回溯法及动态规划算法程序的运行时间与城市数量之间的关系,并与前面的分析结果进行比较。

    (5)撰写相应的实验报告,实验报告内容包括:实验目的、实验任务、实验环境、实验步骤、实验结果及其分析以及实验总结等部分内容。

    更多相关内容
  • 回溯法求解N皇后问题及其时间复杂度分析

    万次阅读 多人点赞 2020-07-02 21:33:49
    回溯法求解N皇后问题及其时间复杂度分析一、回溯法简介1. 什么是回溯法?2. 回溯法时间复杂度分析蒙特卡罗方法蒙特卡罗方法在回溯法求解时间复杂度中的应用二、回溯法求解N皇后问题1. 回溯法求解N皇后问题的过程2....

    一、回溯法简介

    1. 什么是回溯法?

      相信"迷宫"是许多人儿时的回忆,大家小时候一定都玩过迷宫游戏。我们从不用别人教导,都知道走迷宫的策略是:

    1. 当遇到一个岔路口,会有以下两种情况:
      1. 存在没走过的路。此时可以任意选一条没走过的路深入,只要记住我们所走过的路径即可。倘若下次再来到这个路口,便不再沿着走过的路径继续深入,而是沿着没走过的路径深入下去;
      2. 所有路都已经走过。如果所有岔路口都已经遍历,则回退至上一个最近的岔路口。
    2. 当遇到死胡同,便回退到刚才距离最近的岔路口。
    3. 不断前进并重复该过程,直到找到终点或回退到起点位置。

      其实,这就是回溯法——一个基于深度优先搜索和约束函数的问题求解方法。

    2. 回溯法的时间复杂度分析

      众所周知,回溯法的时间复杂度主要取决于如下几点:

    1. 生成每个节点x[k](x[k]表示第k层的当前节点)所用的时间。
    2. 满足约束函数(用约束函数剪去得不到可行解的子树)的x[k]值的个数(第k层有可能生成几个这样的节点)。
    3. 计算约束函数Constraint对节点进行判断的时间。
    4. 计算上界(限界)函数Bound的时间。
    5. 满足约束函数和限界函数的所有节点x[k]的个数。

      当问题和算法一旦确定下来,就只剩下第5点的实际产生的节点数目是根据问题的具体实例而动态生成,不可预知的。
      对于一个具体的问题实例,很难预测出回溯法的行为(先选哪一条岔路,这条岔路是否能很快得到最优解),这时应该怎么办呢?

    蒙特卡罗方法

      此时,可以使用蒙特卡罗方法估计回溯法产生的节点数目。
      所谓蒙特卡罗方法,其实就是一种以概率统计理论为指导的,使用随机数(或伪随机数)来解决计算问题的方法,通过对大量随机试验求平均,以求得相近的值。
      蒙特卡罗方法的基本思想是:当求解的问题是某种随机事件出现的概率或数学期望时,通过大量“实验”的方法,以频率估计概率或者得到某些数字特征,将其近似看作问题的解。
      1777年,法国数学家布丰(Buffon)提出使用投针试验的方法求解圆周率π,这被认为是蒙特卡罗方法的起源(扯远了)。

    蒙特卡罗方法在回溯法求解时间复杂度中的应用

      我们需要估计的是回溯法实际产生的节点数目,以此计算回溯法的时间复杂度。
      其主要思想是,在解空间树(状态空间树)上动态、随机的产生一条路径,然后沿此路径来估算解空间树中所有满足约束条件的节点总数(这里计算的是最差时间复杂度,假设要走遍所有满足约束条件的节点)。
      多次进行上述实验,对结果求平均值,即可得到回溯法中实际生成的节点数目的估计值。

    二、回溯法求解N皇后问题

    1. 回溯法求解N皇后问题的过程

      问题背景:8皇后问题是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题,是回溯算法的典型案例。N皇后问题由此推广而来。
      问题描述:在N×N格的国际象棋上摆放N个皇后,使其不能互相攻击,即不能处于同一列或同一行,也不能处在同一斜线上,请问有多少种摆法?
    8皇后问题

      N皇后问题也是回溯算法的典型案例,这里,我们可以使用递归和循环迭代两种不同的回溯方式编写代码:

    //
    //  main.cpp
    //  BackTrack Solution of N-Queens Problem.
    //
    //  Created by Kang on 2020/7/2 at NJUPT.
    //  Copyright © 2020 Kang. All rights reserved.
    //
    
    #include <iostream>
    #include <cmath>
    #include <ctime>
    using namespace std;
    
    const int maxSize = 10;
    int x[maxSize];
    
    /**
     Judge if the Queen can be placed at (k, x[k]), if OK, return true.
     */
    bool CanPlace(int k){
        for(int i = 0; i < k; ++i) {
            if(x[i] == x[k] || abs(i-k) == abs(x[i]-x[k]))
                return false;
        }
        return true;
    }
    
    void Print(int N){
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if(x[i] != j) {
                    printf(" ");
                } else {
                    printf("▇\n");
                    break;
                }
            }
        }
        printf("---------\n");
    }
    
    /**
     k the current deepth( from 0 to n-1) in the Solution Space Tree
     */
    int Recursive_BackTrack(int k, int N){
        int solutionCount = 0;
        
        if(k == N){
            Print(N);
            return 1;
        }
        
        for (int i = 0; i < N; ++i) {
            x[k] = i;
            if(CanPlace(k)){
                solutionCount += Recursive_BackTrack(k+1, N);
            }
        }
        return solutionCount;
    }
    
    int Iterated_BackTrack(int N){
        int solutionCount = 0, k = 0;       // 问题解的个数、当前层数
        
        for (int i = 0; i < maxSize; ++i) { // 将所有层中,所选子树(列)的初始值置为-1
            x[i] = -1;
        }
        
        while (k > -1) {     // 如果已经退回第0行前面,则结束遍历
            if(k == N){      // 如果已经超过最后一行,则打印路径并返回上一层
                Print(N);
                ++solutionCount;
                --k;
                continue;
            }
            
            if(++x[k] < N){  // 如果还有未访问的子节点,则选择这棵树的下一个子树
                if(CanPlace(k)){
                    ++k;     // 如果当前位置可以摆放,则k自增,进入下一行的循环。
                } else {
                             // 如果当前位置不能摆放,则k不必动,直接进入下次循环。
                }
            } else {         // 子树已经全部搜索,返回上一层
                x[k] = -1;   // 注意,返回时要将子树进行复位。
                --k;
            }
        }
        
        return solutionCount;
    }
    
    int main(int argc, const char * argv[]) {
        int N;
        int count;
        
        printf("请输入皇后个数:");
        scanf("%d", &N);
        
        // count = Recursive_BackTrack(0, N);
        count = Iterated_BackTrack(N);
        
        cout<<"共有"<<count<<"种不同的解法。"<<endl;
        return 0;
    }
    

      笔者在写博客的过程中发现了可以优化的地方,于是赶快去修改了一下。不知道各位读者有没有发现,各位可以仔细对比以下两份不同的代码,答案将在这份代码后面给出。

    //
    //  optimisedMain.cpp
    //  Optimised BackTrack Solution of N-Queens Problem.
    //
    //  Created by Kang on 2020/7/2 at NJUPT.
    //  Copyright © 2020 Kang. All rights reserved.
    //
    
    #include <iostream>
    #include <cmath>
    #include <ctime>
    using namespace std;
    
    const int maxSize = 10;      // 最大能输入的棋盘规模(皇后数量)
    int x[maxSize];              // x[k]表示:第k行选择第x[k]列
    int flag[maxSize][maxSize];  // flag[k][i]:第k行的第i列如果可选则为1,不可选则为0
    
    /**
     Calculate the kth row's all unalternative column i, and turn flag[i] from 1 to 0.
     */
    void calcFlag(int k, int N){
        for (int i = 0; i < N; ++i) {
            flag[k][i] = 1;
        }
        
        for(int i = 0; i < k; ++i) { // from 0th to (k-1)th row
            flag[k][x[i]] = 0;  // 正对下方的列直接Pass
            
            if(x[i] + abs(i-k) < N)   // 检查右下方:如果当前列号x[i] + 行差abs(i-k) < N
                flag[k][x[i] + abs(i-k)] = 0;
            if (x[i] - abs(i-k) > -1) // 检查左下方:如果当前列号x[i] + 行差abs(i-k) < N
                flag[k][x[i] - abs(i-k)] = 0;
        }
    }
    
    void Print(int N){
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if(x[i] != j) {
                    printf(" ");
                } else {
                    printf("▇\n");
                    break;
                }
            }
        }
        printf("---------\n");
    }
    
    /**
     k the current deepth( from 0 to n-1) in the Solution Space Tree
     N the scale of the problem
     return number of solution
     */
    int Recursive_BackTrack(int k, int N){
        int solutionCount = 0;
        
        if(k == N){
            Print(N);
            return 1;
        }
        
        calcFlag(k, N);
        for (int i = 0; i < N; ++i) {
            if(flag[k][i]) {
                x[k] = i;
                solutionCount += Recursive_BackTrack(k+1, N);
            }
        }
        return solutionCount;
    }
    
    /**
     N the scale of the problem
     return number of solution
    */
    int Iterated_BackTrack(int N){
        int solutionCount = 0, k = 0;       // 问题解的个数、当前层数
        
        for (int i = 0; i < maxSize; ++i) { // 将所有层中,所选子树(列)的初始值置为-1
            x[i] = -1;
        }
        
        calcFlag(0, N);
        while (k > -1) {     // 如果已经退回第0行前面,则结束遍历
            if(k == N){      // 如果已经超过最后一行,则打印路径并返回上一层
                Print(N);
                ++solutionCount;
                --k;
                continue;
            }
            
            if(++x[k] < N){  // 如果还有未访问的子节点,则选择这棵树的下一个子树
                if (flag[k][x[k]] == 1) {
                    ++k;     // 如果当前列x[k]可以摆放,则k自增,进入下一行的循环。
                    calcFlag(k, N);
                } else {
                             // 如果当前位置不能摆放,则k不必动,直接进入下次循环。
                }
            } else {         // 子树已经全部搜索,返回上一层
                x[k--] = -1;   // 注意,返回时要将子树进行复位。
            }
        }
        
        return solutionCount;
    }
    
    int main(int argc, const char * argv[]) {
        int N;
        int count;
        
        printf("请输入皇后个数:");
        scanf("%d", &N);
        
        //count = Recursive_BackTrack(0, N);
        count = Iterated_BackTrack(N);
        
        cout<<"共有"<<count<<"种不同的解法。"<<endl;
        return 0;
    }
    

      Answer:这其实是一种添加辅助数组flag,从而牺牲空间复杂度O(n2),减小时间复杂度n倍的策略。这样,每一个位置判断是否可以摆放,只需要O(1)的时间复杂度,而非前者O(n)的时间复杂度(以下计算时间复杂度时,均采用的是后者的求解方式)。

    2. 回溯法求解N皇后问题的时间复杂度

      根据前面所讲到的蒙特卡罗方法,此时可以将其用于求解N皇后的时间复杂度。对于n元组长度的问题实例,其状态空间树中的节点数目常见的有n!(排列树)、an(子集树)和nn(可复选的排列树),则回溯算法的最坏时间复杂度分别为:

    • O(p(n) * n!)
    • O(p(n) * 2n)
    • O(p(n) * nn)

    其中,p(n)表示生成一个节点所需的时间复杂度。

      虽然回溯法的最坏时间复杂度非常的大,但是在大多数情况下,通常不需要生成状态空间树中的全部节点,而是通过约束函数限界函数进行剪枝,从而最终只生成状态空间树中很少量的一部分节点,这里,我们就使用N皇后问题来举例,利用蒙特卡罗方法估算一下算法运行中实际生成的节点占状态空间树中总节点的比例

    2.1 求解时的效率分析

      在求解时间复杂度之前,先分析一下回溯法的效率。回溯法的运行时间通常取决于状态空间树上实际生成的那部分节点的数目。
      在n皇后问题中,状态空间树(排列树)中总的节点个数为(如图为4皇后问题的完整的解空间树,共有65个节点):

    • 1+n+(n-1)+(n-2)+ ······ +[n-(n-2)]+[n-(n-1)]

    在这里插入图片描述

    而实际生成的节点数的个数怎么计算呢?
    不妨对4-皇后问题先演算一下~
    在这里插入图片描述
    计算得到4皇后问题实际生成的节点数为16个,只生成了 (16/65)*100% = 24.6% 的节点。

      但实际上,我们在通常的问题中无法预知要从哪一条岔路开始搜索解(这里很简单我们从0位置开始向后),而且有的时候我们要求出所有符合条件的解,这就要求我们将状态空间树中所有符合剪枝函数的点全部计算进来

      如果要计算实际生成的节点数,那么问题来了:

    1. 当我遇到岔路的时候,会随机走一条路,请问我走了哪条路?
    2. 我也是走一步之后,才知道下一步的有几个岔路或者是否是死胡同。

      这时,蒙特卡罗方法就派上用场了。既然我们不清楚要生成多少节点,那我们不妨进行若干次的试验,然后求平均:每次随机生成一条路径,根据这条路径的情况来草率的推断所有其他路径和这条路一样,从而草率的估计实际生成的节点数量。
      很显然,对于8皇后来说,第一行选第0个位置和选第1个位置,从而造成的第2行所能选择的范围都不一样,所以说是“草率的”估计。
      但是这么草率的估计是否严谨呢?单单试验一次,恐怕并不严谨。但是,如果我们进行大量的试验,然后对这一整批实验数据求平均,从概率论上来说,试验次数越多,结果越准确(例如,投硬币次数越多,正面朝上的频率越稳定于实际的概率0.5)。

      那我们不妨就用实际的栗子,来对8皇后问题进行一个“草率的”估计。这里简单的用(a)图进行举例:

    • 根节点1个(假定为状态空间树的第0行);
    • 第一行可以有8种选择(0, 1, 2, 3, 4, 5, 6, 7),所以状态空间树的第1行有8个节点。此时,假设我们随机选择了当前可行的1号位置;
    • 在第一行的基础上,我们有5种选择(3, 4, 5, 6, 7),这时可以“草率的”假设:对于每一种第一行的可行的选择(8种),我们在第二行都有5种不同的选择,所以状态空间树的第二行我们可以生成8*5个节点。此时,假设我们随机选择了当前可行的3号位置;
    • 在前两行的基础上,我们有4种选择(0, 5, 6, 7),这时可以“草率的”假设:对于每一种前两行的可行排列(8*5=40),我们在第三行都有4种不同的选择,所以状态空间树的第三行有8*5*4个节点。此时,假设我们随机选择了当前可行的0号位置;
    • 在前三行的基础上,我们有3种选择(2, 6, 7),这时可以“草率的”假设:对于每一种前三行的可行排列(8*5*4=160),我们在第四行都有3种不同的选择,所以状态空间树的第4行有8*5*4*3=480个节点。此时,假设我们随机选择了当前可行的2号位置;
    • 在前四行的基础上,我们有2种选择(4, 7),这时可以“草率的”假设:对于每一种前四行的可行排列(8*5*4*3=480),我们在第四行都有3种不同的选择,所以状态空间树的第5行有480*2=480个节点。此时,假设我们随机选择了当前可行的4号位置;
    • 在前五行的基础上,我们已经没有任何选择了,所以我们“草率的”假设,其他所有的路径都和这条路径一样,都无法继续选择了,所以状态空间树从第6行开始不再实际产生节点。

      因此,我们“草率的”估计,此次随机试验,解空间树中实际产生的节点数量有1+8+8*5+8*5*4+8*5*4*3+8*5*4*3*2 = 1649个,占总节点数8!/8!+8!/7!+8!/6!+······+8!/2!+8!/1!+8!/0!=109601的1.55%在这里插入图片描述
      此时,我们是否可以说回溯法一定就实际生成1.55%的节点数呢?答案是否定的。我们需要尽可能的做多次这样的随机试验(例如b、c、d、e等图),然后求出平均值,才是较为准确的实际生成的节点占比。(其他几个图随机的路径也是一样的道理,笔者此处不再赘述。)

    回溯法进行效率分析的代码

      此处贴上本人手写的代码一份,可以用于测试实际生成的节点与状态空间树中总结点的占比,有疑问欢迎私信。

    //
    //  rate.cpp
    //  Efficiency Analysis of BackTrack for N-Queens Problem.
    //
    //  Created by Kang on 2020/7/2 at NJUPT.
    //  Copyright © 2020 Kang. All rights reserved.
    //
    
    #include <iostream>
    #include <cmath>
    #include <ctime>
    using namespace std;
    
    const int testCount = 100; // 测试次数
    const int MAXN = 20;       // 能测试的皇后最大值
    int countPerRow[MAXN];     // 存放每行能选列的个数,便于最终计算结果
    int bucket[MAXN];          // 符合约束能选则为1,不符合约束不能选则为0
    int x[MAXN];               // 存放生成的随机序列
    int N;                     // 本次是N皇后求解
    
    // 初始化临时标记是否是可选的列
    // 每行的判定开始前,都需要调用,假定该行的每一列都不能选
    void initBucket(){
        for(int i = 0; i < MAXN; ++i) {
            bucket[i] = 0;
        }
    }
    
    // 初始化每行能选的列数,每次试验开始前调用,进行置零
    void initCountPerRow(){    
        for(int i = 0; i < MAXN; ++i) {
            countPerRow[i] = 0;
        }
    }
    
    
    bool CanPlace(int k) {   // 判断第k行第x[k]列能不能放
        for (int i = 0; i < k; ++i) {
            if (x[i] == x[k] || abs(i - k) == abs(x[i] - x[k]))   // 是否下面和斜对角有重合
                return false;
        }
        return true;
    }
    
    // 返回能够抵达的行数
    int RecurBacktrackM(int t) {
        initBucket();
        if (t == N) {            // 如果已经进入第N+1行,则找到解
            return t;
    
        } else {
            int colCount = 0;    // 能摆放几列
            int randInt, r = 0;  // 随机第几个能摆放的位置
            int index = 0;       // 摆放的位置的下标
            for (int i = 0; i < N; ++i) {      // 挨个试探
                x[t] = i;
                if (CanPlace(t)) {             // 判断是否能放
                    bucket[i] = 1;
                    colCount++;
                    countPerRow[t]++;          // 第t行实际产生的可行解数量++
                }
            }
    
            if(colCount > 0) {                 // 如果这一行有可行解
                randInt = rand()%colCount + 1;
                while(r < randInt){
                    if(bucket[index] == 1){
                        r++;
                    }
                    index++;
                }
                index--;
                x[t] = index;                 // 得到随机选择的可行解的列号
                return RecurBacktrackM(t + 1);// 进入下一层
            } else {                          // 不能放说明是死胡同,直接返回
                return t;
            }
        }
    }
    
    int main() {
        srand((unsigned)time(NULL));
        cout<<"请输入棋盘的大小:";
        cin>>N;
    
        double allRate = 0;
        for(int number = 0; number < testCount; number++){
            int row, allNodeCount = 1;
            int geneNodeCount = 1;   // 蒙特卡洛估计的,实际产生的节点的数量
            initCountPerRow();
            row = RecurBacktrackM(0);
    
            cout<<"本次实验的随机序列是:";
            for(int i = 0; i < row; i++){
                cout<<x[i]<<" ";
            }
            cout<<endl;
    
            int tmp;
    
            cout<<"本次实验的每行节点数分别是:";
            for(int i = 0; i < row; i++){
                cout<<countPerRow[i]<<" ";
            }
            cout<<endl;
            for(int i = 0; i < row; i++) {
                tmp = 1;
                for(int j = 0; j <= i; j++) {
                    tmp *= countPerRow[j];
                }
                geneNodeCount += tmp;
            }
            cout<<"本次估计实际产生的节点数是:"<<geneNodeCount<<endl;
            
            for(int i = 0; i < N; i++) {
                tmp = 1;
                for(int j = 0; j <= i; j++) {
                    tmp *= N-j;
                }
                allNodeCount += tmp;
            }
            cout<<"    状态空间树中的总节点数是:"<<allNodeCount<<endl;
            cout<<"    实际生成节点数目与总节点数比值为:"<<((geneNodeCount * 1.0)/allNodeCount)*100<<"%"<<endl;
            allRate += (geneNodeCount * 1.0)/allNodeCount;
            cout<<"-----------------------------------------------"<<endl;
        }
        
        cout<<"此"<<testCount<<"次实验,平均实际生成节点数目与总节点数比值为:"<<(allRate/testCount)*100<<"%"<<endl;
    
        return 0;
    }
    

    运行1000次8皇后问题的试验,效果截图如下:
    在这里插入图片描述

    2.2 时间复杂度分析

      在N皇后问题中,因为每个节点(最下一层除外)都要遍历包括当前层在内的上面每一层的选择,才能得到当前可行的全部直接子孙节点,且绝大多数节点都集中在层数靠下的位置,故可以估计出平均每个节点的生成时间复杂度p(n)都是n。
      例如上例中,根节点生成时要检验它的8个真子孙节点是否可行;对于第一层的每一个节点,也都需要判断其全部的8个真子孙节点是否可行;第二层、第三层······直到倒数第二层,也都需要判断其全部的8个真子孙节点是否可行;最后一层虽比较特殊,无需判断,但最后一层(已经抵达可行解)的节点在N皇后问题(排列树)中和上一层的节点数相同,故与其他节点一视同仁也不影响时间复杂度的计算。
      所以N皇后的时间复杂度为O(n×实际生成的节点数)。

      凑巧赶上小破邮的算法课程,于是写下人生中第一篇正式的CSDN博客,竟然啰嗦了1w多字,希望大家多多点赞支持,有疑问的地方欢迎私信小博同学进行交流奥~

    展开全文
  • 对一个实际的背包问题,分别采用动态规划法和回溯法,以动态图ppt的形式生动形象地展示这两种算法的原理和求解过程
  • 【图的m着色问题】“回溯法”——《算法设计与分析(第五版)》


    一、算法要求

    给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色。是否有一种着色法,使G中每条边的2个顶点着有不同颜色?这个问题是图的m可着色判定问题。
    若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色,则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。
    如果一个图的所有顶点和边都能用某种方式画在平面上且没有任何两边相交,则称这个图是可平面图。著名的平面图的四色猜想是图的m可着色性判定问题的特殊情形。

    1. 思路

    如果我们把地图上的每一个区域退化成一个点,相邻的区域用连线连接起来,那么地图就变成了一个无向连通图,我们给地图着色就相当于给该无向连通图的每个点着色,要求有连线的点不能有相同颜色。这就是经典的图的m着色问题。给定无向连通图G和m种颜色,找出所有不同的着色方案,使相邻的区域有不同的颜色。
    假设地图一共有7个区域,分别是A、B、C、D、E、F、G,我们现在按上面顺序进行编号1~7,每个区域用一个结点表示,相邻的区域有连线。那么地图就转化成了一个无向连通图。
    在这里插入图片描述


    二、完整代码

    1. 主文件

    main.cpp:

    // Project4: 着色问题
    #include <iostream>
    #include <cstring>
    #include <iomanip>
    using namespace std;
    
    const int numMax = 50,
    		n = 7,
    		m = 3,
    		edge = 12;
    int sum = 0;//记录解的个数
    int x[numMax],//解分量
    map[numMax][numMax],//图的邻接矩阵
    simple[12][2] = { {1,2},{1,3},{1,4},{2,3},{2,5},{3,4},
    				{3,5},{4,5},{4,7},{5,6},{5,7},{6,7} };
    
    void CreatMap() {
    	int u, v;
    	memset(map, 0, sizeof(map));//邻接矩阵里面的数据初始化为0,
    	for (int i = 0; i < edge; i++){
    		u = simple[i][0];
    		v = simple[i][1];
    		map[u][v] = map[v][u] = 1;
    	}
    	int nn = 0;
    	for (int i = 0; i < edge; i++) {
    		for (int j = 0; j < edge; j++) {
    			if (map[i][j] != 0) {
    				cout << i << "-" << j << "|";
    				nn++;
    				if (nn % 6 == 0) {
    					cout << endl;
    				}
    			}
    		}
    	}
    }
    
    bool Coloring(int t) {
    	for (int j = 1; j < t; j++) {
    		if (map[t][j]) {
    			//如果t与j邻接
    			if (x[j] == x[t])//着色号是否相同
    				return false;
    		}
    	}
    	return true;
    }
    
    void Backtrack(int t) {
    	if (t > n) { //成功
    		sum++;
    		cout << "#No." << sum << ": ";
    		for (int i = 1; i <= n; i++)//输出该着色方案
    			cout << setw(3) << x[i];
    		cout << endl;
    	}
    	else {
    		for (int i = 1; i <= m; i++) {//每个结点尝试m种颜色
    			x[t] = i;
    			if (Coloring(t))
    				Backtrack(t + 1);
    		}
    	}
    }
    
    int main() {
    	cout << "#Number of nodes: " << setw(3) << n << endl;
    	cout << "#Number of colors:" << setw(3) << m << endl;
    	cout << "#The following is the adjacency of the undirected graph: " << endl;
    	CreatMap();
    	cout << "\n#Possible methods include:"<< endl;
    	Backtrack(1);
    }
    

    2. 效果展示

    输入:
    在这里插入图片描述
    输出:
    在这里插入图片描述


    三、补充

    算法复杂度分析:
    (1)时间复杂度
    最坏情况下,除了最后一层外,有1+m+m2+…+mn-1=(mn-1)(m-1)~mn-1个结点需要扩展,而这些结点每个都要扩展m个分支,总的分支个数为mn,每个分支都判断约束函数,判断约束条件需要O(n)的时间,因此耗时O(nmn)。在叶子结点处输出可行解需要耗时O(n),在最坏情况下回搜索到每一个叶子结点,叶子个数为mn,故耗时为O(nmn)。因此,时间复杂度为O(nmn)。
    (2)空间复杂度
    回溯法的另一个重要特性就是在搜索执行的同时产生解空间。在所搜过程中的任何时刻,仅保留从开始结点到当前扩展结点的路径,从开始结点起最长的路径为n。程序中我们使用x[]数组记录该最长路径作为可行解,所以该算法的空间复杂度为O(n)。

    文档供本人学习笔记使用,仅供参考。

    展开全文
  • 也就是时间复杂度分析方法。T(n)表示算法的执行时间,n表示数据规模。随着规模n的增大,算法执行时间的增长率和f(n)的增长率相同。叫做算法的渐进时间复杂度,简称时间复杂度。大O表示算法的执行时间T(n)与f...

    一、算法效率度量

    如何度量一个算法的执行效率/时间呢?可以利用计算机的计时功能,来度量算法执行效率高低。这种方法也叫事后统计法

    事后统计法有很大的局限性:

    1. 测试结果依赖环境:不同的处理器、不同的操作系统等都会影响测试结果;即使是同一台物理机,Cpu使用率不一样也测试结果也可能不同。
    2. 测试结果受数据规模大小影响:数据规模的大小,直接决定了程序的运行时间。

    通常分析一个算法效率优劣,不需要计算出具体的执行时间,而是粗略的预估算法的时间效率

    也就是时间复杂度分析方法。

    二、时间复杂度

    T(n) = O(f(n))

    T(n)表示算法的执行时间,n表示数据规模。随着规模n的增大,算法执行时间的增长率和f(n)的增长率相同。叫做算法的渐进时间复杂度,简称时间复杂度。

    大O表示算法的执行时间T(n)与f(n)成正比。

    如何理解时间复杂度

    1. 它表示代码的执行时间随数据规模的增长趋势,不是具体的执行时间。
    2. 通常只是表示数据规模n很大时候的执行效率

    如何计算时间复杂度

    1. 忽略常量、低阶、系数,只保留最高量级。
    2. 总得时间复杂度等于量级最大的那段代码的时间复杂度。
    3. 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

    几种常见的时间复杂度

    1. O(1)常量级:哈希表上的各种操作
    2. O(logn)对数级:二分查找、调表
    3. O(n)线性:数组、链表的遍历
    4. O(nlogn)快速排序、归并排序
    5. O(n^2)冒泡、插入、选择排序
    6. O(2^n)指数级:回溯穷举算法,例如八皇后问题
    7. O(n!):求全排列

    最好、最坏、平均时间复杂度

    例如:在一个数组中,找到值等于X的数据。我们需要遍历数组,依次每个元素equas寻找X。

    1、最好情况的时间复杂度就是O(1)。(接口的最小响应时间)

    2、最坏情况时间复杂度O(n)。(接口的最大响应时间)

    3、平均时间复杂度: O(n)。(接口平均响应时间)

    大多数情况下,平均时间复杂度,就是最差情况的时间复杂度。

    4、均摊时间复杂度:是一种特殊的平均时间复杂度。常见的就是支持动态扩容的一些数据结构。

    对一个数据结构进行一组连续操作中,大部分情况下时间复杂度都很低,只有个别情况下时间复杂度比较高,而且这些操作之间存在前后连贯的时序关系。

    摊还分析法:这个时候,我们就可以将这一组操作放在一块儿分析,看是否能将较高时间复杂度那次操作的耗时,平摊到其他那些时间复杂度比较低的操作上。

    在能够应用均摊时间复杂度分析的场合,一般均摊时间复杂度就等于最好情况时间复杂度。

    三、空间复杂度

    空间复杂度,是度量算法运行过程占用的存储空间,通常使用S(n)表示,n表示问题的规模。

    S(n) = O(f(n))

    常见的空间复杂度:O(1)、O(n)

    1. 空间复杂度 O(1)

    代码中m、n所分配的空间都是常量级的,记作O(1)

    int m = 1;
    int n = 2;
    
    1. 空间复杂度 O(n)
      代码中使用array数组保存变量,随着n的增大,数组所占用的内存也随之增加。记作O(n)
    int[] array = new int[n]
    for(i=0; i<n; ++i)
    {
       array[i] = i;
    }
    
    展开全文
  • leetcode刷题总结之回溯法

    千次阅读 2019-11-27 22:02:44
    回溯法是看labuladong的详解回溯法入的门,然后看了《计算机算法设计与分析》第5章的回溯法部分弄清了原理,今日总结一下,供以后复习用。 回溯法的定义: 回溯法有通用解法的美称,对于很多问题,如迷宫等都有很好...
  • 回溯算法性能分析

    2021-05-21 17:34:47
    「关于回溯算法的复杂度分析在网上的资料鱼龙混杂,一些所谓的经典面试书籍不讲回溯算法,算法书籍对这块也避而不谈,感觉就像是算法里模糊的边界」。 「所以这块就说一说我个人理解,对内容持开放态度,集思广益,...
  • 【n后问题】“回溯法”——《算法设计与分析(第五版)》
  • 复杂度分析 时间复杂度:O(N!),其中 N 是皇后数量。 空间复杂度:O(N),其中 N 是皇后数量。空间复杂度主要取决于递归调用层数、记录每行放置的皇后的列下标的数组以及三个集合,递归调用层数不会超过 N,数组的...
  • 旅行售货员问题 1.问题描述: 旅行售货员问题又称TSP问题,问题如下:某售货员要到若干个城市推销商品,已知各城市之间的路程(或旅费),他要选定一条从驻地出发,经过每个城市一遍最后回到驻地的路线,使总的路线...
  • ===== 本文算法的时空复杂度都未达到最优,核心目的在于展现并理解回溯法的算法过程。===== 0-1背包问题 给定 nnn 种物品和一个背包。物品 iii 的重量为 wiw_iwi​,其价值为 pip_ipi​,背包的容积为 ccc。问如何...
  • (5) 分析算法的时间复杂度。 (6) 分别以Word文档和pdf方式提交,并打包压缩后以.rar文件提交。 题目1:数独游戏是在9*9的方格中填放1~9的数字,要求每一行、每一列以及3*3的方格中的数字均不能相同,如下图所示...
  • 2. 分析回溯法时间复杂度,比较回溯法算法与其他算法的时间效率差异。 3. 学会如何利用回溯法求解具体问题,了解动回溯法的应用范围及在实际应用中的局限性 1. 写出采用回溯法求解.上述问题的目标函数,约束条件...
  • 01背包问题(回溯算法实现)

    千次阅读 2021-01-17 12:52:29
    所谓01背包,表示每一个物品只有一个,要么装入,要么不装入。...回溯法是最近学的,所以试着用C语言将其实现了下,下面作以分析,后期将会继续用其他两种算法实现01背包问题,并做比较。回溯法:01背包属于找最优...
  • 旅行售货员--回溯法

    2021-12-21 14:36:03
    在递归算法Backtrack 中,当i=n时,当前扩展结点是排列树的叶结点的父结点。此时 算法检测图G是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点...时间复杂度:O(n!) matrix = [ [0, 1, 2, 3], [1, 0, 6, 8], .
  • 文章目录TSP问题描述回溯法解tsp问题(深度优先)代码基站数据运行结果分支限界法解tsp问题(广度优先)代码运行结果结果分析 TSP问题描述 旅行商从驻地出发,经过每个需要访问的城市一次且只有一次,并最终返回出发...
  • 回溯法 采用试错的思想,它尝试分步的去解决一个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答...
  • 最近,有不少读者留言或私信问我时间复杂度分析方法。时间复杂度说难也不难,说简单也不简单,但它一定是我们学习算法的过程中过不去的一道坎。这篇文章就想给大家介绍一种快速分析时间复杂度的方法...
  • 动态规划(dp) 01背包问题的动态规划解法递归方程为: 当 j &...此时时间复杂度为O(n) 回溯法 使用回溯法解决01背包问题时,若可选物品为n个,则其解空间由长度为n的0-1向量组成~ 此时时...
  • N皇后问题 - 回溯法

    2022-05-07 15:41:56
    学习回溯法和dfs, N皇后是一个经典问题。 力扣上是这莫描述的: n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上, 并且使皇后彼此之间不能相互攻击。 给你一个整数 n ,返回 n 皇后问题 不同的解决方案...
  • 回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为...
  • 时间复杂度 请原谅我也是一个标题党!关于时间复杂度和空间复杂度分析的文章其实不少,但大多数都充斥着复杂的数学计算,让很多读者感到困惑,我就不跟大家扯皮了,关于什么是渐近分析、最坏时间复杂...
  • 在n*n的迷宫里,因为需要遍历所有的点,时间复杂度就是O(n*n)。 递归结果 回溯求解 2.1回溯 回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”...
  • 回溯法求解01背包问题

    千次阅读 2017-07-14 16:03:10
    问题描述在前面文章...接下来我们就使用回溯法来求解这个问题,其时间复杂度为O(n2n)O(n2^n),这个结果当我们的c的值是小于2n2^n的时候,该算法所需的时间是小
  • 回溯法 之 素数环

    千次阅读 2016-12-11 02:21:31
    (探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯...
  • 0-1背包_回溯算法

    2013-12-18 10:09:16
    0-1背包_回溯算法,VC++全程编写,结构体,易学易用
  • 回溯法之子集和问题

    千次阅读 2020-05-24 15:57:28
    典型的回溯法,解空间为子集树。这道题与0-1背包问题非常相似,可以将其理解为有权重的0-1背包问题。只不过是把0-1背包问题中的1表示为具体数字大小,0依然是0,表示不在子集和中。所以这个问题的解空间也是一个子集...
  • 回溯法与分支界限算法的思想、解题步骤、重要概念

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,631
精华内容 4,652
热门标签
关键字:

回溯法时间复杂度分析