2. 计算机
  3. 在一条笔直公路的一边有许多房子，现要安装消火栓，每个消火栓的覆盖范围远大于房子的面积，如下图所示。现求解能覆盖所有房子的最少消火栓数和安装方案(问题求解过程中，可将房子和消火栓均视为直线上的点)。该问题求解算法的基本思路为：从左端的第一栋房子开始，在其右侧

在一条笔直公路的一边有许多房子，现要安装消火栓，每个消火栓的覆盖范围远大于房子的面积，如下图所示。现求解能覆盖所有房子的最少消火栓数和安装方案(问题求解过程中，可将房子和消火栓均视为直线上的点)。该问题求解算法的基本思路为：从左端的第一栋房子开始，在其右侧

admin2019-10-08  32
问题 在一条笔直公路的一边有许多房子，现要安装消火栓，每个消火栓的覆盖范围远大于房子的面积，如下图所示。现求解能覆盖所有房子的最少消火栓数和安装方案(问题求解过程中，可将房子和消火栓均视为直线上的点)。该问题求解算法的基本思路为：从左端的第一栋房子开始，在其右侧m米处安装一个消火栓，去掉被该消火栓覆盖的所有房子。在剩余的房子中重复上述操作，直到所有房子被覆盖。算法采用的设计策略为________(1)；对应的时间复杂度为________(2)。

假设公路起点A的坐标为0，消火栓的覆盖范围(半径)为20m，10栋房子的坐标为(10，20，30，35，60，80，160，210，260，300)，单位为m。根据上述算法，共需要安装________(3)个消火栓。以下关于该求解算法的叙述中，正确的是________(4)。
(4)
选项 A、肯定可以求得问题的一个最优解
B、可以求得问题的所有最优解
C、对有些实例，可能得不到最优解
D、只能得到近似最优解
答案A
解析 对于第一个空，本题使用的是分治法。
1)分治法特征：对于一个规模为n的问题，若该问题可以容易地解决(比如说规模n较小)则直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
    2)动态规划法：在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。本题情景没有列出所有的可能解进行筛选，因此，本题不属于动态规划法。
    3)回溯法：回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。这种走不通就退回再走的技术就是回溯法。本题情景没有探索和回退的过程，因此，本题不属于回溯法。
    4)贪心法：总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不必为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解。在本题情景中，没有给出每步选择的局部最优判断条件，因此，本题不属于贪心法。
    舍弃已被覆盖的房子，可以将问题的规模逐步缩小，形成规模较小的子问题，而这些问题的求解与原问题的求解过程相同，因此本题属于分治法的算法思想。
    由于本题的算法过程，是依次与各个房子进行判断，当所有房子都被比较之后，则问题结束，因此时间复杂度与房子的个数相关，本问题的时间复杂度应该趋于现象，为O(n)。
    对于第三个空，关于对应序列(10，20，30，35，60，80，160，2lO，260，300)：
    第一轮放置：在第一座房子x=10的右侧20m处安装一个消火栓，可以覆盖10，20，30，35这4栋房子；
    第二轮放置：去掉前4栋房子，在第5栋房子x=60的右侧20米处安装一个消火栓，可以覆盖60、80这2栋房子；
    第三轮放置：去掉前面已覆盖的房子，在第7栋房子x=160的右侧20m处安装一个消火栓，只可以覆盖160这一栋房子：
    第四轮放置：去掉前面己覆盖的房子，在第8栋房子x=210的右侧20m处安装一个消火栓，可以覆盖210这一栋房子
    第五轮放置：去掉前面己覆盖的房子，在第9栋房子x=260的右侧20米处安装一个消火栓，可以覆盖260、300这2栋房子；
    房子全部覆盖完毕，因此共需安装5个消火栓。
    对于第四个空，对于得到一个最优解是动态规划的特点，可以得到问题所有的最优解，是回溯法的特征，可以排除A、B选项。对于C、D选项，C的语法更为合理一些。
转载请注明原文地址:https://kaotiyun.com/show/tGCZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)