algorithm - 改进的刽子手游戏，最优算法

Question

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

电脑在提示后给出以下提示

1. 开始于
2. 以。。结束
3. 包含
4. 不包括

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

这个问题有最优策略吗？天真的方法就是尝试每一个单词。当然，这是非常糟糕的。我认为更好的方法。作为第一个提示，选择最常见的字母等。但我认为你可以更有效地做到这一点

标签： algorithm

Answer 1

是的，有一个最佳策略。但是，该策略取决于解决给定单词列表的博弈树。词表是有限的；您在每个节点上都有一组有限的选择；可以配置每个猜测以确保结果添加大量信息，从而使您更接近解决方案。因此，博弈树是有限的。

为给定的词典（单词列表）构建游戏树。如果你想要保证最优攻击，你需要解决博弈树，包括minimax和pruning。如果您想在更短的时间内找到非常好的攻击，那么请从决策树的 ML（机器学习）领域中汲取灵感。

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