免费小说阅读网

手机浏览器扫描二维码访问

第341章 勒洛三角体（第5页）

L（5）=5，L（6）=6，L（7）=7，L（8）=7。

（对，L（8）=7，俺没敲错。

）

因为俺心里想的是个随机变量X，在这个策略下所需要的问题数目L（X）就也是个随机变量。

这个随机变量L（X）也有一个分布，在知道P（x）的前提下，如果想算也是可以算出来的。

但是俺懒得算它。

既然L（X）是个随机变量，一个最自然的方式定义这个策略所需要的问题个数就是用这个随机变量的均值，或者说用平均所需要的问题个数。

如果你的数字直觉好，应该可以看到，即使不求L（X）的分布，这个随机变量的均值其实就是

L（1）*P（1）+L（2）*P（2）+…+L（M）*P（M）.

用L（X）的均值定义一个问问题策略所需要的问题个数除了“自然”

，还有什么物理意义吗？当然！

前面的大数定理告诉咱们，如果你用这个策略玩这个游戏很多次，你所用问题个数的平均值“几乎总是很接近”

L（X）的均值。

而当你玩了这个游戏无数次之后，你平均每次用的问题数就正好是这个L（X）的均值。

由此可见，如果俺们准备玩这个游戏很多次，那么用L（X）的均值定义所需要问题的个数，用金星老师的话说就是一个动作两个字：完美。

至此，俺们已经确定这个“二十个问题”

游戏的准确规则，即：你要设计一种问问题的策略，当用这个策略跟俺玩很多次（更准确的说，无数次）这个游戏之后，平均每次用的问题个数要越少越好！

换句话说，我们希望寻找一个最好的问问题策略，同时确定最少需要多少个问题（平均意义上）。

其实在一些特殊的情况下，确定最优的问问题策略和最少需要的问题个数并不困难。

考虑这样一个特例：俺心里的神秘数字X的取值范围是S={1，2，…，8}，而且X的概率分布函数是个均匀分布。

那么最优的问问题方法就是所谓的“二分法”

：每问一个问题要把这个神秘数字的可能范围缩减一半。

比如这样的问法：

问题1:把集合{1，2，…，8}分成左右两份，左边的是{1，2，3，4}，右边的是{5，6，7，8}。

然后问：你想的数是不是在左边啊？

问题2:根据俺的答案，你可以确定这个神秘数字只剩下四种选择。

你再类似地把四种选择分成左右两份，然后问：你想的数是不是在左边啊？

问题3:根据俺的答案，你现在可以确定这个神秘数字只有两种选择，再把它们一个放左边，一个放右边。

你再问：你想的数是不是在左边啊？

如此问完三个问题，你一定知道了俺的神秘数字。

相信你的直觉也应该告诉你，这就是最优问法！

那么在这个例子里，所需的最少问题个数就是3。

从咱们用每个问题把猜测空间一切两半的问法，同学们应该也已经认识到，这里得出的最少问题数3正是因为8=2^3，或者说，2=log8.（本文中所有的对数操作均以2为底数）。

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

这个特例显然可以推广：如果神秘数字X的概率分布函数是在2^K种可能性上的均匀分布，那么“二十个问题”

游戏的最优策略可以通过二分法实现；在这种策略下，不论神秘数字是什么，问出它所需要的问题数都是K，因此所需要的平均问题数也是K。

同学们请用红笔圈下这个结论（小心别把手机触摸屏划坏了），咱么晚点要用到这个结论。

当然，这个二分法只适合于这样的特例，当神秘数字的可能性总数不是2的多少次方的时候，或者当神秘数字的分布不均匀的时候，这种问法显然不是最优的。

这个问题任意形式的最优解法曾让一个叫大卫·霍夫曼（DavidHuffman）的年轻学生在1951年一夜成名。

不过，那已经是在香农提出信息论三年之后了。