首页 试题详情
单选题

在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的面积,如下图所示。现求解能覆盖所有房子的最少消防栓数和安装方案(问题求解过程中,可将房子和消防栓均视为直线上的点)。该问题求解算法的基本思路为:从左端的第一栋房子开始,在其右侧m米处安装一个消防栓,去掉被该消防栓覆盖的所有房子。在剩余的房子中重复上述操作,直到所有房子被覆盖。算法采用的设计策略为( );对应的时间复杂度为( )。 假设公路起点A的坐标为0,消防栓的覆盖范围(半径)为20米,10栋房子的坐标为(10,20,,30,35,60,80,160,210,260,300),单位为米。根据上述算法,共需要安装( )个消防栓。以下关于该求解算法的叙述中,正确的是(请作答此空)。

A肯定可以求得问题的一个最优解

B可以求得问题的所有最优解

C对有些实例,可能得不到最优解

D只能得到近似最优解

正确答案:A (备注:此答案有误)

相似试题

  • 单选题

    一条笔直公路一边许多房子安装消防栓,每个消防栓覆盖范围远大于房子面积,如下图所示。求解能覆盖所有房子最少消防栓数和安装方案(问题求解过程中,可将房子和消防栓均视为直线上点)。该问题求解算法基本思路为:从左端第一栋房子开始,其右侧m米处安装一个消防栓,去掉被该消防栓覆盖所有房子剩余房子中重复上述操作,直到所有房子被覆盖。算法采用设计策略为(请作答此空);对应时间复杂度为( )。假设公路起点A坐标为0,消防栓覆盖范围(半径)为20米,10栋房子坐标为(10,20,,30,35,60,80,160,210,260,300),单位为米。根据上述算法,共需要安装( )个消防栓。以下关于该求解算法叙述中,正确是( )

    答案解析

热门题库