栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

回溯法 DFS 全排列

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

回溯法 DFS 全排列

回溯法求全排列

  最近在写算法老师布置的作业,其中有一道题是:有一个含有n个整数的数组a,所有元素均不相同,求其所有元素的全排列,例如,a[ ]={1,2,3},得到的结果是(1,2,3),(1,3,2),(2,3,1),(2,1,3),(3,1,2),(3,2,1)。题目很简单,但却很好的体现出了回溯法的思想,所以想借由这个题目来作为回溯法的典型,方便以后复习。(●’◡’●)
  解:显然本问题的解空间为排列树,直接用数组a生成其排列,每个位置可取a中任何元素,但一个排列中的元素不能重复。为此采用元素交换的方式,对排列数的第i层,扩展状态是a[ i ]位置可以取a[ i ]到a[ n-1 ]的任何元素,即j=i到n-1循环:将a[i]与a[ j ]交换,在这种方式下求出排列后需要恢复,即将a[ i ]与a[ j ]再次交换,回到交换之前的状态(回溯),然后继续求其他排列。
  例如a[ ]={1,2,3}时求全排列的过程如图5.8所示。

图中的树就是对应的解空间树,这里数组a的下标从0开始,所以根节点“a={1,2,3}”的层次为0,它的子树分别对应a[ 0 ]位置选择a[ 0 ]、a[ 1 ]、a[ 2 ]元素。实际上,对于第i层的节点,其子树分别对应a[ i ]位置选择a[ i ]、a[ i+1 ]、… 、a[ n-1 ]元素。树的高度为n+1,叶子结点的层次是n,解空间树更清晰的描述如图5.9所示。

  从图5.9中可以看出,对于第i层的结点,其扩展仅仅考虑a[ i ]及以后的元素,而不必考虑前面已经选择的元素。例如第2层的“1,3,2”结点,不必考虑前面的“1,3”仅仅扩展a[ 2 ],即a[ 2 ]取值为从根结点的路径上设有取过的值2,产生“1,3,2”的解。
  对应的Java代码如下:

public class FullArray_3 {
    static int[] a;
    static int n;

    //输入数组a的元素个数(数字的个数)以及对数组赋值(各个数字的值)
    public void inPut(){
        Scanner read = new Scanner(System.in);
        System.out.println("请输入数字的个数");
        n = read.nextInt();
        a = new int[n];
        System.out.println("请分别输入各个数字的值");
        for (int i =0;i
        if (i>=n)                //终结条件: 当交换到最底层所有元素都确定时做输出
            disPlay(arr,n);      
        else {                          //当没有达到最底层时,进行元素交换并递归
            for (int j =i;j
                swap(arr,j,i);
                dfs(arr,n,i+1);
                swap(arr,j,i);    //一个数组确定后需要回溯到上一个状态再进行然后求其他排列,所以需要将元素交换回来
            }
        }

    }
    
    //输出
    public void disPlay(int[] arr,int n ){
        for (int i =0;i
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    public static void main(String[] args) {
        FullArray_3 f = new FullArray_3();
        f.inPut();
        f.dfs(a,n,0);
    }

}

  在代码的编写过程中,我在编写dfs方法的方法体时遗漏了esle关键字,导致方法在满足终结条件时仍进入了循环,因此线程一直存储dfs方法到栈堆中,从而使线程的堆栈大小超过分配的内存限制,发生StackOverFlowError。这提醒我们在编写程序时应该细心一点不能粗心大意。
 
 
 
 
 
           摆烂是形容有能力的人不作为,就我这两下子还摆啊,我不摆也很烂了/(ㄒoㄒ)/~~

 
 
 
 
 
 
  本文解中文字部分引用《算法与设计分析(第二版)》✨✨✨

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/937408.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号