不正当的刽子手问题

Question

Perverse Hangman是一款非常像常规Hangman的游戏,有一个重要区别:获胜的单词由房子动态决定,具体取决于猜测的字母.

例如,假设您有董事会_ AIL和12个剩余的猜测.因为有13个不同的单词以AIL结尾(保释,失败,冰雹,监狱,kail,邮件,钉子,桶,铁路,帆,尾巴,ail,w),所以无论你猜不到12个字母,房子都能保证赢. ,房子会声称所选择的单词是你没猜到的那个.但是,如果董事会是_ ILM,那么你已经走投无路,因为FILM是唯一以ILM结尾的词.

挑战是:给定一个字典,一个字长和允许猜测的数量,提出一个算法:

a)证明玩家总是通过输出决策树来获胜,无论如何都是为了让房子在角落里的角落

b)证明房子总是通过输出房子的决策树来获胜,无论如何都能让房子逃脱.

作为玩具示例,请考虑字典:

bat
bar
car

如果您被允许3次错误猜测,则玩家将使用以下树获胜:

Guess B
NO -> Guess C, Guess A, Guess R, WIN
YES-> Guess T
      NO -> Guess A, Guess R, WIN
      YES-> Guess A, WIN

Answer 1

这几乎与"如何通过反复称重找到奇怪的硬币？"相同.问题.根本的见解是,您正在尝试最大化您从猜测中获得的信息量.

用于构建决策树的贪婪算法如下: - 对于每个猜测,选择答案为"真"的猜测和答案为"假"的猜测尽可能接近50-50,作为理论上的信息这提供了最多的信息.

设N是集合的大小,A是字母表的大小,L是单词中的字母数.

所以把你所有的话放在一个集合中.对于每个字母位置,以及字母表中的每个字母,计算该字母在该位置有多少个单词(这可以使用额外的散列表进行优化).选择最接近大小的一半的计数.这是O(L*A).

将该集合分为两个,将具有此字母的子集放在此位置,并将两个分支分配给树.重复每个子集,直到您拥有整个树.在最坏的情况下,这将需要O(N)步骤,但如果你有一个很好的字典,这将导致O(logN)步骤.