笔试题: 了解穷举算法吗? 如何用代码实现

关注“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



面试官：数据量很大，分页查询很慢，有什么优化方案？