抽象覆蓋點:最少覆蓋全部門
在明定的相鄰覆蓋模型中給出覆蓋五個門點的最少放置方案。
影片暫時無法載入。請檢查網絡後重試,或直接下載影片。
下載影片
展開影片文字稿
- 这是抽象覆盖模型,不代表真实摄像头视野。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門;兩個可以覆蓋全部。