囚徒问题的破绽及推广 |
送交者: 大胖球 2004年02月06日18:53:43 于 [教育学术] 发送悄悄话 |
最大的破绽是一天放风一人, 固定不变. 如果说成是平均一天一人(每天可以0人, 也可以N人)才行, 否则时间可以用来表示次序. 让我们首先从一个记数人(只有第一个人记数)的算法的优化谈起. 学过算法的人都知道, 讨论一个算法, 平均时间固然重要, 最优时间和最劣时间也很重要. 好, 如果一天固定放风一人. 则可以简单推广到两个记数人. 我们让奇数号的人 1.2 不可记数状态(灯关), 奇数天时候: 2.1 可被记数状态(灯开), 偶数天时候: 2.2 不可记数状态(灯关), 偶数天时候 而1号只能在奇数天处于记数状态记数. 即 1.1 奇数天, 灯关(记数状态): 1.2 奇数天, 灯开: 2.1 偶数天, 灯关(记数状态) 2.2 偶数天, 灯开 关于偶数号的被记数和2号的记数可以类推. 当1号数到50(包括自己)的时候, 转变为奇号被记数人(还继续是奇号记数人) 当1号或2号任何一人数到51时就可以宣布GAME OVER了. 这个的最优解要快一天. 最劣解是无穷大. 平均解很难计算, 但应该要好一点.
这个解可以继续优化. 例如每个人的身份可以转换. 任何一个人在记数天都可以开灯. 转换到最后的第100个人宣布GAME OVER等等) 所以说, 在每天一个人放风的情况下, 究竟找多少人记数是个问题. 这个问题有实际意义. 例如在一个OS中, 有100个THREAD, 但只有一BIT的存储器. 如果固定时间内激活一个THREAD, 谁能SHUTDOWN OS的问题(最后一个被激活的SHUTDOWN OS). 如果时间不固定, 可以推广到2盏灯, 3盏灯... 8盏灯. (9盏或以上就没意义了). 另外, 可以考虑的还有, 如果放低要求, 保证有90%以上的把握就可以宣布了,要不然就等死了(风险/收益合适)下的优化解是什么. 这个足够写篇硕士论文了.(博士论文也够格了如果探讨深入的话) |
|
|
|
实用资讯 | |
|
|
一周点击热帖 | 更多>> |
|
|
一周回复热帖 |
|
|
历史上的今天:回复热帖 |
2003: | 我鄙视你,"海龟"一族! | |
2003: | 中国名校百年沉浮 | |
2002: | 论夏雨天的"呼吁完善制度" | |
2002: | 以“科学”和“爱国”的名义——学术腐 | |