用 E4X 和 Prototype 创建 Ajax mindreader 应用程序，第 1 部分: 构建 Twenty Questions 基础结构

核心提示： 在本系列中，示例应用程序要简单得多，用 E4X 和 Prototype 创建 Ajax mindreader 应用程序，第 1 部分: 构建 Twenty Questions 基础结构(2)，实际上，我们仅仅实现一个简单的二分查找法（binary search），但是这个问题是传统的 &ldqu

在本系列中，示例应用程序要简单得多。实际上，我们仅仅实现一个简单的二分查找法（binary search），这种算法的理论基础是：如果在一组可能的内容中不断删除不合适的内容，最终就会找到需要的东西。实际上，“twenty questions” 这个名字就来源于这样一种理论：对于包含宇宙中所有东西的集合，只需用大约 20 个不同的 “是/否” 问题进行排除，最终就可以找到一个东西。

在第 1 部分中，将构建一个自包含的系统，它从一个固定的知识库开始，然后向用户提问来判断用户心里想的东西。在第 2 部分中，将对系统进行培训，让它学习新东西。如果系统猜错了，系统会询问正确的东西以及如何从知识库中区分出它。然后，它把新知识添加到知识库中并重新开始。最后，将把这个功能与一个外部数据库集成起来，从而存储系统从所有用户那里学到的东西。

算法

说起来容易，但是究竟如何在浏览器中实现 Twenty Questions 呢？如果人与人之间玩这个游戏，提问人可以凭借经验决定下一个问题；计算机如何做出决定呢？

实际上很简单。二分查找算法 — 或更一般的分治算法 — 用每个问题排除大约一半儿的可能选择。例如，如果最初有 1024 个可能的选择，那么第一个问题把范围缩小到 512 个，第二个问题把范围缩小到 256 个，第三个问题把范围缩小到 128 个，以此类推。对于 1024 个可能的选择，只需要 10 个问题就可以找到目标。实际上，20 个问题可以区分 1,048,576 个不同的选择！

实际上，算法并不复杂。算法如下：

装载知识库中的所有东西。

询问用户他心里想的东西是 “动物、植物还是矿物？”
应用程序使用的其他问题都要求回答是或否，但是这个问题是传统的 “第一个问题”，它可以排除大约 2/3 的可能选择。

编缉推荐阅读以下文章

• 用 E4X 和 Prototype 创建 Ajax mindreader 应用程序，第 2 部分: 使 mindreader 应用程序更智能化