抽象覆盖点:最少覆盖全部门
在明定的相邻覆盖模型中给出覆盖五个门点的最少放置方案。
视频暂时无法加载。请检查网络后重试,或直接下载视频。
下载视频
展开视频文字稿
- 这是抽象覆盖模型,不代表真实摄像头视野。1到5号门排成一列,一个标记只覆盖自己和紧邻门。
- 一个标记最多覆盖连续3个门,所以单个标记不可能覆盖5个门,至少需要2个。
- 把一个标记放2号,它覆盖1、2、3号。
- 另一个放4号,它覆盖3、4、5号。两个范围合起来覆盖全部五门。
- 下界说至少2个,构造又用2个做到,所以最少正好是2个。
- 现在改成1到4号门,规则不变。请圈出最少标记及各自覆盖范围,小宝贝到你了。
逻辑思维
下界与构造
看一个例子
在本题抽象模型中,1到5号门排成一列;一个标记放在某门,只覆盖该门和紧邻门。最少放几个标记能覆盖全部门?
一个标记最多覆盖连续3个门,所以单个标记不可能覆盖5个门,至少需要2个。把一个标记放2号,它覆盖1、2、3号。另一个放4号,它覆盖3、4、5号。两个范围合起来覆盖全部五门。下界说至少2个,构造又用2个做到,所以最少正好是2个。
马上试一题
一个最多覆盖3门,不足4门;两个可以覆盖全部。