算法——深度优先搜索（DFS）

柔光的暖阳◎ 2024-01-30 06:36 18阅读 0赞

> ## DFS ##
> 
>  *  思路：
>     
>      *  从初始状态出发，下一步可能有多种状态；选其中一个状态深入，到达新的状态；**直到无法继续深入，回退到前一步，**转移到其他状态，然后再深入下去。最后，遍历完所有可以到达的状态，并得到最终的解。
>      *  DFS通常使用递归来实现
>  *  弊端：
>     
>      *  递归容易超时
>  *  **大部分DFS搜索的题目都需要用到回溯的思路，其难度主要在于扩展子结点时如何构造停止递归并返回的条件。**

> ## 递归 ##
> 
>  *  递归方法就是直接或间接地调用其自身
>  *  注意：
>     
>      *  避免进入死循环
>      *  容易超时
>         
>          *  递归 <——> 非递归，相互转化

> ## 回溯法 ##
> 
>  *  回溯法是一种采用深度优先方式进行搜索的算法，当搜索到某一步时，**如果发现原先的选择不是最优选择或者达不到目标，就退回一步重新选择。**
>  *  **剪枝函数：（在回溯中用于减少子结点扩展的函数）**
>     
>      *  1、约束函数：是问题的可行解吗？
>      *  2、限界函数：确定是问题的可行解，但，是问题的最优解吗？
>  *  解题步骤：
>     
>      *  1、如何递归
>      *  2、如何剪枝与回溯

## 一、计算阶乘（递归） ##

> 阶乘函数：![n!=\\left\\\{\\begin\{matrix\} 1 &,n=0 \\\\ n\\times (n-1)! & ,n> 0 \\end\{matrix\}\\right.][n_left_begin_matrix_ 1 _n_0 _ n_times _n-1_ _ _n_ 0 _end_matrix_right.]
> 
> 比如
> 
>  *  3！=6
>     
>      *  3！= 3\*2\*1 = 6
>  *  4！=24
>     
>      *  4！= 4\*3\*2\*1 = 24
>  *  5！=120
>     
>      *  5！= 5\*4\*3\*2\*1 = 120

> 分析：
> 
>  *  ![fcd24ff0f4784bee902a9c5d27d0e97b.jpeg][]

package no1_1;
    import java.util.Scanner;
    public class Main {
    	public static void main(String[] args) {
    		Scanner input = new Scanner(System.in);
    		int n = input.nextInt();
    		System.out.println(factorial(n));
    	}
    	public static int factorial(int n) {
    		if(n==0) {
    			return 1;
    		}else {
    			return n*factorial(n-1);
    		}
    	}
    }

## 二、数字游戏（回溯） ##

> 　　给定一个1～N的排列a\[i\]，每次将相邻两个数相加，得到新序列，再对新序列重复这样的操作，显然每次得到的序列都比上一次的序列长度少1，最终只剩一个数字。  
> 　　例如:  
> 　　3 1 2 4  
> 　　4 3 6  
> 　　7 9  
> 　　16  
> 　　现在如果知道N和最后得到的数字sum，请求出最初序列a\[i\]，为1～N的一个排列。若有多种答案，则输出字典序最小的那一个。数据保证有解。
> 
> ![111f5f158935449bbb17c1b650f7bfd3.png][]

> 分析：
> 
>  *  ![337f9593b8444cc1b335eea71299938a.jpeg][]
>  *  ![b0c831d938d14d279fb4a1ee6116d98c.jpeg][]

package no1_1;
    
    import java.util.Scanner;
     
    public class Main {
    	//main()方法是静态方法，它只能调用静态方法，所以dfs()也是静态方法
    	//因为两个方法都是静态方法，所以它们共用的属性sum,N等都得是静态的
    	static int sum;
    	static int N;
    	static int arr1[];
    	static boolean flag = true;
     
    	public static void main(String[] args) {
    		Scanner input = new Scanner(System.in);
    		N = input.nextInt();
    		sum = input.nextInt();
    		int array[] = new int[N];
    		int usedArray[] = new int[N + 1];
    		//开始递归
    		dfs(0, array, usedArray, flag);
    	}
     
    	public static void dfs(int step, int arr[], int usedArray[], Boolean flag) {
    		//首先检查当前步数是否等于N，如果是，则表示已经生成了一个完整的排列(最顶层，有N个数的数组)
    		if (step == N) {
    			//复制该排列到新数组中
    			int arr1[] = new int[N];
    			for (int i = 0; i < N; i++) {
    				arr1[i] = arr[i];
    			}
    			//从上往下，计算该排列最终得到的数字
    			for (int i = 1; i < N; i++) {
    				for (int j = 0; j < N - i; j++) {
    					arr1[j] = arr1[j] + arr1[j + 1];
    				}
    			}
    			//某排列计算出的数字与题目符合
    			if (arr1[0] == sum) {
    				//把该排列输出到控制台
    				for (int x : arr) {
    					System.out.print(x + " ");
    				}
    				//停止递归
    				flag = false;
    				//回溯，但不再递归
    				return;
     
    			} else
    				//条件不满足，
    				//回溯，继续递归生成下一步的排列
    				return;
    		}
    		//继续递归，生成可能的排列
    		if (flag == true) {
    			//最初序列arr[i]，为1～N的一个排列
    			//在递归生成排列时，使用usedArray数组来标记已经使用过的数字，避免重复使用
    			for (int i = 1; i <= N; i++) {
    				if (usedArray[i] == 0) {
    					arr[step] = i;
    					usedArray[i] = 1;
    					dfs(step + 1, arr, usedArray, flag);
    					usedArray[i] = 0;//取消标记
    				}
    			}
    		}
    		return;
    	}
    }

## 三、粘木棍（DFS） ##

> ![b8911158547143ac8edf3e5aa34b7654.png][]
> 
> ![774475b57af24b6bae05c9ceef1f8991.png][]

> 分析：
> 
>  *  ![27880badd4554bf5ae4ff7918d1a68a6.jpeg][]
>  *  ![6db5a00ee9b24ae7a0a87dfcee9db3a9.jpeg][]

package no1_1;
    import java.util.*;
    public class Main {
    	static int n,m,result=Integer.MAX_VALUE;
    	static int[] array;
        public static void main(String[] args) {
            Scanner input=new Scanner(System.in);
            n=input.nextInt();
            m=input.nextInt();
            array=new int[n];
            for(int i=0;i<n;i++) {
            	array[i]=input.nextInt();
            }
            dfs(n);
            System.out.println(result);
        }
        public static void dfs(int n) {
        	if(n==m) {//到达底部，先验证这次分组是否正确，如果不正确就回溯
                //不用Arrays.sort()方法找最大值和最小值，是为了方便回溯，如果随便改变了数组元素的顺序，就无法正常回溯了
        		int min=Integer.MAX_VALUE,max=Integer.MIN_VALUE;
        		for(int i=0;i<m;i++) {
        			if(array[i]<min) min=array[i];
        			if(array[i]>max) max=array[i];
        		}
        		result=Math.min(result, max-min);//维护一个最小的差值
        		return ;//停止递归，返回
        	}
        	for(int i=0;i<n;i++) {
        		for(int j=i+1;j<n;j++) {
        			array[i]+=array[j];//合并元素
        			swap(j,n-1);//将废弃的元素丢到数组后面
        			dfs(n-1);//数组长度减一
        			swap(j,n-1);//回溯，交换回来
        			array[i]-=array[j];//把合并的两个元素和拆开
        		}
        	}
        }
        //交换函数
        public static void swap(int a,int b) {
        	int temp=array[a];
        	array[a]=array[b];
        	array[b]=temp;
        }
    }

## 四、24点 ##

> ![3d56379000794c61904b2cb582517e15.png][]
> 
> ![ed663eb3f60743928b881f1b0a536044.png][]

> 分析：
> 
>  *  一组数据里有4个数字
>  *  递归，每次处理2个数字，加减乘除（加乘各自只有一种方法，而乘除各自有两种）
>  *  把处理结果存放在card\[1\]的位置，再把最后一个有效数字挪到card\[0\]的位置，数组有效数字长度-1
>  *  每种方法都维护一个不大于24的最大值
>  *  ![eac1e219ce994f6f897c8bea863a1bb8.jpeg][]

package no1_1;
    import java.util.*;
    public class Main {
    	static int max;
        public static void main(String[] args) {
            Scanner input=new Scanner(System.in);
            int n=input.nextInt();
            int[] cards=new int[4];
        	int[] res=new int[n];//存储结果
            for(int i=0;i<n;i++) {
            	//每次只取一组输入数据进行处理，处理完成，再接收下一组输入数据
            	for(int j=0;j<4;j++) {
            		cards[j]=input.nextInt();
            	}
            	max=0;
            	dfs(cards,4);
            	res[i]=max;
            }
            for(int i=0;i<n;i++) {
            	System.out.println(res[i]);
            }
        }
        public static void dfs(int cards[],int n) {
        	//维护一个不大于24的最大值
        	if(n==1) {
        		if(cards[n-1]<=24) {//最终结果保存在数组的第一个位置上，此时有效数据只有一个，其他都运算过舍弃了
            		max=Math.max(max, cards[n-1]);
        		}
        		return;
        	}
        	for(int i=0;i<n-1;i++) {
        		for(int j=i+1;j<n;j++) {
        			int a=cards[i],b=cards[j];
        			
        			//a+b=b+a，加法具有交换律
        			cards[j]=a+b;
        			cards[i]=cards[n-1];
        			dfs(cards,n-1);
        			//n数字，其中两个数字相处理后会导致j位置的数字被更新而i位置的数字无效，
    				//此时将最后一个数调到i位置，这样有效数字正好变成了前n-1个数字
        			
        			//a*b=b*a，乘法具有交换律
        			cards[j]=a*b;
        			cards[i]=cards[n-1];
        			dfs(cards,n-1);
        			
        			//减法不具有交换律
        			cards[j]=a-b;
        			cards[i]=cards[n-1];
        			dfs(cards,n-1);
        			
        			cards[j]=b-a;
        			cards[i]=cards[n-1];
        			dfs(cards,n-1);
        			
        			//除法不具有交换律
        			if(b!=0 && a%b==0) {//除数不能为0，且是整除时才可以除
        				cards[j]=a/b;
            			cards[i]=cards[n-1];
            			dfs(cards,n-1);
        			}
        			if(a!=0 && b%a==0) {
        				cards[j]=b/a;
            			cards[i]=cards[n-1];
            			dfs(cards,n-1);
        			}
        			//这两个数处理得不合适，恢复这两个数的原始状态
        			cards[i]=a;
        			cards[j]=b;
        		}
        	}
        	
        }
    }

[n_left_begin_matrix_ 1 _n_0 _ n_times _n-1_ _ _n_ 0 _end_matrix_right.]: https://latex.csdn.net/eq?n%21%3D%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%201%20%26%2Cn%3D0%20%5C%5C%20n%5Ctimes%20%28n-1%29%21%20%26%20%2Cn%3E%200%20%5Cend%7Bmatrix%7D%5Cright.
[fcd24ff0f4784bee902a9c5d27d0e97b.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/4c4b4c9aa18849ccb136ca0d2c4bf861.png
[111f5f158935449bbb17c1b650f7bfd3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/55d369166e9a492da7c4f8e46a794320.png
[337f9593b8444cc1b335eea71299938a.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/4d11da4f67d748e389fb63623f0effb2.png
[b0c831d938d14d279fb4a1ee6116d98c.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/482139c920e44ac59b009ef1a632b50c.png
[b8911158547143ac8edf3e5aa34b7654.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/a5e26252675d4563ad43783192b42fd1.png
[774475b57af24b6bae05c9ceef1f8991.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/f62978aff03342e2bb854e8cac07b3ab.png
[27880badd4554bf5ae4ff7918d1a68a6.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/97706704d6084f7899dd70591ee97bbb.png
[6db5a00ee9b24ae7a0a87dfcee9db3a9.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/a3d85fbbfff04a06a2de2a07b313927a.png
[3d56379000794c61904b2cb582517e15.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/d8708b88afb44cafae0b81d6886a1c30.png
[ed663eb3f60743928b881f1b0a536044.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/ef22e97a1e5b4a8ba7dc55c958569a3d.png
[eac1e219ce994f6f897c8bea863a1bb8.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/cce44ec041814679b29674c678fc6e73.png