sjo*_*obe 5 algorithm tree breadth-first-search depth-first-search data-structures
有一群人[比如1874年],他们代表着世界上不同的公司[比方说他们中的236个].我的任务是最好地确定每个人工作的公司.诀窍在于我不能简单地问一个人"你在哪里工作"并得到答案,但我所拥有的是一份问卷,里面有一些问题[比方说290个问题]以及我应该对员工的期望.每个公司.有些公司可能会有相同的答案,所以最后,即使我无法准确确定一个人的公司,我也应该能够缩小范围并说他/她必须为其中一家公司工作.
使用多值映射和其他一些数据结构,我已经确定了所有可以通过1个问题[查询]识别的公司.使用这些查询来表示树数据结构的根,我需要使用其他查询/问题构建树的其余部分作为分支来识别其余的.
任何建议/帮助/建议？
根据您在评论中的回答，我觉得您也可以让树的每个级别代表一个问题，并让该级别上的节点的分支/子节点代表答案。正如 btilly 所提到的，从技术上讲，这将是一个特里树。
更有效（尽管不一定在空间上）的解决方案可能涉及使用哈希表和哈希函数，该函数作用于答案选择来创建其哈希，但我认为考虑到您的要求和要求，特里树是最好的方法不在乎。
哦，对了：根据答案选择的布局方式，您可能在特定分支上有一系列答案，其中某些级别没有任何子分支/树；在这种情况下，您可能会将这些单一分支部分折叠成单独的节点。http://en.wikipedia.org/wiki/Trie#compressing_tries也可能提供一些提示。
根据您对我最初答案的回复，这是我的想法：
为问题及其答案选择保留一个节点数组，每个答案选择都与一个哈希表（或您希望使用的任何数据结构）相关联；我建议使用哈希表，因为经常使用 Python 并习惯于Python 的set数据结构，以哈希表的形式实现，包含指向每个公司的指针，或者如果给定问题的给定答案将指示开始的公司，则包含指向单个公司的指针。
当您第一次检查特定问题的答案时，并且有多个公司与该答案选择相关联，请将第一个答案的哈希表中的数据临时复制为链接列表或其他内容。当回答更多问题时，根据每个新答案的哈希表检查列表的元素，并从列表中删除每个新答案的哈希表中不存在的公司。重复提问过程，直到 1) 列表中只剩下一家公司，2) 列表中没有公司留下，或 3) 您已问完所有问题。
如果是 1)，则为提问者的雇主。
如果是 2)，则该员工并未受雇于任何要检查的公司，和/或某处存在错误。
如果是3)，则链表中剩余的公司就是问答者可能受雇的公司。
可能有一种更有效的方法来做到这一点，因为我的实现至少需要 580 个哈希表（每个答案一个，每个问题至少 2 个答案），但我现在真的想不出任何东西。