共计 2548 个字符，预计需要花费 7 分钟才能阅读完成。
关注“Java 后端技术全栈”**
回复“面试”获取全套面试材料
穷举法又称 穷举搜寻法，是一种在问题域的解空间中对所有可能的解穷举搜寻，并依据条件抉择最优解的办法的总称。数学上也把穷举法称为枚举法，就是在一个由无限个元素形成的汇合中，把所有元素一一枚举钻研的办法。
穷举算法依赖于计算机的弱小计算能力来穷尽每一种可能的状况，从而达到求解的目标。穷举算法效率不高，但实用于一些没有显著法则可循的场合。
应用穷举法解决问题，基本上就是以下两个步骤：
• 确定问题的解（或状态）的定义、解空间的范畴以及正确解的断定条件；
• 依据解空间的特点来抉择搜寻策略，一一测验解空间中的候选解是否正确；
解空间的定义
解空间就是全副可能的候选解的一个束缚范畴，确定问题的解就在这个束缚范畴内，将搜寻策略利用到这个束缚范畴就能够找到问题的解。要确定解空间，首先要定义问题的解并建设解的数据模型。如果解的数据模型抉择谬误或不适合，则会导致解空间结构繁冗、范畴难以界定，甚至无奈设计穷举算法。
穷举解空间的策略
穷举解空间的策略就是搜索算法的设计策略，依据问题的类型，解空间的构造可能是线性表、汇合、树或者图，对于不同类型的解空间，须要设计与之相适应的穷举搜索算法。简略的问题能够用通用的搜索算法，比方线性搜索算法用于对线性解空间的搜寻，广度优先和深度优先的递归搜索算法实用于树型解空间或更简单的图型解空间。
自觉搜寻和启发式搜寻
对于线性问题的 自觉搜寻 ，就是把线性表中的所有算法依照肯定的程序遍历一遍，对于简单问题的自觉搜寻，罕用广度优先搜寻和深度优先搜寻这两种自觉搜索算法。如果搜寻可能智能化一点，利用搜寻过程中呈现的额定信息间接跳过一些状态，防止自觉的、机械式的搜寻，就能够放慢搜索算法的收敛，这就是 启发性搜寻。启发性搜寻须要一些额定信息和操作来“启发”搜索算法，依据这些信息的不同，启发的形式也不同。
剪枝策略
对解空间穷举搜寻时，如果有一些状态节点能够依据问题提供的信息明确地被断定为不可能演化出最优解，也就是说，从此节点开始遍历失去的子树，可能存在正确的解，然而必定不是最优解，就能够跳过此状态节点的遍历，这将极大地提高算法的执行效率，这就是剪枝策略，利用剪枝策略的难点在于如何找到一个评估办法（估值函数）对状态节点进行评估。特定的评估办法都附着在特定的搜索算法中，比方博弈树算法中罕用的极大极小值算法和“α-β”算法，都随同着相应的剪枝算法。
剪枝和启发
剪枝不是启发性搜寻。剪枝的原理是在后果曾经搜寻进去或局部搜寻进去（比方树的根节点曾经搜寻进去了，然而叶子节点还没有搜寻进去）的状况下，依据最优解的判断条件，确定这个方向上不可能存在最优解，从而放弃对这个方向的持续搜寻。而启发性搜寻通常是依据启发函数给出的评估值，在后果进去之前就朝着最可能呈现最优解的方向搜寻。它们的差别点在于是依据后果进行判断还是依据启发函数的评估值进行判断。
搜索算法的评估和收敛
收敛准则是只有能找到一个比拟好的解就返回（不求最好），依据解的评估判断是否须要持续下一次搜寻。大型棋类游戏通常面临这种问题，比方国际象棋和围棋的求解算法，想要搜寻整个解空间失去最优解目前是不可能的，所以此类搜索算法通常都通过一个搜寻深度参数来管制搜索算法的收敛，当搜寻到指定的深度时（相当于走了若干步棋）就返回以后曾经找到的最好的后果，这种退而求其次的策略也是不得已而为之。
简言之
穷举算法的根本思维就是从所有可能的状况中搜寻正确的答案，其执行步骤如下:
(1)对于一种可能的状况，计算其后果。
(2)判断后果是否满足要求，如果不满足则进行执行第 (1) 步来搜寻下一个可能的状况；如果满足要求，则示意寻找到一个正确的答案。
鸡兔同笼问题
鸡兔同笼问题最早记录于 1500 年前的《孙子算经》，这是我国现代一一个十分有名的问题。鸡兔同笼的原文如下: 今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何?
这个问题的大抵意思是:
在一个笼子里关着若干只鸡和若干只兔，从下面数共有 35 个头; 从上面数有 94 只脚。
问笼中鸡和兔的数量各是多少?
理清思路
同样的波及到两个变量：多少头 head 和多少只脚 foot，假如有 chicken 只和兔子 rabbit 只。那么就有一下关系：
chicken+rabbit=head；
chicken*2+rabbit*4=foot
套用在下面的例子中就是
chicken+rabbit=35；
chicken*2+rabbit*4=94
在应用穷举算法时，须要明确问题答案的范畴，这样才可能在指定范畴搜寻答案。指定范畴之后，就能够应用循环和条件判断语句进行逐渐验证后果了。
代码实现
public class ExhaustionAlgorithm {public static void main(String[] args) {exhaustion(35, 94);
}
public static void exhaustion(int head, int foot) {
int chicken, rabbit;
for (chicken = 0; chicken <= head; chicken++) {
rabbit = head - chicken;
if (chicken * 2 + rabbit * 4 == foot) {System.out.println(String.format("鸡有 %d 只，兔子有 %d 只", chicken, rabbit));
}
}
}
}
输入
鸡有 23 只，兔子有 12 只
其实下面这段代码和之前的文章——口试题：代码如何实现“百钱买百鸡”？是齐全相似的，所以百钱买百鸡的算法其实就是穷举算法。
参考资料：
https://www.cnblogs.com/orxx/…
https://zhuanlan.zhihu.com/p/…
举荐浏览
算法——根底学习材料 PDF 版下载
《数据结构与算法剖析：Java 语言形容》.pdf
面试官：数据量很大，分页查问很慢，有什么优化计划？
