【软件设计师】常见的算法设计方法——穷举搜索法

2024-03-07 11:44

本文主要是介绍【软件设计师】常见的算法设计方法——穷举搜索法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 🐓 穷举搜索法

什么是穷举搜索法

穷举搜索法,又称枚举法穷举法,是一种编程中常用到的问题求解方法。当找不到解决问题的规律时,穷举搜索法会对可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从中找出那些符合要求的候选解作为问题的解。

穷举搜索法的基本思想是列举出所有可能的情况,逐个判断哪些情况符合问题所要求的条件,从而得到问题的全部解答。这种方法利用计算机运算速度快、精确度高的特点,对要解决问题的所有可能情况,一个不漏地进行检查,从中找出符合要求的答案。

穷举搜索法的基本场景

穷举搜索法的基本场景通常涉及以下两个方面:

问题所涉及的情况:在穷举搜索法中,首先需要明确问题所涉及的所有可能情况。这些情况的种数必须可以确定,并且需要被一一列举出来。既不能重复,也不能遗漏。例如,如果问题是求解一个特定数学方程的所有整数解,那么就需要列举出所有可能的整数,并检查哪些整数满足方程的条件。

答案需要满足的条件:在列举出所有可能的情况后,需要分析这些情况需要满足什么条件才能成为问题的答案。这些条件可能包括数学公式、逻辑关系、约束条件等。例如,在求解数学方程的情况下,答案需要满足方程等于零的条件。

穷举搜索法的基本原理

穷举搜索法的基本原理是通过列举所有可能的情况来找到满足特定条件的解。这种方法基于这样一个概念:如果一个问题的解空间是有限的,那么通过逐一检查每一个可能的解,最终一定能够找到所有满足条件的解。

算法设计——穷举搜索法

 🐓 代码实例解析

设计思路

使用穷举法解决问题,基本上就是以下两个步骤:

确定问题的解(或状态)的定义、解空间的范围以及正确解的判定条件;

根据解空间的特点来选择搜索策略,逐个检验解空间中的候选解是否正确;

 解空间(范围内找解)

解空间就是全部可能的候选解的一个约束范围,确定问题的解就在这个约束范围内,将搜索策略应用到这个约束范围就可以找到问题的解。

剪枝策略

对解空间穷举搜索时,如果有一些状态节点可以根据问题提供的信息明确地被判定为不可能演化出最优解,也就是说,从此节点开始遍历得到的子树,可能存在正确的解,但是肯定不是最优解,就可以跳过此状态节点的遍历,这将极大地提高算法的执行效率,这就是剪枝策略,应用剪枝策略的难点在于如何找到一个评价方法(估值函数)对状态节点进行评估。

案例1

鸡兔同笼问题。有鸡和兔在一个笼子中,数头共 50 个头,数脚共 120 只脚,问:鸡和兔分别有多少只?

情况一:盲目搜索

假设买 x 鸡,y 只兔,使用代码求解如下:

for x in range(1, 51):for y in range(1, 51):if x + y == 50 and 2*x + 4*y == 120:print x, y
情况二:启发搜索

假设买 x 鸡,y 只兔,使用代码求解如下:

for x in range(1, 51):if 2*x + 4*(50-x) == 120:print x, 50-x

案例2

找出给定整数数组中所有可能的两个数之和的组合

import java.util.ArrayList;  
import java.util.List;  public class ExhaustiveSearchExample {  public static void main(String[] args) {  int[] numbers = {1, 2, 3, 4, 5};  List<int[]> allSumCombinations = findAllSumCombinations(numbers, 10);  for (int[] combination : allSumCombinations) {  System.out.println("(" + combination[0] + ", " + combination[1] + ")");  }  }  public static List<int[]> findAllSumCombinations(int[] numbers, int targetSum) {  List<int[]> combinations = new ArrayList<>();  for (int i = 0; i < numbers.length; i++) {  for (int j = i + 1; j < numbers.length; j++) {  if (numbers[i] + numbers[j] == targetSum) {  combinations.add(new int[]{numbers[i], numbers[j]});  }  }  }  return combinations;  }  
}

代码运行结果及解释

(1, 9)  
(2, 8)  
(3, 7)  
(4, 6)  
(5, 5)

findAllSumCombinations方法使用了两层循环来穷举数组中所有可能的数对。对于每一对数(numbers[i]numbers[j]),它检查它们的和是否等于targetSum。如果等于,它就将这对数添加到一个列表中。最后,该方法返回这个列表,其中包含了所有满足条件的数对。 

 🐓 穷举搜索法的优缺点及注意事项

穷举搜索法的优点

直观易懂:穷举搜索法通常基于问题的直接描述,易于理解和实现。

正确性保证:由于穷举搜索法会检查所有可能的解,因此它能够确保找到问题的最优解(如果存在的话)。

适用性广泛:这种方法适用于许多问题,特别是那些没有更简单或更有效算法可用的问题。

穷举搜索法的缺点

计算量大:穷举搜索法需要检查所有可能的解,因此计算量通常很大,尤其是在问题规模较大时。

效率低下:由于需要检查大量解,穷举搜索法通常非常耗时,可能在现实应用中不可行。

资源消耗多:在处理大规模问题时,穷举搜索法可能需要大量的内存和计算资源。

使用穷举搜索法需要注意的问题

问题规模:在使用穷举搜索法之前,需要仔细评估问题的规模。如果问题规模太大,穷举搜索法可能不是一个好选择。

优化技巧:尽管穷举搜索法本身可能效率低下,但可以通过一些优化技巧(如剪枝、排序、哈希等)来减少计算量和提高效率。

利用问题特性:在某些情况下,可以利用问题的特性(如对称性、单调性等)来减少搜索空间或优化搜索过程。

考虑其他算法:如果穷举搜索法不切实际,可能需要考虑使用其他更高效的算法来解决问题

 🐓 LeetCode练习传送门

1. 两数之和 - 力扣(LeetCode):给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回它们的数组下标。

LCR 083. 全排列 - 力扣(LeetCode):给定一个没有重复数字的数组,返回其所有可能的全排列。

LCR 081. 组合总和 - 力扣(LeetCode):给定一个无重复元素的数组 candidates 和一个目标数 target,找出 candidates 中所有可以使数字和为 target 的组合。

LCR 033. 字母异位词分组 - 力扣(LeetCode):给定一个字符串数组,将字母异位词组合到一起。字母异位词指字母相同,但排列不同的字符串。

91. 解码方法 - 力扣(LeetCode):给定一个经过编码的字符串,返回它有多少种解码方法。

这篇关于【软件设计师】常见的算法设计方法——穷举搜索法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/783395

相关文章

QT移植到RK3568开发板的方法步骤

《QT移植到RK3568开发板的方法步骤》本文主要介绍了QT移植到RK3568开发板的方法步骤,文中通过图文示例介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录前言一、获取SDK1. 安装依赖2. 获取SDK资源包3. SDK工程目录介绍4. 获取补丁包二

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

java导出pdf文件的详细实现方法

《java导出pdf文件的详细实现方法》:本文主要介绍java导出pdf文件的详细实现方法,包括制作模板、获取中文字体文件、实现后端服务以及前端发起请求并生成下载链接,需要的朋友可以参考下... 目录使用注意点包含内容1、制作pdf模板2、获取pdf导出中文需要的文件3、实现4、前端发起请求并生成下载链接使

Linux虚拟机不显示IP地址的解决方法(亲测有效)

《Linux虚拟机不显示IP地址的解决方法(亲测有效)》本文主要介绍了通过VMware新装的Linux系统没有IP地址的解决方法,主要步骤包括:关闭虚拟机、打开VM虚拟网络编辑器、还原VMnet8或修... 目录前言步骤0.问题情况1.关闭虚拟机2.China编程打开VM虚拟网络编辑器3.1 方法一:点击还原VM

Android WebView无法加载H5页面的常见问题和解决方法

《AndroidWebView无法加载H5页面的常见问题和解决方法》AndroidWebView是一种视图组件,使得Android应用能够显示网页内容,它基于Chromium,具备现代浏览器的许多功... 目录1. WebView 简介2. 常见问题3. 网络权限设置4. 启用 JavaScript5. D

Java捕获ThreadPoolExecutor内部线程异常的四种方法

《Java捕获ThreadPoolExecutor内部线程异常的四种方法》这篇文章主要为大家详细介绍了Java捕获ThreadPoolExecutor内部线程异常的四种方法,文中的示例代码讲解详细,感... 目录方案 1方案 2方案 3方案 4结论方案 1使用 execute + try-catch 记录

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

SpringBoot项目启动错误:找不到或无法加载主类的几种解决方法

《SpringBoot项目启动错误:找不到或无法加载主类的几种解决方法》本文主要介绍了SpringBoot项目启动错误:找不到或无法加载主类的几种解决方法,具有一定的参考价值,感兴趣的可以了解一下... 目录方法1:更改IDE配置方法2:在Eclipse中清理项目方法3:使用Maven命令行在开发Sprin

JAVA SE包装类和泛型详细介绍及说明方法

《JAVASE包装类和泛型详细介绍及说明方法》:本文主要介绍JAVASE包装类和泛型的相关资料,包括基本数据类型与包装类的对应关系,以及装箱和拆箱的概念,并重点讲解了自动装箱和自动拆箱的机制,文... 目录1. 包装类1.1 基本数据类型和对应的包装类1.2 装箱和拆箱1.3 自动装箱和自动拆箱2. 泛型2

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.