小编Ron*_*ald的帖子

在Hangman游戏中,贪婪的字母频率算法是否等同于最佳获胜机会算法？

为了更好地猜测正确的答案,有没有值得牺牲保留你的剩余生命的情况？

进一步澄清问题:

• 要猜测的所选单词取自已知字典.
• 你有N个生命,因此必须最大化猜测单词中所有字母而不犯N 错误的概率(即你可能有无限数量的正确猜测).
• 为了这个练习,词典中的每个单词具有相同的概率(即单词是随机选择的)
  • 一个更难的练习就是提出一个针对恶意的,无所不知的词选择策略(我不是在这里问)

动机:这个问题的灵感来自http://www.datagenetics.com/blog/april12012/index.html上的有趣讨论

他们提出了一种最佳地解决单词游戏"Hangman"的算法.

他们的策略可以这样概括(编辑以供澄清):

• 我们可以假设这个词是从特定的字典中提取的
• 我们知道单词中的字母数
• 消除字典中没有正确字母数的所有单词.
• 选择尚未猜到的字母,该字母出现在字典的剩余子集中的最大字数中.
• 如果出现这封信,我们知道它的位置.
• 如果没有出现这封信,我们就知道这封信没有出现.
• 消除字典子集中不完全符合此正确模式的所有单词,然后重复.
• 如果有两个(或更多)字母同样经常出现,算法可以对位置进行更深入的分析,以确定哪一个是首选的(如果这是合理的？)

在每一个阶段,我们都在猜测最大数量的剩余可能单词中出现的字母(以前没有猜到).

喜欢这种算法有一些动机 - 我们总是最不可能失去生命.

但是,令我感到震惊的是,这不一定是最好的解决方案:如果我们试图猜测这个词(在一定数量的生命中),那么最常见的字母是最有用的字母并不一定总是这样.区分剩余的可用单词.

不过,我不确定,因为尽可能避免失去生命似乎是恰当的.最佳策略是否会让我们牺牲生命以获得更好的获胜机会？

问题:这种贪婪算法是否等同于最佳获胜机会算法？你能证明吗？

一个示例字典+游戏将是理想的显示反证.