主题：牛的进来
daisyang
[专家分：0] 发布于 2007-01-03 01:11:00
世界名画陈列馆由m×n个陈列室组成。为防止名画被窃，需在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外，还可以监视与它所在陈列室相邻的前、后、左、右4个陈列室。请设计一个安排警卫机器人哨位的方案，使得名画陈列馆中每一个陈列室都在警卫机器人监视之下，且所用的警卫机器人最少。
这个要用什么算法？牛人快来解决吧
回复列表 （共4个回复）
沙发
雪光风剑 [专家分：27190] 发布于 2007-01-03 10:02:00
把整个陈列馆设为一个m*n的矩阵（二维数组）
递归的方法放置机器人
对于某一间陈列室有三种状态：
room[i][j]=0无人看守
room[i][j]=2在相邻的机器人看守范围内
room[i][j]=1有机器人看守
如果不考虑时间代价
可以考虑穷举所有的机器人放法然后分别算出全矩阵的权数，取权数最小的那个
否则的话考虑以马步放置机器人，这样所有的点都可以尽可能多地顾及而保证遗漏在最小程度
板凳
daisyang [专家分：0] 发布于 2007-01-03 19:16:00
room[i][j]=2在相邻的机器人看守范围内
是什么意思？？？
3 楼
argentmoon [专家分：13260] 发布于 2007-01-03 22:58:00
去参看一下图论里面的最小支配集算法。
4 楼
雪光风剑 [专家分：27190] 发布于 2007-01-04 00:30:00
意思是：这间房间本身没有机器人，但是这间房间在另外的机器人的看守范围内
我来回复
您所在位置：