问改进的Hangman博弈，最优算法
EN

Stack Overflow用户

提问于 2018-11-26 18:09:53

回答 1查看 93关注 0票数 2

计算机现在随机选择其中一个单词，程序应该尽可能少地猜测单词。

在提示之后，计算机给它提供了以下提示

让我们以单词house为例:如果我们猜到"h“，那么我们得到的答案是搜索的单词以"h”开头。如果我们猜到"ous“，我们得到的答案是搜索到的单词包含"ous”usw，如果我们猜到"house“，那么我们得到的答案是我们找到了正确的单词。

对于这个问题，有没有最优的策略？天真的方法是简单地尝试每一个单词。当然，这很糟糕。我想是更好的方法。作为第一小贴士，选择最常见的字母等等。但是我认为你可以更有效地做到这一点。

发布于 2018-11-26 22:19:29

是的，有一个最优的策略。然而，该策略取决于求解给定单词列表的游戏树。单词列表是有限的；在每个节点上都有有限的选择；可以配置每个猜测，以保证结果会添加大量的信息，从而使您更接近解决方案。所以，游戏树是有限的。

为给定的词汇(单词列表)构建游戏树。如果您想要有保证的最优攻击，您需要解决游戏树，包括minimax和剪枝。如果您想在较短的时间内找到非常好的攻击，请从决策树的ML (机器学习)区域中提取。

这足以让你朝着解决方案的方向前进吗？

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/53486787

复制

相似问题

问改进的Hangman博弈，最优算法EN