algorithm - 哈夫曼树 : card guessing game

Question

"Design a strategy that minimizes the expected number of questions asked in the following game [Gar94], #52. You have a deck of cards that consists of one ace of spades, two deuces of spades, three threes, and on up to nine nines, making 45 cards in all. Someone draws a card fromthe shuffleddeck, which you have to identify by asking questions answerable with yes or no."

这是算法设计与分析中的练习。

我想到了两种解决方法:

1. 是 9 吗？否:是 8 吗？否:是 7 吗？ ...等等。

2. 卡片是否 > 5？否:卡片是否 > 2？ ...等等。

哪种方法是正确的？

欢迎任何帮助。

编辑:我应该使用贪心法。

Answer 1

这两种方法都不是最好的方法。您可以进一步概括您提出的问题，例如:“所选择的牌是 1、4、7 还是 8 中的一张？”。

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