【数据结构与算法之穷举法】穷举法的基本思想

清疚 2024-03-25 16:39 92阅读 0赞

#### 【数据结构与算法之穷举法】穷举法的基本思想 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之穷举法】穷举法的基本思想

穷举法，是使用最广泛、设计最简单、同时最耗时的算法，也称为暴力法、蛮力法。

【穷举法基本思想】在问题的解空间中穷举每一种可能的解，并对每一种可能的解进行判断，从中找出答案。

【使用穷举法的注意事项】

1.  划定的解空间必须覆盖问题的全部解，否则这个解空间是不完备的；
2.  解空间集合一定是离散集合。`或者说集合中的元素数量必须是有限的、可列的`

只要划定了正确的解空间，就可以按照一定的步骤搜索这个解空间，并将解空间中的可能解穷举出来。

举个栗子：题目`两数之和`

题目描述：给定一个整数数组array 和一个目标值target，请在该数组中找出和为目标值target 的两个整数，并输出它们在数组array 中的下标。

> 在数组中找，一个元素不能重复使用，当然也可能无解

`示例`

array = \{1,3,5,7,9,2,4,6,8,0\}，target = 15

`结果`array\[3\] + array\[8\] = 15 ; array\[4\] + array\[7\] = 15。

假设需要寻找的数组元素下标为index\_1 和index\_2，数组长度为length，则index\_1 和 index\_2 的取值范围分别是 0 ≤ index\_1 ≤ length -1 ，0 ≤ index\_2 ≤ length -1，同时index\_1 ≠ index\_2

所以本题的解空间为：\{index\_1, index\_2 | index\_1 ∈ \[0, length - 1\], index\_2 ∈ \[0, length - 1\] , index\_1 ≠ index\_2\}

Java实现代码：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: SumOfTwoNumbers
     * @Author: Ding Jiaxiong
     * @Data:2023/3/14 14:48
     */
    
    public class SumOfTwoNumbers {
        
    
        public static void outupIndexOfArray(int[] array, int target) {
        
    
            boolean haveSolution = false;
    
            for (int index_1 = 0; index_1 < array.length; index_1++) {
        
                for (int index_2 = 0; index_2 < array.length; index_2++) {
        
                    if (index_1 != index_2 && (array[index_1] + array[index_2] == target)) {
        
                        // 找到一个解，输出
                        System.out.println("array[" + index_1 + "] + " + "array[" + index_2 + "] = " + target);
                        haveSolution = true;
                    }
                }
            }
    
            if (!haveSolution) {
        
                System.out.println("无解");
            }
        }
    
        public static void main(String[] args) {
        
    
            int[] array = {
        1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
            int target = 15;
            outupIndexOfArray(array, target);
    
        }
    
    }

运行结果

![在这里插入图片描述][69cc7193bacb4120bc2933df01aa26d1.png_pic_center]

其实可以发现，好像第1个结果和第4个结果是相同的，第2个和第3个结果也是相同，这很容易想明白，因为我们的解空间中包含了重复的解。

![在这里插入图片描述][a09071c3f2b74e5a80140a9c7d0c854d.png_pic_center]

在代码实现上，我们只要将内层循环变量index\_2 的起始值从原来的0 改为index\_1 + 1，就可以将解空间的大小缩小为原来的一半了，同时也不用再判断index\_1 是否等于index\_2。

改进实现：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: SumOfTwoNumbers
     * @Author: Ding Jiaxiong
     * @Data:2023/3/14 14:48
     */
    
    public class SumOfTwoNumbers {
        
    
        public static void outupIndexOfArray(int[] array, int target) {
        
    
            boolean haveSolution = false;
    
            for (int index_1 = 0; index_1 < array.length; index_1++) {
        
                for (int index_2 = index_1 + 1; index_2 < array.length; index_2++) {
        
                    if (index_1 != index_2 && (array[index_1] + array[index_2] == target)) {
        
                        // 找到一个解，输出
                        System.out.println("array[" + index_1 + "] + " + "array[" + index_2 + "] = " + target);
                        haveSolution = true;
                    }
                }
            }
    
            if (!haveSolution) {
        
                System.out.println("无解");
            }
        }
    
        public static void main(String[] args) {
        
    
            int[] array = {
        1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
            int target = 15;
            outupIndexOfArray(array, target);
    
        }
    
    }

运行结果

![在这里插入图片描述][2d754d4c2b86421c95579c9d424cb146.png_pic_center]

> 【最后】
> 
> 在应用穷举法解决问题时，关键是划定好问题的解空间
> 
>  *  如果解空间过大，那么不但会增加冗余的搜索操作，还可能导致得到的结果重复
>  *  如果过小，可能会漏解，进而违背穷举法牺牲时间换取解的全面性的初衷

[69cc7193bacb4120bc2933df01aa26d1.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/766abec0ebc14efd9483f515cf2b2991.png
[a09071c3f2b74e5a80140a9c7d0c854d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8da0d28c0fd04c17b4ac126d7ada1b5b.png
[2d754d4c2b86421c95579c9d424cb146.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/66b68ed8ef4c44da88eeac2e3b89b91c.png