专栏首页Java后端技术栈cwnait笔试题:了解穷举算法吗?如何用代码实现

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

穷举法又称穷举搜索法,是一种在问题域的解空间中对所有可能的解穷举搜索,并根据条件选择最优解的方法的总称。数学上也把穷举法称为枚举法,就是在一个由有限个元素构成的集合中,把所有元素一一枚举研究的方法。

穷举算法依赖于计算机的强大计算能力来穷尽每一种可能的情况,从而达到求解的目的。穷举算法效率不高,但适用于一些没有明显规律可循的场合。

使用穷举法解决问题,基本上就是以下两个步骤:   • 确定问题的解(或状态)的定义、解空间的范围以及正确解的判定条件;   • 根据解空间的特点来选择搜索策略,逐个检验解空间中的候选解是否正确;

解空间的定义 解空间就是全部可能的候选解的一个约束范围,确定问题的解就在这个约束范围内,将搜索策略应用到这个约束范围就可以找到问题的解。要确定解空间,首先要定义问题的解并建立解的数据模型。如果解的数据模型选择错误或不合适,则会导致解空间结构繁杂、范围难以界定,甚至无法设计穷举算法。

穷举解空间的策略 穷举解空间的策略就是搜索算法的设计策略,根据问题的类型,解空间的结构可能是线性表、集合、树或者图,对于不同类型的解空间,需要设计与之相适应的穷举搜索算法。简单的问题可以用通用的搜索算法,比如线性搜索算法用于对线性解空间的搜索,广度优先和深度优先的递归搜索算法适用于树型解空间或更复杂的图型解空间。

盲目搜索和启发式搜索 对于线性问题的盲目搜索,就是把线性表中的所有算法按照一定的顺序遍历一遍,对于复杂问题的盲目搜索,常用广度优先搜索和深度优先搜索这两种盲目搜索算法。如果搜索能够智能化一点,利用搜索过程中出现的额外信息直接跳过一些状态,避免盲目的、机械式的搜索,就可以加快搜索算法的收敛,这就是启发性搜索。启发性搜索需要一些额外信息和操作来“启发”搜索算法,根据这些信息的不同,启发的方式也不同。

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

剪枝和启发 剪枝不是启发性搜索。剪枝的原理是在结果已经搜索出来或部分搜索出来(比如树的根节点已经搜索出来了,但是叶子节点还没有搜索出来)的情况下,根据最优解的判断条件,确定这个方向上不可能存在最优解,从而放弃对这个方向的继续搜索。而启发性搜索通常是根据启发函数给出的评估值,在结果出来之前就朝着最可能出现最优解的方向搜索。它们的差异点在于是根据结果进行判断还是根据启发函数的评估值进行判断。

搜索算法的评估和收敛 收敛原则是只要能找到一个比较好的解就返回(不求最好),根据解的评估判断是否需要继续下一次搜索。大型棋类游戏通常面临这种问题,比如国际象棋和围棋的求解算法,想要搜索整个解空间得到最优解目前是不可能的,所以此类搜索算法通常都通过一个搜索深度参数来控制搜索算法的收敛,当搜索到指定的深度时(相当于走了若干步棋)就返回当前已经找到的最好的结果,这种退而求其次的策略也是不得已而为之。

简言之

穷举算法的基本思想就是从所有可能的情况中搜索正确的答案,其执行步骤如下:

(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/p/10947129.html https://zhuanlan.zhihu.com/p/112047590

本文分享自微信公众号 - Java后端技术全栈(jjs-2018),作者:田老师

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 面试被问:缓存击穿有什么解决方案

    缓存(内存 or Memcached or Redis.....)在互联网项目中广泛应用,本篇博客将讨论下缓存击穿这一个话题,涵盖缓存击穿的现象、解决的思路、以...

    用户4143945
  • 浅谈几种设计模式--代理模式

    代理模式(Proxy Pattern),为其他对象提供一个代理,并由代理对象控制原有对象的引用;也称为委托模式。

    用户4143945
  • 10个重构小技巧,去掉代码中的S味

    本次我们抛开 JAVA 虚拟机源码这些相对底层的东西,来与各位探讨一下几个代码重构的小技巧。重构的手法有很多种,相对而言,一篇文章的涵盖量自然是无法提到所有,这...

    用户4143945
  • Java架构笔记-互联网架构设计:高性能的后端

    后端服务一般指用户直接看到的远程服务,涉及到网络硬件、逻辑计算、通信协议和数据存储等部分。下面我们将着重介绍高性能后台服务的设计方法和策略。

    聚优云惠
  • 2017年深度学习领域阅读量最高的11篇文章

    来源:Analytics Vidhya 智能观 编译 【智能观】本文是国外知名技术网站Analytics Vidhya总结的11篇深度学习领域最佳文章,如果你还...

    企鹅号小编
  • 暗网悲剧的前半生:亲爹傻逼,养父脑残。

    暗网不负众望,2018年再次拉向高潮——华住旗下3千万酒店开房数据,在暗网中文论坛出售。

    用户1564362
  • torch详解(Yoshua Bengio深度学习暑期班)

    用户1908973
  • 【Java入门提高篇】Day31 Java容器类详解(十三)TreeSet详解

      TreeSet是Set家族中的又一名懒将,跟其他两位一样,与对应的Map关系密不可分

    弗兰克的猫
  • 【Java入门提高篇】Day31 Java容器类详解(十三)TreeSet详解

      TreeSet是Set家族中的又一名懒将,跟其他两位一样,与对应的Map关系密不可分

    弗兰克的猫
  • 【Java入门提高篇】Day31 Java容器类详解(十三)TreeSet详解

      TreeSet是Set家族中的又一名懒将,跟其他两位一样,与对应的Map关系密不可分

    弗兰克的猫

扫码关注云+社区

领取腾讯云代金券