设万维读者为首页 广告服务 技术服务 联系我们 关于万维
简体 繁体 手机版
分类广告
版主:诤友
万维读者网 > 教育学术 > 帖子
囚徒问题的破绽及推广
送交者: 大胖球 2004年02月06日18:53:43 于 [教育学术] 发送悄悄话

最大的破绽是一天放风一人, 固定不变. 如果说成是平均一天一人(每天可以0人, 也可以N人)才行, 否则时间可以用来表示次序.

让我们首先从一个记数人(只有第一个人记数)的算法的优化谈起.

学过算法的人都知道, 讨论一个算法, 平均时间固然重要, 最优时间和最劣时间也很重要.
只有一个记数人的情况下, 最优时间为198天. (假设1号为记数人, 则放风顺序为2号, 1号, 3号, 1号 ... 100号, 1号).
假设最长N天内所有人必然轮一遍的情况下(不加这个条件则所有解的最劣时间为无穷大, 讨论起来没有意义), 最劣时间大概为200N.(大于100N, 略小于200N, 就不详细计算了).

好, 如果一天固定放风一人. 则可以简单推广到两个记数人.
我们对囚犯进行编号. 假设
1. 1,2 号为记数人.
2. 可被记数状态为灯开时
3. 被记数为关灯
4. RESET为把灯从关的状态下打开
5. PASS 为不改变灯的状态.

我们让奇数号的人
1.1 可被记数状态(灯开), 奇数天时候:
A. 如果首次放风: 被记数(关灯)
B. 否则, PASS

1.2 不可记数状态(灯关), 奇数天时候:
A. 如果首次放风: PASS并转变为偶数号, 即下次偶数天放风为首次
B. 否则, RESET并转变为偶数号, 即下次偶数天放风为首次

2.1 可被记数状态(灯开), 偶数天时候:
PASS

2.2 不可记数状态(灯关), 偶数天时候
A. 如果首次奇数天放风: PASS 并重置首次, 即下次奇数天放风为首次
B. 否则, PASS

而1号只能在奇数天处于记数状态记数. 即

1.1 奇数天, 灯关(记数状态):
RESET. 心中总数加一(记数)

1.2 奇数天, 灯开:
PASS

2.1 偶数天, 灯关(记数状态)
RESET. 下次碰偶数天灯开的时候关灯

2.2 偶数天, 灯开
PASS

关于偶数号的被记数和2号的记数可以类推.

当1号数到50(包括自己)的时候, 转变为奇号被记数人(还继续是奇号记数人)
当2号数到50(包括自己)的时候, 转变为偶号被记数人(还继续是偶号记数人)

当1号或2号任何一人数到51时就可以宣布GAME OVER了.

这个的最优解要快一天. 最劣解是无穷大. 平均解很难计算, 但应该要好一点.


继续推广到100个记数人. 最优解为100天(每个人看见灯关并在自己的被记数天时,
才能PASS. 否则RESET. 第一个人在每个100天的第一天关灯, 当第100个人在每100天的最后一天看见灯关的时候宣布GAME OVER). 最劣解当然也是无穷大.
平均解也很难算, 但应该差很多.

这个解可以继续优化. 例如每个人的身份可以转换. 任何一个人在记数天都可以开灯. 转换到最后的第100个人宣布GAME OVER等等)

所以说, 在每天一个人放风的情况下, 究竟找多少人记数是个问题.

这个问题有实际意义. 例如在一个OS中, 有100个THREAD, 但只有一BIT的存储器. 如果固定时间内激活一个THREAD, 谁能SHUTDOWN OS的问题(最后一个被激活的SHUTDOWN OS).

如果时间不固定, 可以推广到2盏灯, 3盏灯... 8盏灯. (9盏或以上就没意义了).

另外, 可以考虑的还有, 如果放低要求, 保证有90%以上的把握就可以宣布了,要不然就等死了(风险/收益合适)下的优化解是什么.

这个足够写篇硕士论文了.(博士论文也够格了如果探讨深入的话)


0%(0)
0%(0)
标 题 (必选项):
内 容 (选填项):
实用资讯
北美最全的折扣机票网站
贝佳药业美国专利【骨精华】消关节痛、骨刺、五十肩【心血通】改善心绞痛
一周点击热帖 更多>>
一周回复热帖
历史上的今天:回复热帖
2003: 我鄙视你,"海龟"一族!
2003: 中国名校百年沉浮
2002: 论夏雨天的"呼吁完善制度"
2002: 以“科学”和“爱国”的名义——学术腐