第四百七十一章 二分法的效率
  在这个例子中有个现象也值得注意一下：不管俺心里想的是个什么数字，使用二分法所需的问题数字都是3，一个完全确定，毫无随机性的数字。

  这个特例显然可以推广：如果神秘数字X的概率分布函数是在2^K种可能性上的均匀分布，那么“二十个问题”游戏的最优策略可以通过二分法实现；在这种策略下，不论神秘数字是什么，问出它所需要的问题数都是K，因此所需要的平均问题数也是K。同学们请用红笔圈下这个结论（小心别把手机触摸屏划坏了），咱么晚点要用到这个结论。

  当然，这个二分法只适合于这样的特例，当神秘数字的可能性总数不是2的多少次方的时候，或者当神秘数字的分布不均匀的时候，这种问法显然不是最优的。这个问题任意形式的最优解法曾让一个叫大卫·霍夫曼（DavidHuffman）的年轻学生在1951年一夜成名。不过，那已经是在香农提出信息论三年之后了。



更多完整内容阅读登陆

《墨缘文学网，https://wap.mywenxue.org》