精华内容
下载资源
问答
  • 五大常用算法&实例列举

    千次阅读 2016-09-14 01:16:49
  • 分治算法(divide and conquer)是五大常用算法(分治算法、动态规划算法、贪心算法、回溯法、分治界限法)之一,很多人在平时学习中可能只是知道分治算法,但是可能并没有系统的学习分治算法,本篇就带你较为全面的去...

    原创公众号:bigsai
    文章收录在 bigsai-algorithm 求个star

    前言

    分治算法(divide and conquer)是五大常用算法(分治算法、动态规划算法、贪心算法、回溯法、分治界限法)之一,很多人在平时学习中可能只是知道分治算法,但是可能并没有系统的学习分治算法,本篇就带你较为全面的去认识和了解分治算法。

    在学习分治算法之前,问你一个问题,相信大家小时候都有存钱罐的经历,父母亲人如果给钱都会往自己的宝藏中存钱,我们每隔一段时间都会清点清点钱。但是一堆钱让你处理起来你可能觉得很复杂,因为数据相对于大脑有点庞大了,并且很容易算错,你可能会将它先分成几个小份算,然后再叠加起来计算总和就获得这堆钱的总数了

    image-20201130124009617

    当然如果你觉得各个部分钱数量还是太大,你依然可以进行划分然后合并,我们之所以这么多是因为:

    • 计算每个小堆钱的方式和计算最大堆钱的方式是相同的(区别在于体量上)
    • 然后大堆钱总和其实就是小堆钱结果之和。这样其实就有一种分治的思想。

    当然这些钱都是想出来的……

    BACDB95DF648E67CF0576A009697EBD2

    分治算法介绍

    分治算法是用了分治思想的一种算法,什么是分治

    分治,字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。在计算机科学中,分治法就是运用分治思想的一种很重要的算法。分治法是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)等等。

    将父问题分解为子问题同等方式求解,这和递归的概念很吻合,所以在分治算法通常以递归的方式实现(当然也有非递归的实现方式)。分治算法的描述从字面上也很容易理解,分、治其实还有个合并的过程:

    • 分(Divide):递归解决较小的问题(到终止层或者可以解决的时候停下)
    • 治(Conquer):递归求解,如果问题够小直接求解。
    • 合并(Combine):将子问题的解构建父类问题

    一般分治算法在正文中分解为两个即以上的递归调用,并且子类问题一般是不想交的(互不影响)。当求解一个问题规模很大很难直接求解,但是规模较小的时候问题很容易求解并且这个问题并且问题满足分治算法的适用条件,那么就可以使用分治算法。

    image-20201130165303362

    那么采用分治算法解决的问题需要 满足那些条件(特征) 呢?

    1 . 原问题规模通常比较大,不易直接解决,但问题缩小到一定程度就能较容易的解决。

    2 . 问题可以分解为若干规模较小、求解方式相同(似)的子问题。且子问题之间求解是独立的互不影响。

    3 . 合并问题分解的子问题可以得到问题的解。

    你可能会疑惑分治算法和递归有什么关系?其实分治重要的是一种思想,注重的是问题分、治、合并的过程。而递归是一种方式(工具),这种方式通过方法自己调用自己形成一个来回的过程,而分治可能就是利用了多次这样的来回过程。

    分治算法经典问题

    对于分治算法的经典问题,重要的是其思想,因为我们大部分借助递归去实现,所以在代码实现上大部分都是很简单,而本篇也重在讲述思想。

    分治算法的经典问题,个人将它分成两大类:子问题完全独立和子问题不完全独立。

    1 . 子问题完全独立就是原问题的答案可完全由子问题的结果推出。

    2 . 子问题不完全独立,有些区间类的问题或者跨区间问题使用分治可能结果跨区间,在考虑问题的时候需要仔细借鉴下。

    二分搜索

    二分搜索是分治的一个实例,只不过二分搜索有着自己的特殊性

    • 序列有序
    • 结果为一个值

    正常二分将一个完整的区间分成两个区间,两个区间本应单独找值然后确认结果,但是通过有序的区间可以直接确定结果在那个区间,所以分的两个区间只需要计算其中一个区间,然后继续进行一直到结束。实现方式有递归和非递归,但是非递归用的更多一些:

    public int searchInsert(int[] nums, int target) {
      if(nums[0]>=target)return 0;//剪枝
      if(nums[nums.length-1]==target)return nums.length-1;//剪枝
      if(nums[nums.length-1]<target)return nums.length;
      int left=0,right=nums.length-1;
      while (left<right) {
        int mid=(left+right)/2;
        if(nums[mid]==target)
          return mid;
        else if (nums[mid]>target) {
          right=mid;
        }
        else {
          left=mid+1;
        }
      }
      return left;
    }
    

    快速排序

    快排也是分治的一个实例,快排每一趟会选定一个数,将比这个数小的放左面,比这个数大的放右面,然后递归分治求解两个子区间,当然快排因为在分的时候就做了很多工作,当全部分到最底层的时候这个序列的值就是排序完的值。这是一种分而治之的体现。

    image-20201120133851275

    public void quicksort(int [] a,int left,int right)
    {
      int low=left;
      int high=right;
      //下面两句的顺序一定不能混,否则会产生数组越界!!!very important!!!
      if(low>high)//作为判断是否截止条件
        return;
      int k=a[low];//额外空间k,取最左侧的一个作为衡量,最后要求左侧都比它小,右侧都比它大。
      while(low<high)//这一轮要求把左侧小于a[low],右侧大于a[low]。
      {
        while(low<high&&a[high]>=k)//右侧找到第一个小于k的停止
        {
          high--;
        }
        //这样就找到第一个比它小的了
        a[low]=a[high];//放到low位置
        while(low<high&&a[low]<=k)//在low往右找到第一个大于k的,放到右侧a[high]位置
        {
          low++;
        }
        a[high]=a[low];			
      }
      a[low]=k;//赋值然后左右递归分治求之
      quicksort(a, left, low-1);
      quicksort(a, low+1, right);		
    }
    
    

    归并排序(逆序数)

    快排在分的时候做了很多工作,而归并就是相反,归并在分的时候按照数量均匀分,而合并时候已经是两两有序的进行合并的,因为两个有序序列O(n)级别的复杂度即可得到需要的结果。而逆序数在归并排序基础上变形同样也是分治思想求解。

    image-20201120173153449

    private static void mergesort(int[] array, int left, int right) {
      int mid=(left+right)/2;
      if(left<right)
      {
        mergesort(array, left, mid);
        mergesort(array, mid+1, right);
        merge(array, left,mid, right);
      }
    }
    
    private static void merge(int[] array, int l, int mid, int r) {
      int lindex=l;int rindex=mid+1;
      int team[]=new int[r-l+1];
      int teamindex=0;
      while (lindex<=mid&&rindex<=r) {//先左右比较合并
        if(array[lindex]<=array[rindex])
        {
          team[teamindex++]=array[lindex++];
        }
        else {				
          team[teamindex++]=array[rindex++];
        }
      }
      while(lindex<=mid)//当一个越界后剩余按序列添加即可
      {
        team[teamindex++]=array[lindex++];
    
      }
      while(rindex<=r)
      {
        team[teamindex++]=array[rindex++];
      }	
      for(int i=0;i<teamindex;i++)
      {
        array[l+i]=team[i];
      }
    }
    

    最大子序列和

    最大子序列和的问题我们可以使用动态规划的解法,但是也可以使用分治算法来解决问题,但是最大子序列和在合并的时候并不是简单的合并,因为子序列和涉及到一个长度的问题,所以正确结果不一定全在最左侧或者最右侧,而可能出现结果的区域为:

    • 完全在中间的左侧
    • 完全在中间的右侧
    • 包含中间左右两个节点的一个序列

    用一张图可以表示为:

    在这里插入图片描述

    所以在具体考虑的时候需要将无法递归得到结果的中间那个最大值串的结果也算出来参与左侧、右侧值得比较。

    力扣53. 最大子序和在实现的代码为:

    public int maxSubArray(int[] nums) {
        int max=maxsub(nums,0,nums.length-1);
        return max;
    }
    int maxsub(int nums[],int left,int right)
    {
        if(left==right)
            return  nums[left];
        int mid=(left+right)/2;
        int leftmax=maxsub(nums,left,mid);//左侧最大
        int rightmax=maxsub(nums,mid+1,right);//右侧最大
    
        int midleft=nums[mid];//中间往左
        int midright=nums[mid+1];//中间往右
        int team=0;
        for(int i=mid;i>=left;i--)
        {
            team+=nums[i];
            if(team>midleft)
                midleft=team;
        }
        team=0;
        for(int i=mid+1;i<=right;i++)
        {
            team+=nums[i];
            if(team>midright)
                midright=team;
        }
        int max=midleft+midright;//中间的最大值
        if(max<leftmax)
            max=leftmax;
        if(max<rightmax)
            max=rightmax;
        return  max;
    }
    

    最近点对

    最近点对是一个分治非常成功的运用之一。在二维坐标轴上有若干个点坐标,让你求出最近的两个点的距离,如果让你直接求那么枚举暴力是个非常非常大的计算量,我们通常采用分治的方法来优化这种问题。

    image-20201130204401673

    如果直接分成两部分分治计算你肯定会发现如果最短的如果一个在左一个在右会出现问题。我们可以优化一下。

    在具体的优化方案上,按照x或者y的维度进行考虑,将数据分成两个区域,先分别计算(按照同方法)左右区域内最短的点对。然后根据这个两个中较短的距离向左和向右覆盖,计算被覆盖的左右点之间的距离,找到最小那个距离与当前最短距离比较即可。

    image-20201130205950625

    这样你就可以发现就这个一次的操作(不考虑子情况),左侧红点就避免和右侧大部分红点进行距离计算(O(n2)的时间复杂度)。事实上,在进行左右区间内部计算的时候,它其实也这样递归的进行很多次分治计算。如图所示:

    image-20201130210925059

    这样下去就可以节省很多次的计算量。

    但是这种分治会存在一种问题就是二维坐标可能点都聚集某个方法某条轴那么可能效果并不明显(点都在x=2附近对x分割作用就不大),需要注意一下。

    杭电1007推荐给大家,ac的代码为:

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.OutputStreamWriter;
    import java.io.PrintWriter;
    import java.io.StreamTokenizer;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Comparator;
    import java.util.List;
    public class Main {
        static int n;
        public static void main(String[] args) throws IOException {
            StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
            PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
            //List<node>list=new ArrayList();
             while(in.nextToken()!=StreamTokenizer.TT_EOF)
             {
                 n=(int)in.nval;if(n==0) {break;}
                node no[]=new node[n];
                
                 for(int i=0;i<n;i++)
                 {
                     in.nextToken();double x=in.nval;
                     in.nextToken();double y=in.nval;
                    // list.add(new node(x,y));
                     no[i]=new node(x,y);
                 }
                 Arrays.sort(no, com);
                double min= search(no,0,n-1);
                out.println(String.format("%.2f", Math.sqrt(min)/2));out.flush();
             }         
        }
        private static double search(node[] no, int left,int right) {
            int mid=(right+left)/2;
            double minleng=0;
            if(left==right) {return Double.MAX_VALUE;}
            else if(left+1==right) {minleng= (no[left].x-no[right].x)*(no[left].x-no[right].x)+(no[left].y-no[right].y)*(no[left].y-no[right].y);}
            else minleng= min(search(no,left,mid),search(no,mid,right));
            int ll=mid;int rr=mid+1;
            while(no[mid].y-no[ll].y<=Math.sqrt(minleng)/2&&ll-1>=left) {ll--;}
            while(no[rr].y-no[mid].y<=Math.sqrt(minleng)/2&&rr+1<=right) {rr++;}
            for(int i=ll;i<rr;i++)
            {
                for(int j=i+1;j<rr+1;j++)
                {
                    double team=0;
                    if(Math.abs((no[i].x-no[j].x)*(no[i].x-no[j].x))>minleng) {continue;}
                    else
                    { 
                        team=(no[i].x-no[j].x)*(no[i].x-no[j].x)+(no[i].y-no[j].y)*(no[i].y-no[j].y);
                        if(team<minleng)minleng=team;
                    }
                }
            }
            return minleng;
        
        }
        private static double min(double a, double b) {
            // TODO 自动生成的方法存根
            return a<b?a:b;
        }
        static Comparator<node>com=new Comparator<node>() {
    
            @Override
            public int compare(node a1, node a2) {
                // TODO 自动生成的方法存根
                return a1.y-a2.y>0?1:-1;
            }};
        static class node
        {
            double x;
            double y;
            public node(double x,double y)
            {
                this.x=x;
                this.y=y;
            }
        }
    }
    
    

    结语

    到这里,分治算法就讲这么多了,因为分治算法重要在于理解其思想,还有一些典型的分治算法解决的问题,例如大整数乘法、Strassen矩阵乘法、棋盘覆盖、线性时间选择、循环赛日程表、汉诺塔等问题你可以自己研究其分治的思想和原理。

    原创不易,bigsai请你帮两件事帮忙一下:

    1. 点赞在看, 您的肯定是我在平台创作的源源动力。

    2. 微信搜索「bigsai」,关注我的公众号,不仅免费送你电子书,我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。

    记得关注、咱们下次再见!

    image-20201114211553660

    展开全文
  • [回溯算法] 五大常用算法之回溯法

    万次阅读 多人点赞 2018-02-12 14:40:46
    算法入门6:回溯法一. 回溯法 – 深度优先搜素 1. 简单概述 回溯法思路的简单描述是:把问题的解空间转化成了图或者树的结构表示,然后使用深度优先搜索策略进行遍历,遍历的过程中记录和寻找所有可行解或者最优解...

    算法入门6:回溯法

    一. 回溯法 – 深度优先搜素                       

    1. 简单概述

           回溯法思路的简单描述是:把问题的解空间转化成了图或者树的结构表示,然后使用深度优先搜索策略进行遍历,遍历的过程中记录和寻找所有可行解或者最优解。

    基本思想类同于:

    • 图的深度优先搜索
    • 二叉树的后序遍历

          【

             分支限界法:广度优先搜索

             思想类同于:图的广度优先遍历

                                    二叉树的层序遍历

          】

    2. 详细描述

            详细的描述则为:

            回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树,当算法搜索至解空间树的某一节点时,先利用剪枝函数判断该节点是否可行(即能得到问题的解)。如果不可行,则跳过对该节点为根的子树的搜索,逐层向其祖先节点回溯;否则,进入该子树,继续按深度优先策略搜索。

            回溯法的基本行为是搜索,搜索过程使用剪枝函数来为了避免无效的搜索。剪枝函数包括两类:1. 使用约束函数,剪去不满足约束条件的路径;2.使用限界函数,剪去不能得到最优解的路径。

            问题的关键在于如何定义问题的解空间,转化成树(即解空间树)。解空间树分为两种:子集树和排列树。两种在算法结构和思路上大体相同。

    3. 回溯法应用

           当问题是要求满足某种性质(约束条件)的所有解或最优解时,往往使用回溯法。

           它有“通用解题法”之美誉。

    二. 回溯法实现 - 递归和递推(迭代)                               

            回溯法的实现方法有两种:递归和递推(也称迭代)。一般来说,一个问题两种方法都可以实现,只是在算法效率和设计复杂度上有区别。
          【类比于图深度遍历的递归实现和非递归(递推)实现】

    1. 递归

            思路简单,设计容易,但效率低,其设计范式如下:

    [cpp]  view plain  copy
    1. //针对N叉树的递归回溯方法  
    2. void backtrack (int t)  
    3. {  
    4.     if (t>n) output(x); //叶子节点,输出结果,x是可行解  
    5.     else  
    6.        for i = 1 to k//当前节点的所有子节点  
    7.         {  
    8.             x[t]=value(i); //每个子节点的值赋值给x  
    9.             //满足约束条件和限界条件  
    10.           if (constraint(t)&&bound(t))   
    11.                 backtrack(t+1);  //递归下一层  
    12.         }  
    13. }  

    2. 递推

          算法设计相对复杂,但效率高。

    [cpp]  view plain  copy
    1. //针对N叉树的迭代回溯方法  
    2. void iterativeBacktrack ()  
    3. {  
    4.     int t=1;  
    5.     while (t>0) {  
    6.         if(ExistSubNode(t)) //当前节点的存在子节点  
    7.         {  
    8.             for i = 1 to k  //遍历当前节点的所有子节点  
    9.             {  
    10.                 x[t]=value(i);//每个子节点的值赋值给x  
    11.                 if (constraint(t)&&bound(t))//满足约束条件和限界条件   
    12.                 {  
    13.                     //solution表示在节点t处得到了一个解  
    14.                     if (solution(t)) output(x);//得到问题的一个可行解,输出  
    15.                     else t++;//没有得到解,继续向下搜索  
    16.                 }  
    17.             }  
    18.         }  
    19.         else //不存在子节点,返回上一层  
    20.         {  
    21.             t--;  
    22.         }  
    23.     }  
    24. }  

    三. 子集树和排列树                                                        

    1. 子集树

           所给的问题是从n个元素的集合S中找出满足某种性质的子集时,相应的解空间成为子集树。
    如0-1背包问题,从所给重量、价值不同的物品中挑选几个物品放入背包,使得在满足背包不超重的情况下,背包内物品价值最大。它的解空间就是一个典型的子集树。

           回溯法搜索子集树的算法范式如下:

    [cpp]  view plain  copy
    1. void backtrack (int t)  
    2. {  
    3.   if (t>n) output(x);  
    4.     else  
    5.       for (int i=0;i<=1;i++) {  
    6.         x[t]=i;  
    7.         if (constraint(t)&&bound(t)) backtrack(t+1);  
    8.       }  
    9. }  
    10.  

    2. 排列树

          所给的问题是确定n个元素满足某种性质的排列时,相应的解空间就是排列树。
    如旅行售货员问题,一个售货员把几个城市旅行一遍,要求走的路程最小。它的解就是几个城市的排列,解空间就是排列树。
          回溯法搜索排列树的算法范式如下:

    [cpp]  view plain  copy
    1. void backtrack (int t)  
    2. {  
    3.   if (t>n) output(x);  
    4.     else  
    5.       for (int i=t;i<=n;i++) {  
    6.         swap(x[t], x[i]);  
    7.         if (constraint(t)&&bound(t)) backtrack(t+1);  
    8.         swap(x[t], x[i]);  
    9.       }  
    10.   
    11.   

    四. 经典问题                                    

    (1)装载问题
    (2)0-1背包问题
    (3)旅行售货员问题
    (4)八皇后问题
    (5)迷宫问题
    (6)图的m着色问题

    1. 0-1背包问题

            问题:给定n种物品和一背包。物品i的重量是wi,其价值为pi,背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
            分析:问题是n个物品中选择部分物品,可知,问题的解空间是子集树。比如物品数目n=3时,其解空间树如下图,边为1代表选择该物品,边为0代表不选择该物品。使用x[i]表示物品i是否放入背包,x[i]=0表示不放,x[i]=1表示放入。回溯搜索过程,如果来到了叶子节点,表示一条搜索路径结束,如果该路径上存在更优的解,则保存下来。如果不是叶子节点,是中点的节点(如B),就遍历其子节点(D和E),如果子节点满足剪枝条件,就继续回溯搜索子节点。


    代码:

    [cpp]  view plain  copy
    1. #include <stdio.h>  
    2.    
    3. #define N 3         //物品的数量  
    4. #define C 16        //背包的容量  
    5.    
    6. int w[N]={10,8,5};  //每个物品的重量  
    7. int v[N]={5,4,1};   //每个物品的价值  
    8. int x[N]={0,0,0};   //x[i]=1代表物品i放入背包,0代表不放入  
    9.    
    10. int CurWeight = 0;  //当前放入背包的物品总重量  
    11. int CurValue = 0;   //当前放入背包的物品总价值  
    12.    
    13. int BestValue = 0;  //最优值;当前的最大价值,初始化为0  
    14. int BestX[N];       //最优解;BestX[i]=1代表物品i放入背包,0代表不放入  
    15.    
    16. //t = 0 to N-1  
    17. void backtrack(int t)  
    18. {  
    19.     //叶子节点,输出结果  
    20.     if(t>N-1)   
    21.     {  
    22.         //如果找到了一个更优的解  
    23.         if(CurValue>BestValue)  
    24.         {  
    25.             //保存更优的值和解  
    26.             BestValue = CurValue;  
    27.             for(int i=0;i<N;++i) BestX[i] = x[i];  
    28.         }  
    29.     }  
    30.     else  
    31.     {  
    32.         //遍历当前节点的子节点:0 不放入背包,1放入背包  
    33.         for(int i=0;i<=1;++i)  
    34.         {  
    35.             x[t]=i;  
    36.    
    37.             if(i==0) //不放入背包  
    38.             {  
    39.                 backtrack(t+1);  
    40.             }  
    41.             else //放入背包  
    42.             {  
    43.                  //约束条件:放的下  
    44.                 if((CurWeight+w[t])<=C)  
    45.                 {  
    46.                     CurWeight += w[t];  
    47.                     CurValue += v[t];  
    48.                     backtrack(t+1);  
    49.                     CurWeight -= w[t];  
    50.                     CurValue -= v[t];  
    51.                 }  
    52.             }  
    53.         }  
    54.         //PS:上述代码为了更符合递归回溯的范式,并不够简洁  
    55.     }  
    56. }  
    57.    
    58. int main(int argc, char* argv[])  
    59. {  
    60.     backtrack(0);  
    61.    
    62.     printf("最优值:%d\n",BestValue);  
    63.    
    64.     for(int i=0;i<N;i++)  
    65.     {  
    66.        printf("最优解:%-3d",BestX[i]);  
    67.     }  
    68.     return 0;  
    69. }  

    2. 旅行售货员问题

          回溯法----旅行售货员问题

    3. 详细描述N皇后问题

           问题:在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

           N皇后问题等价于在n×n格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。

          分析:从n×n个格子中选择n个格子摆放皇后。可见解空间树为子集树。

          使用Board[N][N]来表示棋盘,Board[i][j]=0 表示(I,j)位置为空,Board[i][j]=1 表示(I,j)位置摆放有一个皇后。

          全局变量way表示总共的摆放方法数目。

          使用Queen(t)来摆放第t个皇后。Queen(t) 函数符合子集树时的递归回溯范式。当t>N时,说明所有皇后都已经摆   放完成,这是一个可行的摆放方法,输出结果;否则,遍历棋盘,找皇后t所有可行的摆放位置,Feasible(i,j) 判断皇后t能否摆放在位置(i,j)处,如果可以摆放则继续递归摆放皇后t+1,如果不能摆放,则判断下一个位置。

           Feasible(row,col)函数首先判断位置(row,col)是否合法,继而判断(row,col)处是否已有皇后,有则冲突,返回0,无则继续判断行、列、斜方向是否冲突。斜方向分为左上角、左下角、右上角、右下角四个方向,每次从(row,col)向四个方向延伸一个格子,判断是否冲突。如果所有方向都没有冲突,则返回1,表示此位置可以摆放一个皇后。


            代码:

    [cpp]  view plain  copy
    1. /************************************************************************  
    2.  * 名  称:NQueen.cpp 
    3.  * 功  能:回溯算法实例:N皇后问题  
    4.  * 作  者:JarvisChu  
    5.  * 时  间:2013-11-13  
    6.  ************************************************************************/   
    7.    
    8. #include <stdio.h>  
    9.    
    10. #define N 8  
    11.    
    12. int Board[N][N];//棋盘 0表示空白 1表示有皇后  
    13. int way;//摆放的方法数  
    14.    
    15.    
    16. //判断能否在(x,y)的位置摆放一个皇后;0不可以,1可以  
    17. int Feasible(int row,int col)  
    18. {  
    19.     //位置不合法  
    20.     if(row>N || row<0 || col >N || col<0)  
    21.         return 0;  
    22.    
    23.     //该位置已经有皇后了,不能  
    24.     if(Board[row][col] != 0)  
    25.     {   //在行列冲突判断中也包含了该判断,单独提出来为了提高效率  
    26.         return 0;  
    27.     }  
    28.    
    29.     //  
    30.     //下面判断是否和已有的冲突  
    31.    
    32.     //行和列是否冲突  
    33.     for(int i=0;i<N;++i)  
    34.     {  
    35.         if(Board[row][i] != 0 || Board[i][col]!=0)  
    36.             return 0;  
    37.     }  
    38.    
    39.     //斜线方向冲突  
    40.    
    41.     for(int i=1;i<N;++i)  
    42.     {  
    43. /* i表示从当前点(row,col)向四个斜方向扩展的长度 
    44.   
    45. 左上角 \  / 右上角   i=2 
    46.         \/           i=1 
    47.         /\           i=1 
    48. 左下角 /  \ 右下角   i=2 
    49. */  
    50.         //左上角  
    51.         if((row-i)>=0 && (col-i)>=0)    //位置合法  
    52.         {  
    53.             if(Board[row-i][col-i] != 0)//此处已有皇后,冲突  
    54.                 return 0;  
    55.         }  
    56.    
    57.         //左下角  
    58.         if((row+i)<N && (col-i)>=0)  
    59.         {  
    60.             if(Board[row+i][col-i] != 0)  
    61.                 return 0;  
    62.         }  
    63.    
    64.         //右上角  
    65.         if((row-i)>=0 && (col+i)<N)  
    66.         {  
    67.             if(Board[row-i][col+i] != 0)  
    68.                 return 0;  
    69.         }  
    70.    
    71.         //右下角  
    72.         if((row+i)<N && (col+i)<N)  
    73.         {  
    74.             if(Board[row+i][col+i] != 0)  
    75.                 return 0;  
    76.         }  
    77.     }  
    78.    
    79.     return 1; //不会发生冲突,返回1  
    80. }  
    81.    
    82.    
    83. //摆放第t个皇后 ;从1开始  
    84. void Queen(int t)  
    85. {  
    86.     //摆放完成,输出结果  
    87.     if(t>N)  
    88.     {  
    89.         way++;  
    90.         /*如果N较大,输出结果会很慢;N较小时,可以用下面代码输出结果 
    91.         for(int i=0;i<N;++i){ 
    92.             for(int j=0;j<N;++j) 
    93.                 printf("%-3d",Board[i][j]); 
    94.             printf("\n"); 
    95.         } 
    96.         printf("\n------------------------\n\n"); 
    97.         */  
    98.     }  
    99.     else  
    100.     {  
    101.         for(int i=0;i<N;++i)  
    102.         {  
    103.             for(int j=0;j<N;++j)  
    104.             {  
    105.                 //(i,j)位置可以摆放皇后,不冲突  
    106.                 if(Feasible(i,j))  
    107.                 {  
    108.                     Board[i][j] = 1;  //摆放皇后t  
    109.                     Queen(t+1);       //递归摆放皇后t+1  
    110.                     Board[i][j] = 0;  //恢复  
    111.                 }  
    112.             }  
    113.         }  
    114.     }  
    115. }  
    116.    
    117. //返回num的阶乘,num!  
    118. int factorial(int num)  
    119. {  
    120.     if(num==0 || num==1)  
    121.         return 1;  
    122.     return num*factorial(num-1);  
    123. }  
    124.    
    125.    
    126. int main(int argc, char* argv[])  
    127. {  
    128.     //初始化  
    129.     for(int i=0;i<N;++i)  
    130.     {  
    131.         for(int j=0;j<N;++j)  
    132.         {  
    133.             Board[i][j]=0;  
    134.         }  
    135.     }  
    136.    
    137.     way = 0;  
    138.    
    139.     Queen(1);  //从第1个皇后开始摆放  
    140.    
    141.     //如果每个皇后都不同  
    142.     printf("考虑每个皇后都不同,摆放方法:%d\n",way);//N=8时, way=3709440 种  
    143.    
    144.     //如果每个皇后都一样,那么需要除以 N!出去重复的答案(因为相同,则每个皇后可任意调换位置)  
    145.     printf("考虑每个皇后都不同,摆放方法:%d\n",way/factorial(N));//N=8时, way=3709440/8! = 92种  
    146.    
    147.     return 0;  
    148. }  

    PS:该问题还有更优的解法。充分利用问题隐藏的约束条件:每个皇后必然在不同的行(列),每个行(列)必然也只有一个皇后。这样我们就可以把N个皇后放到N个行中,使用Pos[i]表示皇后i在i行中的位置(也就是列号)(i = 0 to N-1)。这样代码会大大的简洁,因为节点的子节点数目会减少,判断冲突也更简单。

    4. 迷宫问题

            问题:给定一个迷宫,找到从入口到出口的所有可行路径,并给出其中最短的路径

            分析:用二维数组来表示迷宫,则走迷宫问题用回溯法解决的的思想类似于图的深度遍历。从入口开始,选择下一个可以走的位置,如果位置可走,则继续往前,如果位置不可走,则返回上一个位置,重新选择另一个位置作为下一步位置。

            N表示迷宫的大小,使用Maze[N][N]表示迷宫,值为0表示通道(可走),值为1表示不可走(墙或者已走过);

            Point结构体用来记录路径中每一步的坐标(x,y)

           (ENTER_X,ENTER_Y) 是迷宫入口的坐标

           (EXIT_X, EXIT _Y)    是迷宫出口的坐标

           Path容器用来存放一条从入口到出口的通路路径

           BestPath用来存放所有路径中最短的那条路径


           Maze()函数用来递归走迷宫,具体步骤为:

           1. 首先将当前点加入路径,并设置为已走
           2. 判断当前点是否为出口,是则输出路径,保存结果;跳转到4
           3. 依次判断当前点的上、下、左、右四个点是否可走,如果可走则递归走该点
           4. 当前点推出路径,设置为可走

           代码:

    [cpp]  view plain  copy
    1. /************************************************************************  
    2.  * 名  称:Maze.cpp 
    3.  * 功  能:回溯算法实例:迷宫问题 
    4.  * 作  者:JarvisChu  
    5.  * 时  间:2013-11-13  
    6.  ************************************************************************/   
    7. #include <iostream>  
    8. #include <vector>  
    9.    
    10. using namespace std;  
    11.    
    12. typedef struct  
    13. {  
    14.     int x;  
    15.     int y;  
    16. }Point;  
    17.    
    18. #define N 10         //迷宫的大小  
    19. #define ENTER_X 0    //入口的位置(0,0)  
    20. #define ENTER_Y 0  
    21. #define EXIT_X N-1   //出口的位置(N-1,N-1)  
    22. #define EXIT_Y N-1   
    23.    
    24.    
    25. int Maze[N][N];<span style="white-space:pre;">      </span>//定义一个迷宫,0表示通道,1表示不可走(墙或已走)  
    26. int paths;<span style="white-space:pre;">       </span>//路径条数  
    27. vector<Point> Path;<span style="white-space:pre;">    </span>//保存一条可通的路径  
    28. vector<Point> BestPath;<span style="white-space:pre;">    </span>//保存最短的路径  
    29.    
    30. bool First = true;<span style="white-space:pre;">   </span>//标志,找到第一条路径  
    31.    
    32. //初始化迷宫  
    33. void InitMaze()  
    34. {  
    35. <span style="white-space:pre;"> </span>//简单起见,本题定义一个固定大小10*10的迷宫  
    36. <span style="white-space:pre;"> </span>//定义一个迷宫,0表示通道,1表示墙(或不可走)  
    37.     int mz[10][10]={  
    38.     {0,0,1,1,1,1,1,1,1,1}, //0  
    39.     {1,0,0,1,1,0,0,1,0,1}, //1  
    40.     {1,0,0,1,0,0,0,1,0,1}, //2  
    41.     {1,0,0,0,0,1,1,0,0,1}, //3  
    42.     {1,0,1,1,1,0,0,0,0,1}, //4  
    43.     {1,0,0,0,1,0,0,0,0,1}, //5  
    44.     {1,0,1,0,0,0,1,0,0,1}, //6  
    45.     {1,0,1,1,1,0,1,1,0,1}, //7  
    46.     {1,1,0,0,0,0,0,0,0,0}, //8  
    47.     {1,1,1,1,1,1,1,1,1,0}  //9  
    48.     //   0 1 2 3 4 5 6 7 8 9  
    49.     };   
    50.    
    51.     //复制到迷宫  
    52.     memcpy(Maze,mz,sizeof(mz));  
    53.    
    54.     paths = 0;  
    55. }  
    56.    
    57. //从(x,y)位置开始走;初始为(0,0)  
    58. void MazeTrack(int x,int y)  
    59. {  
    60.     ///  
    61.     //当前点加入到路径  
    62.     Point p={x,y};  
    63.     Path.push_back(p);  
    64.     Maze[x][y] = 1;         //设置为已走,不可走  
    65.    
    66.     //cout<<"来到("<<x<<","<<y<<")"<<endl;  
    67.    
    68.     ///  
    69.     //如果该位置是出口,输出结果  
    70.     if(x == EXIT_X && y== EXIT_Y)  
    71.     {  
    72.         cout<<"找到一条道路"<<endl;  
    73.         paths++;  
    74.           
    75.         //输出路径  
    76.         vector<Point>::iterator it;  
    77.         for(it=Path.begin();it!=Path.end();++it)  
    78.         {  
    79.             cout<<"("<<it->x<<","<<it->y<<") ";  
    80.         }  
    81.         cout<<endl;  
    82.    
    83.         //判断是否更优  
    84.         if(First)//如果是找到的第一条路径,直接复制到最优路径  
    85.         {  
    86.             for(it=Path.begin();it!=Path.end();++it)  
    87.             {  
    88.                 BestPath.push_back(*it);  
    89.             }  
    90.             First = false;  
    91.         }  
    92.         else //不是第一条,则判断是否更短  
    93.         {  
    94.             //更短,复制到最优路径  
    95.             if(Path.size()<BestPath.size())  
    96.             {  
    97.                 BestPath.clear();  
    98.                 for(it=Path.begin();it!=Path.end();++it)  
    99.                 {  
    100.                     BestPath.push_back(*it);  
    101.                 }  
    102.             }  
    103.         }  
    104.     }  
    105.    
    106.     ///  
    107.     //判断(x,y)位置的上、下、左、右是否可走  
    108.    
    109.     if((x-1)>=0 && Maze[x-1][y]==0)//上(x-1,y);存在且可走  
    110.     {  
    111.         MazeTrack(x-1,y);  
    112.     }  
    113.    
    114.     if((x+1)<N && Maze[x+1][y]==0)//下(x+1,y);存在且可走  
    115.     {  
    116.         MazeTrack(x+1,y);  
    117.     }  
    118.    
    119.     if((y-1)>=0 && Maze[x][y-1]==0)//左(x,y-1);存在且可走  
    120.     {  
    121.         MazeTrack(x,y-1);  
    122.     }  
    123.    
    124.     if((y+1)<N && Maze[x][y+1]==0)//右(x,y+1);存在且可走  
    125.     {  
    126.         MazeTrack(x,y+1);  
    127.     }  
    128.    
    129.     ///  
    130.     //返回上一步  
    131.     Path.pop_back();  
    132.     Maze[x][y] = 0;         //设置为未走  
    133. }  
    134.    
    135.    
    136. int main(int argc, char* argv[])  
    137. {  
    138.     //初始化迷宫  
    139.     InitMaze();  
    140.           
    141. /*  //显示迷宫 
    142.     for(int i=0;i<N;++i){ 
    143.         for(int j=0;j<N;++j) 
    144.             cout<<Maze[i][j]<<"  "; 
    145.         cout<<endl; 
    146.     }*/  
    147.    
    148.     //回溯法走迷宫  
    149.     MazeTrack(ENTER_X,ENTER_Y);  
    150.    
    151.     //显示最优的路径  
    152.     cout<<"可行路径总条数为"<<paths<<";最优路径为"<<endl;  
    153.     vector<Point>::iterator it;  
    154.     for(it=BestPath.begin();it!=BestPath.end();++it)  
    155.     {  
    156.         cout<<"("<<it->x<<","<<it->y<<") ";  
    157.     }  
    158.     cout<<endl;  
    159.     return 0;  
    160. }  

    PS:用WPF实现了一个简单的图形化迷宫程序。白色表示通道,红色表示墙,最短的路径用黄色显示。目前实现了一个10*10的迷宫自动搜素最短通路,右侧显示搜索过程中得到的每一个可行通路。
    由于构造一个迷宫比较复杂,所以暂时“迷宫设置”功能没有做实现,至于手动一步步查看搜素过程的动画也没有做实现。


    实现的大致思路如下:迷宫的数据使用二维数据mazeData表示。迷宫的显示使用Grid控件表示,每个方格处添加一个Rectangle控件,如果该方格mazeData值为0,则填充白色值为1,则填充红色,值为2则填充黄色。


    XAML代码为:

    [html]  view plain  copy
    1. <Window x:Class="MazeAnimation.MainWindow"  
    2.         xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"  
    3.         xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"  
    4.         Title="迷宫" Height="496" Width="673" Loaded="Window_Loaded">  
    5.     <Grid>  
    6.         <Grid.RowDefinitions>  
    7.             <RowDefinition Height="30"></RowDefinition>  
    8.             <RowDefinition Height="*"></RowDefinition>  
    9.             <RowDefinition Height="120"></RowDefinition>  
    10.         </Grid.RowDefinitions>  
    11.           
    12.         <Grid.ColumnDefinitions>  
    13.             <ColumnDefinition Width="463"></ColumnDefinition>  
    14.             <ColumnDefinition Width="*"></ColumnDefinition>  
    15.         </Grid.ColumnDefinitions>  
    16.           
    17.         <DockPanel Name="dpTips" Grid.Row="0" Grid.ColumnSpan="2" Background="AliceBlue" >  
    18.             <Label FontSize="16" Foreground="#FFAD1616" HorizontalAlignment="Center">迷宫的动态演示</Label>  
    19.         </DockPanel>  
    20.           
    21.         <Grid Name="gdMaze" Grid.Row="1" Grid.Column="0" HorizontalAlignment="Stretch" VerticalAlignment="Stretch" >  
    22.               
    23.         </Grid>  
    24.   
    25.         <ScrollViewer Grid.Row="1" Grid.Column="1"  Margin="5" HorizontalAlignment="Stretch" HorizontalScrollBarVisibility="Auto">  
    26.             <TextBox Name="tbLog" Background="Beige"></TextBox>  
    27.         </ScrollViewer>  
    28.           
    29.         <DockPanel Name="dpSetting" Grid.Row="2" Grid.Column="0"  VerticalAlignment="Stretch">  
    30.    
    31.             <TabControl Name="tcMazeSetting"  Background="#FFE5D9D9" VerticalAlignment="Stretch" HorizontalAlignment="Stretch">  
    32.                 <TabItem Header="迷宫设置" Name="tabItemMaze">  
    33.                     <Grid>  
    34.                         <Grid.RowDefinitions>  
    35.                             <RowDefinition Height="*"></RowDefinition>  
    36.                             <RowDefinition Height="*"></RowDefinition>  
    37.                             <RowDefinition Height="*"></RowDefinition>  
    38.                         </Grid.RowDefinitions>  
    39.                         <Grid.ColumnDefinitions>  
    40.                             <ColumnDefinition Width="60"></ColumnDefinition>  
    41.                             <ColumnDefinition Width="*"></ColumnDefinition>  
    42.                         </Grid.ColumnDefinitions>  
    43.                           
    44.                         <Label Content="大小:"  Name="label1" Grid.Row="0" Grid.Column="0"/>  
    45.                         <Label Content="入口:"  Name="label2" Grid.Row="1" Grid.Column="0"/>  
    46.                         <Label Content="出口:"  Name="label3" Grid.Row="2" Grid.Column="0"/>  
    47.                                                                      
    48.                         <StackPanel Grid.Row="0" Grid.Column="1" Orientation="Horizontal">  
    49.                             <Label Content="高:"></Label>  
    50.                             <TextBox Name="tbMazeHeight" HorizontalAlignment="Left" MinWidth="40"></TextBox>  
    51.                             <Label Content="宽:"></Label>  
    52.                             <TextBox Name="tbMazeWidth" HorizontalAlignment="Left" MinWidth="40"></TextBox>  
    53.                         </StackPanel>  
    54.   
    55.                         <StackPanel Grid.Row="1" Grid.Column="1" Orientation="Horizontal">  
    56.                             <Label Content="X="></Label>  
    57.                             <TextBox Name="tbEnterX" HorizontalAlignment="Left" MinWidth="40"></TextBox>  
    58.                             <Label Content="Y="></Label>  
    59.                             <TextBox Name="tbEnterY" HorizontalAlignment="Left" MinWidth="40"></TextBox>  
    60.                         </StackPanel>  
    61.   
    62.                         <StackPanel Grid.Row="2" Grid.Column="1" Orientation="Horizontal">  
    63.                             <Label Content="X="></Label>  
    64.                             <TextBox Name="tbExitX" HorizontalAlignment="Left" MinWidth="40"></TextBox>  
    65.                             <Label Content="Y="></Label>  
    66.                             <TextBox Name="tbExitY" HorizontalAlignment="Left" MinWidth="40"></TextBox>  
    67.                         </StackPanel>  
    68.                     </Grid>  
    69.                       
    70.                 </TabItem>  
    71.                 <TabItem Header="演示设置" Name="tabItemDemo">  
    72.                     <StackPanel Orientation="Vertical" HorizontalAlignment="Stretch">  
    73.                         <CheckBox Name="cbAutoRun" Content="自动执行" Margin="10"></CheckBox>  
    74.                         <StackPanel Orientation="Horizontal">  
    75.                             <Label Content="执行速度:" Margin="10"></Label>  
    76.                             <TextBox Name="tbAutoRunSpeed" MinWidth="50" Margin="10"></TextBox>  
    77.                             <Label Content="毫秒" Margin="0,10,0,10"></Label>  
    78.                         </StackPanel>  
    79.                     </StackPanel>  
    80.                 </TabItem>  
    81.             </TabControl>  
    82.         </DockPanel>  
    83.           
    84.         <StackPanel Orientation="Horizontal" Grid.Row="2" Grid.Column="1" HorizontalAlignment="Center">  
    85.             <Button Name="btnStart" Content="自动开始" Height="40" Width="70" Margin="5" Click="btnStart_Click"></Button>  
    86.             <Button Name="btnNext" Content="手动下一步" Height="40" Width="70" Margin="5" Click="btnNext_Click"></Button>  
    87.         </StackPanel>  
    88.     </Grid>  
    89. </Window>  

    对应的MainWindow.xaml.cs代码为:

    [csharp]  view plain  copy
    1. using System;  
    2. using System.Collections.Generic;  
    3. using System.Linq;  
    4. using System.Text;  
    5. using System.Windows;  
    6. using System.Windows.Controls;  
    7. using System.Windows.Data;  
    8. using System.Windows.Documents;  
    9. using System.Windows.Input;  
    10. using System.Windows.Media;  
    11. using System.Windows.Media.Imaging;  
    12. using System.Windows.Navigation;  
    13. using System.Windows.Shapes;  
    14.   
    15. namespace MazeAnimation  
    16. {  
    17.   
    18.   
    19.   
    20.     /// <summary>  
    21.     /// Interaction logic for MainWindow.xaml  
    22.     /// </summary>  
    23.     public partial class MainWindow : Window  
    24.     {  
    25.         public struct Point  
    26.         {  
    27.             public int x;  
    28.             public int y;  
    29.             public Point(int a, int b) { x = a; y = b; }  
    30.         };  
    31.   
    32.         public bool bAutoRun = true;  
    33.         public int mazeHeight = 10;  
    34.         public int mazeWidth = 10;  
    35.   
    36.         int[,] mazeData = new int[10, 10]  
    37.             {  
    38.                 {0,0,1,1,1,1,1,1,1,1}, //0  
    39.                 {1,0,0,1,1,0,0,1,0,1}, //1  
    40.                 {1,0,0,1,0,0,0,1,0,1}, //2  
    41.                 {1,0,0,0,0,1,1,0,0,1}, //3  
    42.                 {1,0,1,1,1,0,0,0,0,1}, //4  
    43.                 {1,0,0,0,1,0,0,0,0,1}, //5  
    44.                 {1,0,1,0,0,0,1,0,0,1}, //6  
    45.                 {1,0,1,1,1,0,1,1,0,1}, //7  
    46.                 {1,1,0,0,0,0,0,0,0,0}, //8  
    47.                 {1,1,1,1,1,1,1,1,1,0}  //9  
    48.             //   0 1 2 3 4 5 6 7 8 9  
    49.             };  
    50.   
    51.         public int enterX = 0;  
    52.         public int enterY = 0;  
    53.         public int exitX = 9;  
    54.         public int exitY = 9;  
    55.         public int runSpeed = 100;  
    56.   
    57.         public int paths = 0; //总条数  
    58.         public Stack<Point> path = new Stack<Point>(); //一条找到的路径  
    59.         public Stack<Point> bestPath = new Stack<Point>();//最优路径  
    60.         public bool bFrist = true;  
    61.   
    62.   
    63.         public MainWindow()  
    64.         {  
    65.             InitializeComponent();  
    66.         }  
    67.   
    68.         //显示迷宫,白色0表示通道,红色1表示不可走,黄色2表示最优的路径,绿色3表示已经走过的路径  
    69.         private void DisplayMaze()  
    70.         {  
    71.             gdMaze.Children.Clear();  
    72.             //设置可走和不可走  
    73.             for (int i = 0; i < mazeHeight; i++)  
    74.             {  
    75.                 for (int j = 0; j < mazeWidth; j++)  
    76.                 {  
    77.                     Rectangle rect = new Rectangle();  
    78.                     rect.SetValue(Grid.RowProperty, i);  
    79.                     rect.SetValue(Grid.ColumnProperty, j);  
    80.   
    81.                     if (mazeData[i, j] == 0)  
    82.                     {  
    83.                         rect.Fill = Brushes.White;  
    84.                     }  
    85.                     else if (mazeData[i, j] == 1)  
    86.                     {  
    87.                         rect.Fill = Brushes.Red;  
    88.                     }  
    89.                     else if (mazeData[i, j] == 2)  
    90.                     {  
    91.                         rect.Fill = Brushes.Yellow;  
    92.                     }  
    93.                     else if (mazeData[i, j] == 3)  
    94.                     {  
    95.                         rect.Fill = Brushes.Blue;  
    96.                     }  
    97.                     gdMaze.Children.Add(rect);  
    98.                 }  
    99.             }  
    100.         }  
    101.   
    102.         //初始化迷宫  
    103.         private void InitMaze()  
    104.         {  
    105.   
    106.             gdMaze.Background = Brushes.LightGray;  
    107.             gdMaze.ShowGridLines = true;  
    108.   
    109.             for (int i = 0; i < mazeHeight; i++)  
    110.             {  
    111.                 gdMaze.RowDefinitions.Add(new RowDefinition());  
    112.             }  
    113.   
    114.             for (int i = 0; i < mazeWidth; i++)  
    115.             {  
    116.                 gdMaze.ColumnDefinitions.Add(new ColumnDefinition());  
    117.             }  
    118.   
    119.             DisplayMaze();  
    120.         }  
    121.   
    122.         //从(x,y)位置开始走;初始为(0,0)  
    123.         private void MazeTrack(int x, int y)  
    124.         {  
    125.             ///  
    126.             //当前点加入到路径  
    127.             Point p = new Point(x, y);  
    128.             path.Push(p);  
    129.   
    130.             mazeData[x, y] = 3;         //设置为已走,不可走             
    131.             //DisplayMaze();  
    132.             //System.Threading.Thread.Sleep(runSpeed);//休眠  
    133.   
    134.   
    135.             ///  
    136.             //如果该位置是出口,输出结果  
    137.             if (x == exitX && y == exitY)  
    138.             {  
    139.                 string msg = "找到一条道路(逆序)\n";  
    140.                 tbLog.AppendText(msg);  
    141.   
    142.                 paths++;  
    143.   
    144.                 //输出路径  
    145.                 foreach (Point pnt in path)  
    146.                 {  
    147.                     msg = "(" + pnt.x + "," + pnt.y + ")";  
    148.                     tbLog.AppendText(msg);  
    149.                 }  
    150.                 tbLog.AppendText("\n\n");  
    151.   
    152.                 //判断是否更优  
    153.                 if (bFrist)//如果是找到的第一条路径,直接复制到最优路径  
    154.                 {  
    155.                     foreach (Point pnt in path)  
    156.                     {  
    157.                         bestPath.Push(pnt);  
    158.                     }  
    159.   
    160.                     bFrist = false;  
    161.                 }  
    162.                 else //不是第一条,则判断是否更短  
    163.                 {  
    164.                     //更短,复制到最优路径  
    165.                     if (path.Count < bestPath.Count)  
    166.                     {  
    167.                         bestPath.Clear();  
    168.                         foreach (Point pnt in path)  
    169.                         {  
    170.                             bestPath.Push(pnt);  
    171.                         }  
    172.                     }  
    173.                 }  
    174.             }  
    175.   
    176.             ///  
    177.             //判断(x,y)位置的上、下、左、右是否可走  
    178.   
    179.             if ((x - 1) >= 0 && mazeData[x - 1, y] == 0)//上(x-1,y);存在且可走  
    180.             {  
    181.                 MazeTrack(x - 1, y);  
    182.             }  
    183.   
    184.             if ((x + 1) < mazeHeight && mazeData[x + 1, y] == 0)//下(x+1,y);存在且可走  
    185.             {  
    186.                 MazeTrack(x + 1, y);  
    187.             }  
    188.   
    189.             if ((y - 1) >= 0 && mazeData[x, y - 1] == 0)//左(x,y-1);存在且可走  
    190.             {  
    191.                 MazeTrack(x, y - 1);  
    192.             }  
    193.   
    194.             if ((y + 1) < mazeWidth && mazeData[x, y + 1] == 0)//右(x,y+1);存在且可走  
    195.             {  
    196.                 MazeTrack(x, y + 1);  
    197.             }  
    198.   
    199.             ///  
    200.             //返回上一步  
    201.             path.Pop();  
    202.             mazeData[x, y] = 0;         //设置为未走  
    203.   
    204.             //DisplayMaze();  
    205.             //System.Threading.Thread.Sleep(runSpeed);//休眠  
    206.         }  
    207.   
    208.   
    209.         private void Window_Loaded(object sender, RoutedEventArgs e)  
    210.         {  
    211.             //初始化变量  
    212.             tbMazeHeight.Text = mazeHeight.ToString();  
    213.             tbMazeWidth.Text = mazeWidth.ToString();  
    214.             tbEnterX.Text = enterX.ToString();  
    215.             tbEnterY.Text = enterY.ToString();  
    216.             tbExitX.Text = exitX.ToString();  
    217.             tbExitY.Text = exitY.ToString();  
    218.   
    219.             cbAutoRun.IsChecked = bAutoRun;  
    220.             tbAutoRunSpeed.Text = runSpeed.ToString();  
    221.   
    222.             //初始化迷宫  
    223.             InitMaze();  
    224.         }  
    225.   
    226.         //点击开始  
    227.         private void btnStart_Click(object sender, RoutedEventArgs e)  
    228.         {  
    229.             string msg = "开始走迷宫\n";  
    230.             tbLog.AppendText(msg);  
    231.             MazeTrack(enterX, enterY);  
    232.   
    233.             //显示最优的路径  
    234.             msg = "\n可行路径总条数为" + paths + "\n最优路径为\n";  
    235.             tbLog.AppendText(msg);  
    236.   
    237.             foreach (Point pnt in bestPath)  
    238.             {  
    239.                 msg = "(" + pnt.x + "," + pnt.y + ")";  
    240.                 tbLog.AppendText(msg);  
    241.   
    242.                 mazeData[pnt.x, pnt.y] = 2;  
    243.   
    244.             }  
    245.             DisplayMaze();  
    246.         }  
    247.   
    248.         //下一步  
    249.         private void btnNext_Click(object sender, RoutedEventArgs e)  
    250.         {  
    251.             string msg = "手动开始走迷宫 暂未实现\n";  
    252.             tbLog.AppendText(msg);  
    253.         }  
    254.   
    255.     }  
    256. }  



    参考文献: 《计算机算法设计与分析》(王晓东)


    转载本文请注明作者和出处

    作者 :JarvisChu

    出处:http://blog.csdn.net/jarvischu


    展开全文
  • 求解思想:而化小 1、问题拆分成子问题 2、对子问题求解 在汉诺塔游戏中,有三个分别命名为A、B、C得塔座,几个大小各不相同,从小到一次编号得圆盘,每个原盘中间有一个小孔。最初,所有得圆盘都在A塔座上,...

    求解思想:大而化小

    1、问题拆分成子问题

    2、对子问题求解

    在汉诺塔游戏中,有三个分别命名为A、B、C得塔座,几个大小各不相同,从小到大一次编号得圆盘,每个原盘中间有一个小孔。最初,所有得圆盘都在A塔座上,其中最大得圆盘在最下面,然后是第二大,以此类推.

    先上代码

    #include<iostream>
    using namespace std;
    class Move
    {
    public:
    	void moveGo(int i, int a, int b, int c);
    	void display(int i, int a, int b);
    private:
    	static int count;
    };
    int Move::count = 1;
    
    void Move::moveGo(int i, int a, int b, int c)
    {
    	if (1 == i)
    	{
    		display(1, a, b);
    	}
    	else
    	{
    		moveGo(i - 1, a, c, b);
    		display(i, a, b);
    		moveGo(i - 1, c, b, a);
    	}
    }
    void Move::display(int i, int a, int b)
    {
    	printf("第 %d 步:移动第 %d 个塔从 %d 根柱子到 %d 根柱子\n", count,i, a, b);
    	count++;
    }
    int main()
    {
    	Move mo;
    	mo.moveGo(4,1,2,3);
    	cout << endl;
    	system("pause");
    	return 0;
    }

    核心代码

    void Move::moveGo(int i, int a, int b, int c)
    {
    	if (1 == i)
    	{
    		display(1, a, b);
    	}
    	else
    	{
    		moveGo(i - 1, a, c, b);
    		display(i, a, b);
    		moveGo(i - 1, c, b, a);
    	}
    }

    思想:

    1. 如果只有1个塔,那么把这个塔直接从a移动到  display(1, a, b);
    2. 如果有n个塔,把n-1个从a移动到c                    moveGo(i - 1, a, c, b);
    3. 然后把剩下的一个从a移动到b                           display(i, a, b);
    4. 最后把n-1个从c移动到b                                    moveGo(i - 1, c, b, a);

    这样问题就已经求解完了

    展开全文
  • 五大常用算法详解

    千次阅读 2018-04-26 09:59:11
    即最优子结构分解后的小问题解可以合并为原问题的解小问题之间互相独立实例二分查找快速排序合并排序整数乘法循环赛日程表动态划分算法基本思想将问题分解为多个子问题(阶段),按顺序求解,前一个问题的解为后一...
  • 五大常用算法(一) - 分治算法

    千次阅读 2018-10-16 10:37:50
    分治法的设计思想是:将一个难以直接解决的问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。 分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其...
  • (java)五大常用算法

    万次阅读 多人点赞 2018-08-31 10:50:15
    算法一:分治法 基本概念 1.把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。 2.分治策略是对于一个规模...
  • 五大常用算法学习笔记

    万次阅读 多人点赞 2019-02-26 21:52:52
    分治算法:快速排序、归并排序、整数乘法、二分查找、递归(汉诺塔) 基本概念:把一个复杂的问题分成若干个相同或相似的子问题,再把子问题分成更小的子问题… , 知道最后子问题可以简单的直接求解,原问题的解...
  • 五大常用算法——贪心算法详解及经典例子

    万次阅读 多人点赞 2018-02-08 15:07:22
    贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对...
  • 五大常用算法——分治算法详解及经典例题

    万次阅读 多人点赞 2018-03-12 16:36:15
    一、基本概念 在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接...
  • 一、对比回溯法回溯法的求解目标是找出解空间中满足约束条件的所有解,想必之下,分支限界法的求解目标则是找出满足约束条件的一个解,或是满足约束条件的解中找出使某一目标函数值达到极或极小的解,即在某种意义...
  • 首页专题下载手机应用 显示模式登录    注册 登录 ...五大常用算法一(回溯,随机化,动态规划) 字数11045 阅读178 评论0 喜欢6 回溯算法 回溯法:也称为试探法,它并不考虑问题
  • hadoop常用算法简单实例

    千次阅读 2016-01-18 19:26:49
    实例一、对以下数据进行排序,根据收入减去支出得到最后结余从到小排序,数据如下: SumStep运行之后结果如下: SortStep运行之后结果为上图根据结余从到小排序。 代码如下: public class InfoBean ...
  • 常用算法理解

    千次阅读 2017-10-13 16:30:20
    分治法:将问题实例划分成几个较小的子问题(可以递归的划分),然后对这些较小的子问题求解,合并这些较小的子问题,以得到原始问题的解。 有点类似Map/Reduce思想。主要区别在于:Map/Reduce的关键是把一个的...
  • 算法总结---最常用五大算法算法题思路) 一、总结 一句话总结: 【明确所求:dijkstra是求点到点的距离,辅助数组就是源点到目标点的数组】 【最简实例分析:比如思考dijkstra:假设先只有三个点】 1、...
  • 0. 常用算法概述1. 常用遍历算法1.1 for_each1.2 transform 0. 常用算法概述 算法主要是由头文件<algorithm>、 <functional> 、<numeric>组成; <algorithm>是所有STL头文件中最大的一个,...
  • 来源:数据与算法之美本文共2000字,建议阅读8分钟。本文仅用图解,为你介绍十大常用算法及其在分类问题中的应用实例。通过本篇文章大家可以对ML的常用算法形成常识性的认识。...
  • 常用算法整合

    千次阅读 2016-10-21 13:57:31
    常用算法
  • 6. 常用集合算法6.1 set_intersection6.2 set_union6.3 set_difference 6. 常用集合算法   学习目标: 掌握常用的集合算法。   算法简介: set_intersection    // 求两个容器的交集 set_union    // 求两...
  • 3. 常用排序算法3.1 sort3.2 random_shuffle3.3 merge5.3.4 reverse 3. 常用排序算法   学习目标: 掌握常用的排序算法。   算法简介: sort    //对容器内元素进行排序 random_shuffle    //洗牌,对指定...
  • 模糊控制算法实例解析(含代码)

    万次阅读 多人点赞 2017-02-22 19:45:51
    首先来看一个实例,控制进水阀S1和出水阀S2,使水箱水位保持在目标水位O处。按照日常操作经验,有以下规则:1、 若当前水位高于目标水位,则向外排水,差值越,排水越快;2、 若当前水位低于目标水位,则向内...
  • 常用算法设计方法

    千次阅读 2011-12-27 17:48:10
    常用算法设计方法 要使计算机能完成人们预定的工作,首先必须为如何完成预定的工作设计一个算法,然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述,其中程序的数据结构和变量...
  •  《Java常用算法手册》旨在帮助Java语言初级程序员深入了解Java算法思想,提升其语言代码编程能力,还可以作为中专院校学生学习数据结构和算法的参考书,也可为教师授课提供素材,同时还可以作为具有一定编程经验...
  • java 常用算法和时间复杂度

    千次阅读 2016-03-01 10:12:51
    由于下半年要准备工作了,也知道排序算法的重要性(据说是面试必问的知识点),所以又花了点时间重新研究了一下。  排序的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,...
  • 3.1 常用算法思想概述 3.2 穷举算法思想 3.2.1 穷举算法基本思想 3.2.2 穷举算法实例 3.3 递推算法思想 3.3.1 递推算法基本思想 3.3.2 递推算法实例 3.4 递归算法思想 3.4.1 递归算法基本思想 3.4.2 递归算法实例 ...
  • 卡尔曼滤波是一种利用线性系统状态方程,通过系统输入输出观测数据,对系统状态进行最优估计的算法。是目前应用最为广泛的滤波方法, 在通信, 导航, 制导与控制等多领域得到了较好的应用。 卡尔曼滤波本身是贝叶斯...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 69,582
精华内容 27,832
热门标签
关键字:

五大常用算法实例