安装监控摄像头

来自计算思维百科
跳转至: 导航搜索
安装监控摄像头1.jpg

收藏世界著名人物画像的美术馆接到了盗贼的挑战书:“为了纪念2022年2月2日,我会把馆藏人物画中的一幅合成为某个专业游戏玩家的头像。”馆长宰和为了防止发生这种闹剧,打算安装多部摄像头。美术馆由几个画廊和连接这些画廊的走廊构成,设置于某个画廊的监控摄像头能够监视到该画廊和通过走廊直接连接的其他画廊。那么,为了监视所有画廊,至少需要安装几个摄像头呢?

美术馆的各画廊的连接形态如下图所示:

安装监控摄像头2.png

解决方案

在其中一个画廊上设置的摄像头可以同时监控到与画廊直接相连的其他画廊,我们把它描述成图的说法就是“各定点能够控制自身及与之连接的其他顶点”。那么,能够控制图所有顶点的顶点集合就是图的控制集,也就是说,图的控制集中的顶点就是我们要找的安装摄像头的画廊。

我们可以将美术馆的结构图看作是一棵树。

安装监控摄像头3.png

为了找出树的最小控制集,可以从树的最底部开始向上寻找。因为叶节点只能控制自身和父节点,而父节点还可以控制其他结点,因此选择父节点会更加有利。所以寻找方式设计如下:

1.不选择叶节点

2.从树的最底部向上移动,并按照如下方法选择其余结点

(1)若自己的后代结点中存在尚未控制的结点,则选择当前结点;

(2)其余情况不选择当前结点。

根据上述方式从结点5开始寻找结点,

第一步:不选择结点5

第二步:结点2的后代是结点5,结点5没有被控制,所以选择结点2加入控制集

第三步:结点1的后代有结点3,且结点3没有被控制,所以选择结点1加入控制集

第四步:结点0的后代中有结点4,且结点4没有被控制,所以选择结点0加入控制集

完成。

所以,最后的最小控制集是结点2、1、0

安装监控摄像头4.png

所以,我们只要再画廊2、1、0安装摄像头就能监视到所有画廊。

运用的计算思维

我们将画廊结构看成“图”,后又将图转变成树,是将问题进行了“转化”,运用的是“转化”“启发式”的计算思维。

参考文献

[1]具宗万.算法问题实战策略[M].崔盛一,译.北京:人民邮电出版社,2015