在一条笔直公路一边有许多房子，现要安装消防栓，每个消防栓覆盖范围远大于房子面积，如下图所示。现求解能覆盖所有房子最少消防栓数和安装方案（问题求解过程中，可将房子和消防栓均视为直线上点）。该问题求解算法基本思路为：从左端第一栋房子开始，在其右侧m米处安装一个消防栓，去掉被该消防栓覆盖所有房子。在剩余房子中重复上述操作，直到所有房子被覆盖。算法采用设计策略为（ ）；对应时间复杂度为（ ）。
假设公路起点A坐标为0，消防栓覆盖范围（半径）为20米，10栋房子坐标为（10，20,，30，35，60，80，160，210，260，300），单位为米。根据上述算法，共需要安装（ ）个消防栓。以下关于该求解算法叙述中，正确是（请作答此空）。
- A.肯定可以求得问题一个最优解
- B.可以求得问题所有最优解
- C.对有些实例，可能得不到最优解
- D.只能得到近似最优解
正确答案及解析
正确答案
解析
对于第一空，本题使用是分治法。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.只能得到近似最优解
你可能感兴趣的试题
软件在机载设备中运用越来越广泛，驻留于机载设备中嵌入式软件失效会产生灾难性后果，一般要求其具有较高可靠性，因此，软件可靠性测试对机载软件至关重要。
解释软件可靠性含义及影响软件可靠性主要因素。
- 查看答案
【说明】某软件企业内部测试部门对其ERP产品进行内部测试之后，由第三方测试机构进行验收测试，重点测试质量特性包括：功能性、可靠性、易用性、效率、维护性以及可移植性。1、【问题1】验收测试依据是什么?验收测试对测试环境有何要求?2、【问题2】软件产品功能性测试中应关注哪些子特性?3、【问题3】在实际软件测试过程中，对缺陷管理与分析至关重要。回答如下问题：(1)针对本测试，Bug错误类型除了功能性错误外，还可能会包括哪些?(2)严重性级别是Bug重要属性，请写出常见功能性Bug严重性级别层次。(3)在测试过程中，Bug处理会处于不同状态，请设计Bug管理中从发现到关闭必须经历状态名称。4、【问题4】企业内部测试部在测试"主生产计划制定"模块过程中，使用30个测试案例进行测试，共发现10个问题。开发组对软件修改后，向测试组提交问题修改报告及修改后软件。问题修改报告中提出：其中3个问题是用户需求，不是错误，无需修改，其余7个问题已修改完成。测试组使用上轮测试中发现这7个问题5个测试案例进行了回归测试，确认问题已得到修改，因此测试组决定，当前版本可以进入配置管理库，进行后续集成工作。测试组做法是否有问题?为什么?如果有问题，应写出正确做法。
- 查看答案
软件在机载设备中运用越来越广泛，驻留于机载设备中嵌入式软件失效会产生灾难性后果，一般要求其具有较高可靠性，因此，软件可靠性测试对机载软件至关重要。
对某嵌入式软件，设计要求其可靠度为1000小时无失效概率99.99%。经实测得出其失效概率函数F(1000)=0.0012，问该软件是否符合设计可靠性要求，并说明原因。
- 查看答案
软件在机载设备中运用越来越广泛，驻留于机载设备中嵌入式软件失效会产生灾难性后果，一般要求其具有较高可靠性，因此，软件可靠性测试对机载软件至关重要。
可靠性评价时，经常使用定量指标包括失效概率、可靠度和平均无失效时间(MTTF.，请分别解释其含义。
- 查看答案
某嵌入式刹车控制软件，应用于汽车刹车控制器，该软件需求如下：
1．模式选择：采集模式控制离散量信号In_D1并通过模式识别信号灯显示软件当前工作模式。在信号In_D1为低电平时进入正常工作模式(模式识别信号灯为绿色)，为高电平时进入维护模式(模式识别信号灯为红色)。软件在正常工作模式下仅进行刹车控制和记录刹车次数，在维护模式下仅进行中央控制器指令响应。
2．刹车控制：采用定时中断机制，以5ms为周期采集来自驻车器发出模拟量信号In_A1以及来自刹车踏板发出模拟量信号In_A2，并向刹车执行组件发送模拟量信号Out_A1进行刹车控制。
模拟量信号说明：1)In_A1、In_A2以及Out_A1信号范围均为[0.0V,10.0V]，信号精度均为0.1V；2)Out_A1信号计算方法为：Out_A1=In_A1+0.3×In_A2，在计算完成后需要在满足信号精度要求下进行四舍五入及限幅处理。
3．记录刹车次数：在Out_A1大于4V时，读出非易失存储器NVRAM中保存刹车次数记录进行加1操作，然后保存至非易失存储器NVRAM中。
4．响应中央控制器指令；接收来自中央控制器串行口指令字In_S1，回送串行口响应字Out_S1。当接收指令字错误时，软件直接丢弃该命令字，不进行任何响应。
指令字及响应字说明如表1所示。
3、某测试人员设计了如表3所示操作步骤，对模式选择功能进行测试(表中END表示用例到此结束)。
表3
为进一步提高刹车控制软件安全性，在需求中增加了设计约束：软件在单次运行过程中，若进入正常工作模式，则不得再进入维护模式。请参照表3测试用例完成表4，用于测试该设计约束。
表4
- 查看答案