哈夫曼树：卡猜谜游戏

“设计，在提问的预期数量在随后的比赛[Gar94]问，＃52最小的策略你的卡甲板是由黑桃的一个王牌，黑桃两局末平分，三个三分球，以及多达九个九，使得45卡在所有。有人得出卡fromthe shuffleddeck，你必须问问题回答的用yes或no来识别。”哈夫曼树：卡猜谜游戏

这是从设计和算法Analyisis的练习。

什么在我脑海中正在解决它的方法有两种：

哪种方法是正确的？

任何帮助，欢迎。

编辑：我应该使用一个贪心方法。

2012-10-21 Tool

这些都不是最好的办法。你可以概括你进一步询问的问题，例如：“所选的卡片是1,4,7或8吗？”。

要决定要问哪个问题，你会生成一个包含数字的哈夫曼树。然后你会问：“所选的卡片是左子树中的数字之一吗？”如果是，向下移动到左侧子树并重复。否则，移动到右侧子树并重复。

2012-10-21 16:00:54 interjay

霍夫曼代码可以被排序，以便问题就像问题中的＃2一样。例如，“是x <7？”，是的，那么“是x <5？”等。 –

@MarkAdler：这很有趣，你说得对，在这种情况下可以保留最佳结果。我很好奇你是怎么看到这个的：你是否用重量1-9分析了9张牌的这种特殊情况，还是有一些权重的一般属性，这使得这是真的？ – interjay

这是显而易见的，因为频率按照卡片的顺序排列，所以规范代码自然会对符号进行排序。一般属性是value1 = freq2。）可能有些情况并非总是如此，仍然可以按照允许所有分支分叉较小和较大值的方式进行排序。 –

回答