指纹树生成

Question

有一群人（假设有 1874 人），都代表世界上不同的公司（假设有 236 家）。我的任务是最好地确定每个人在哪家公司工作。诀窍在于，我不能简单地问一个人“你在哪里工作”并得到答案，但我拥有的是一份包含许多问题的调查问卷（假设有 290 个问题）以及我应该期望员工得到的确切答案每个公司的。有些公司可能会有相同的答案，所以最后，即使我不能准确确定一个人在哪家公司工作，我也应该能够缩小范围并说他/她一定在其中一家公司工作。

使用多值地图和一些其他数据结构，我已经通过 1 个问题 [查询] 确定了我可以识别的所有公司。使用这些查询来表示树数据结构的根，我需要使用其他查询/问题作为分支来构建树的其余部分来识别其余部分。

有什么建议/帮助/建议吗？

Answer 1

根据您在评论中的回答，我觉得您也可以让树的每个级别代表一个问题，并让该级别上的节点的分支/子节点代表答案。正如 btilly 所提到的，从技术上讲，这将是一个特里树。

更有效（尽管不一定在空间上）的解决方案可能涉及使用哈希表和哈希函数，该函数作用于答案选择来创建其哈希，但我认为考虑到您的要求和要求，特里树是最好的方法不在乎。

哦，对了：根据答案选择的布局方式，您可能在特定分支上有一系列答案，其中某些级别没有任何子分支/树；在这种情况下，您可能会将这些单一分支部分折叠成单独的节点。 http://en.wikipedia.org/wiki/Trie#compressing_tries 也可能提供一些尖端。

---

根据您对我最初答案的回复，这是我的想法：

为问题及其答案选择保留一个节点数组，每个答案选择都与哈希表（或您希望使用的任何数据结构）相关联；我建议哈希表（由于大量使用 Python 并使用 Python 的 set 数据结构（它作为哈希表的一种类型实现））包含指向每个公司的指针，或者包含指向单个公司的指针（如果给定问题的给出答案将表明公司开始 和。

当您第一次检查特定问题的答案时，并且有多个公司与该答案选择相关联，请将第一个答案的哈希表中的数据临时复制为链接列表或其他内容。当回答更多问题时，根据每个新答案的哈希表检查列表的元素，并从列表中删除每个新答案的哈希表中不存在的公司。重复提问过程，直到 1) 列表中只剩下一家公司，2) 列表中没有公司留下，或 3) 您已问完所有问题。

如果是 1)，那就是提问者的雇主。
如果是 2)，则该员工不受任何要检查的公司雇用，和/或某处存在错误。
如果是3)，则链表中剩余的公司就是问答者可能受雇的公司。

可能有一种更有效的方法来做到这一点，因为我的实现至少需要 580 个哈希表（每个答案一个，每个问题至少 2 个答案），但我现在真的想不出任何东西。

Answer 2

从根开始递归构建树。在每个步骤中，您都会有一组有效的调查问卷，最初将是所有调查问卷。从活跃的调查问卷中，选择一个问题，其中“是”的答案与“否”的答案一样多。为这个问题建立一个树节点。使用对您在此节点选择的问题回答“是”的子集调查问卷，创建“是”子树（递归地）。还可以使用对您选择的问题回答“否”的调查问卷子集创建“否”子树。

简单的例子：

假设我们试图猜测动物，并且我们有来自熊、斑马、鲑鱼和鳄鱼的调查问卷。

我们查看调查问卷，发现大约一半的人对“你是哺乳动物吗？”回答“是”，所以我们将其作为树的根。

现在我们只接受对这个问题回答“是”的调查问卷。在我们的例子中，它们是来自熊和斑马的。我们选择问题“你有条纹吗？”，因为大约一半人说有，一半人说没有。由于每个答案只有一份调查问卷，因此您创建了适当猜测斑马和熊的叶节点。

现在我们回溯到根节点并对“否”分支重复该过程。也就是说，我们查看鲑鱼和鳄鱼的调查问卷，并选择一个问题来区分不同的组。 “你喜欢微笑吗？”符合要求。

最终的树如下所示：

Ask: "Are you a mammal?"
 |
 +- yes -> Ask: "Do you have stripes?"
 |          |
 |          +- yes -> Guess: Zebra
 |          |
 |          +- no --> Guess: Bear
 |
 +- no --> Ask: "Do you like to smile?"
            |
            +- yes -> Guess: Crocodile
            |
            +- no --> Guess: Salmon

Answer 3

使用专家系统构建Prolog 是一种可能的解决方案。您考虑过这个选择吗？

通过这样做，您甚至可以添加一些自然语言处理功能，以简化与用户的交互。