在游戏的刽子手，它是一个贪婪的信频算法相当于一个最好的机会 - - 中奖算法？

In the game Hangman, is it the case that a greedy letter-frequency algorithm is equivalent to a best-chance-of-winning algorithm?

是否有过的情况下这是值得牺牲你剩下的生命preservation，为求更好的机会猜测正确答案的？

Is there ever a case where it's worth sacrificing preservation of your remaining lives, for the sake of a better chance of guessing the correct answer?

问题的进一步澄清：

在所选择的字被猜测已采取从已知的字典。 您在指定N的生活，因而必须最大限度地猜测在字中的所有字母的可能性，而不会用N的错误的（即你可以有无限多个正确的猜测）。 在词典里，每个字都有相等的概率，为了这项工作（即这个词是随机选择） 在一个较激烈的运动将拿出对恶意的，无所不知字选取器的策略（我不是要在这里） The selected word to be guessed has been taken from a known dictionary. You are given N lives, and thus have to maximise the probability of guessing all the letters in the word without making N mistakes (i.e. you may have an unlimited number of correct guesses). Each word in the dictionary has equal probability, for the sake of this exercise (i.e. the word is chosen randomly) a harder exercise would be to come up with a strategy against a malicious, omniscient word-chooser (I am not asking that here)

动机：这个问题是在有趣的讨论http://www.datagenetics.com/blog/april12012/index.html

Motivation: This question is inspired by the interesting discussion at http://www.datagenetics.com/blog/april12012/index.html

他们提出的算法求解文字游戏刽子手最佳状态。

They suggest an algorithm for solving the word game "Hangman" optimally.

他们的策略可以概括这样（编辑澄清）：

Their strategy can be summarised thus (edited for clarification):

我们可以认为这个词是从一个特定的字典中抽取 我们知道，字母在单词数量 消除在字典中的所有单词没有字母的正确数量。 选择发生在数量最多的字典中的其余子话的还未猜字母。 如果出现这封信，我们知道它的位置。 如果这封信没有出现，我们知道这不会发生在这个词。 消除在字典中子集中的所有单词，不适合正是这种正确的模式，并重复。 如果有2个（或以上）同样经常出现字母，该算法可以执行的位置更深入的分析，以确定哪一个是preferred（如果这是合理的？）

在每一个阶段，大家都在猜测信（不是previously猜到了）发生人数最多的剩余可能的话。

At each stage, we are guessing the letter (not previously guessed) which occurs in the largest number of remaining possible words.

有一些动机喜欢这个算法 - 我们总是最小可能失去生命。

There is some motivation to like this algorithm - we are always minimally likely to lose a life.

不过，这让我感到这并不一定是最好的解决办法：如果我们尝试猜词（内有一定数量的生活），它不一定总是这样，最频繁出现的字母是最有用的信中剩余的可用区分词汇。

But, it strikes me that this isn't necessarily the best solution: if we're trying to guess the word (within a certain number of lives), it's not necessarily always the case that the most frequently occurring letter is the most useful letter to distinguish between the remaining available words.

我不知道，不过，因为它似乎时机，以避免失去生命尽可能。他会不会是因为优化策略使我们牺牲生命为更好的机会夺冠的情况？

I'm not sure, though, as it does seem opportune to avoid losing a life wherever possible. Will it ever be the case that optimal strategy permits us to sacrifice a life for a better opportunity to win?

问：是这样，这个贪心算法相当于一个最好的机会 - - 中奖算法，还是没有？ 你可以证明这一点？

Question: is it the case that this greedy algorithm is equivalent to a best-chance-of-winning algorithm, or not? And can you prove it?

这是例子词典+游戏将是理想的显示反证。

An example dictionary+game would be ideal to show a disproof.

推荐答案

假定以下词典： ABC，ABD AEF EGH 。 （我会利用unguessed字母。） 假设你只有1点生命（使得证明变得更轻松...）。

Assume the following dictionary: ABC ABD AEF EGH. (I'll capitalize unguessed letters.) Assume you have only 1 life (makes the proof so much easier...).

上面提出的算法：

与 A 开始，你输了（1/4），或留下了 ABC，ABD AEF （3 / 4）。 现在想 B ，失去（1/3），或留下了 ABC，ABD （2/3）。 现在想 C 或 D ，你亏了（1/2）或赢（1/2）。 概率赢得：3/4 * 2/3 * 1/2 = 1/4

Starting with A, you lose (1/4) or are left with aBC aBD aEF (3/4). Now guess B and lose (1/3) or are left with abC abD (2/3). Now guess C or D and you lose (1/2) or win (1/2). Probability to win: 3/4 * 2/3 * 1/2 = 1/4.

现在尝试别的东西：

与启动电子，你输了（1/2），或留下了 AEF EGH （1/2 ）。 现在，你知道该怎么猜赢。 概率赢得：1/2

Starting with E, you lose (1/2) or are left with AeF eGH (1/2). Now you know what to guess and win. Probability to win: 1/2.

显然，该算法不是最优的。

Clearly the proposed algorithm is not optimal.