首页
登录
从业资格
在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的
在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的
最全题库
2022-08-02
57
问题
在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的面积,如下图所示。现求解能覆盖所有房子的最少消防栓数和安装方案(问题求解过程中,可将房子和消防栓均视为直线上的点)。该问题求解算法的基本思路为:从左端的第一栋房子开始,在其右侧m米处安装一个消防栓,去掉被该消防栓覆盖的所有房子。在剩余的房子中重复上述操作,直到所有房子被覆盖。算法采用的设计策略为( );对应的时间复杂度为( )。
假设公路起点A的坐标为0,消防栓的覆盖范围(半径)为20米,10栋房子的坐标为(10,20,,30,35,60,80,160,210,260,300),单位为米。根据上述算法,共需要安装( )个消防栓。以下关于该求解算法的叙述中,正确的是(请作答此空)。A.肯定可以求得问题的一个最优解B.可以求得问题的所有最优解C.对有些实例,可能得不到最优解D.只能得到近似最优解
选项
A.肯定可以求得问题的一个最优解
B.可以求得问题的所有最优解
C.对有些实例,可能得不到最优解
D.只能得到近似最优解
答案
C
解析
对于第一空,本题使用的是分治法。1、分治法特征:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决;否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。2、动态规划法:在求解问题中,对于每一步决策,列出各种可能的局部解,再依据某种判定条件,舍弃那些肯定不能得到最优解的局部解,在每一步都经过筛选,以每一步都是最优解来保证全局是最优解。本题情景没有列出所有的可能解进行筛选,因此,本题不属于动态规划法。3、回溯法:回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当搜索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择。这种走不通就退回再走的技术就是回溯法。本题情景没有探索和回退的过程,因此,本题不属于回溯法。4、贪心法:总是做出在当前来说是最好的选择,而并不从整体上加以考虑,它所做的每步选择只是当前步骤的局部最优选择,但从整体来说不一定是最优的选择。由于它不必为了寻找最优解而穷尽所有可能解,因此其耗费时间少,一般可以快速得到满意的解,但得不到最优解。在本题情景中,没有给出每步选择的局部最优判断条件,因此,本题属于贪心法。 由于本题的算法过程,是依次与各个房子进行判断,当所有房子都被比较之后,则问题结束,因此时间复杂度与房子的个数相关,本问题的时间复杂度应该趋于现象,为O(n),属于贪心算法。对于第三空,关于对应序列(10,20,30,35,60,80,160,210,260,300)第一轮放置:在第一座房子x=10的右侧20米处安装一个消防栓,可以覆盖10,20,30,35这4栋房子;2、第二轮放置:去掉前4栋房子,在第5栋房子x=60的右侧20米处安装一个消防栓,可以覆盖60、80这2栋房子;3、第三轮放置:去掉前面已覆盖的房子,在第7栋房子x=160的右侧20米处安装一个消防栓,只可以覆盖160这一栋房子;4、第四轮放置:去掉前面已覆盖的房子,在第8栋房子x=210的右侧20米处安装一个消防栓,可以覆盖210这一栋房子第五轮放置:去掉前面已覆盖的房子,在第9栋房子x=260的右侧20米处安装一个消防栓,可以覆盖260、300这2栋房子;房子全部覆盖完毕,因此共需安装5个消防栓。对于第四空,对于得到一个最优解是动态规划的特点,可以得到问题所有的最优解,是回溯法的特征,可以排除A、B选项。对于C、D选项。A.肯定可以求得问题的一个最优解B.可以求得问题的所有最优解C.对有些实例,可能得不到最优解D.只能得到近似最优解
转载请注明原文地址:https://tihaiku.com/congyezige/2408414.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
数据字典中“数据项”的内容包括:名称、编号、取值范围、长度和()。A.处理频率
以下关于等价类划分法的叙述中,不正确的是( )。A.如果规定输入值a的范围为1
软件项目管理所涉及的范围覆盖了整个软件()。A.开发过程 B.运行与维
软件项目管理所涉及的范围覆盖了整个软件()A.开发过程 B.运行与维护过程
在某户籍管理信息系统中,假设人口年龄的输入范围为2~100,则根据黑盒测试中的
以下关于等价类划分法的叙述中,不正确的是()。A.如果规定输入值a的范围为1~
软件文档按照其产生和使用的范围可分为开发文档、管理文档和用户文档。其中开发文档不
()不属于易用型测试范围范畴A.软件产品使用户能理解软件是否适合以及如何能将软件
某网上信息系统的服务范围为全国。按照功能类别将其划分为前端路由区、Web区(DM
以下不属于文档测试的测试范围的是()。A.软件开发计划 B.数据库脚本 C.
随机试题
[originaltext]W:Welcometojoinus,Hank.M:Thankyou.(17)Ihavedonethiski
【S1】[br]【S7】D副词辨义题[考频:7]。空格位于take之后,介词短语intheprocess之前,需要副词。该句意为:我想这里的关键是要认真
拆除工程的建设单位与施工单位在签订施工合同时,应签订()协议,明确双方的安全管理
人口采集处理和利用业务属于(),营业执照错发属于(作答此空),户籍管理属于(
根据《商业银行资本管理办法(试行)》的规定,我国商业银行的逆周期资本要求由(
拍卖行应在拍卖日的( )前以登报或通过电视等媒体公告的形式发布关于该房地产拍卖
国家对最低生活保障家庭中有劳动能力,并处于失业状态的成员,给予就业帮助。根据《社
现需设计一个无黏性土的简单边坡。已知边坡高度为10m,土的内摩擦角φ=45°,黏
搜查时,必须有被搜查人或者他的家属、邻居或者其他见证人在场。( )
关于雇用临时员工的不利情况的说法错误的是( )。A.具有较高的灵活性 B.临
最新回复
(
0
)