穷举法定义及示例

2024-07-05 21:49| 来源: 网络整理| 查看: 265

定义

穷举法是算法设计中经常使用的一种方法，基本思想是问题的要求将问题的所有可能的输入一一进行验证，看是否满足问题的条件，从而找到可能的解。问题解有三种情况：有多个解，单个解或无解。穷举法又名枚举法，暴力破解法等。使用数学进行表示如下： Y = F ( X ) ∈ R , w h e r e   X ∈ D . \quad \quad Y=\mathrm{F}(X) \in \mathbb{R} \mathrm{, where} \:X \in \mathbb{D}. Y=F(X)∈R,whereX∈D.

此式中：

X X X 为问题的输入，其取舍范围定义域为 D \mathbb{D} D; Y Y Y为问题的解，即所要达到的目标； F F F 为问题的解决算法，即 F : X → Y F\!: \!X \rightarrow Y F:X→Y; R \R R 为解空间，当 R = ∅ \R = \empty R=∅ 时，问题无解。使用条件

使用穷举法对所有可能的输入进行测试，因此需要花很多的时间。要让其在可以接受的时间范围内解决问题，需要考虑以下三个条件：

定义域范围定义域 D \mathbb{D} D必需是有限的，或者可以看作有限。有限的范围不能太大。举例来说，15X15的棋盘的五子棋的所有输入可能为 225! 种，约为 1.26 × 1 0 + 433 1.26\times10^{+433} 1.26×10+433。优化水平优化是指将定义域中一些明显不可能的输入在穷举前删除，如五子棋中，第一步是不可能走四边的，这样第一步剩下的格子 (225 - 58) = 167，从而解空间下降了 58/225 = 25.78%。如果再考虑外围两圈，又可以再多减少54个格子，即只要考试113个格子，这样总空间变成了 113 × 254 113\times254 113×254! ，这样解空间基本下降了一半。运算能力即计算机的运算能力，现在计算机性能越来越强大，而且还可以多台进行联合工作进行并行计算，如在 2019.3.14，谷歌使用 25 虚拟机器用了121天，计算了31.4万亿位的PI。示例1：鸡兔同笼问题

问题：一个笼子有35个头，94只脚，问鸡和兔各有多少？分析：设鸡x只，免y只，其中 x + y = 35, 2x+4y=94。根据题目可以得到x和y的定义域为 x ∈ [ 0 , 35 ] x\in[0,35] x∈[0,35], y ∈ [ 0 , 35 ] y\in[0,35] y∈[0,35] 优化：由于 23< 94/4 < 24，所以 y 的值域可取得 y ∈ [ 0 , 24 ] y\in[0,24] y∈[0,24]。根据以上分析，使用java编码如下：

public static void main(String[] args) { for(int x = 0; x

【本文地址】

穷举法定义及示例

穷举法定义及示例

今日新闻

推荐新闻