【问题】hangman游戏，在有字典的条件下的最佳猜测方式

这个问题很有意思啊 先占楼 目前仅有想法： dataset是字典，可以对字典进行所有ngram词频分析 这里ngram就是指n个字母，比如1gram就是a,b,c,d各自出现的概率,2gram就是ab,ac,ad,... 给定input 是要猜的单词长度n, 每一次hit guess(char c) API, out是True with 字母出现的位置或者False并且在可用字母中排除掉c 猜测首先是肯定要分元音aeiou和辅音 先测验元音，根据aeiou各自在字典中不同长度单词出现的1gram概率由高到底猜测单个元音字母，直到单个的出现了 其实本质上就是按给定长度n的单词中单个字母出现概率从高到低猜，元音必在辅音前面 猜出了一个元音位置后，这个时候概率优先级的list会更新 更新的内容是，已知字母位置前和后的条件概率，比如猜出了e的位置，更新所有2gram, ae,be,ce,de,... 以及ea,eb,ec,ed,ee,....的概率 这些单个prefix或suffix的字母的条件概率更新到了priority queue, 继续猜，每次猜出新的位置都要进行更新。 比如当前状态是 _ _ _ e a _ e _ _ _ _ 都要更新从 index 0 到 index n - 1每个位置各个字母概率从大到小的一个排序，而这个概率是基于各种ngram组合的 比如 eaxe中间这个未知x概率应该是基于所有当前已知来进行搜索的 不断迭代直到最后结果全部出现

【 在 Azurill 的大作中提到: 】 : 这个问题很有意思啊 先占楼 : 目前仅有想法： : dataset是字典，可以对字典进行所有ngram词频分析 这里ngram就是指n个字母，比如1gram就是a,b,c,d各自出现的概率,2gram就是ab,ac,ad,... : ................... 有点意思，

感觉有点像egg drop 策略：对于字母c属于[a..zA..Z]，定义包含该字母c的单词数为x，不包含该字母c的单词数为y，那么选择字母使得abs(x-y)最小 也就是尽量均分字典，这样总体计算次数期望在log(20000)=14次

这个游戏，等价于 huffman编码，编码对象是单词的不重复字母的组合。 既可以按词表中字母的数量进行编码 也可以按词表中字母对应词的词频进行编码 两个都可以，取决于 设置单词的人的思路。 撸了个python3代码，见： https://pastebin.com/raw/jvVFePRJ 词典用的是 https://raw.githubusercontent.com/first20hours/google-10000-english/master/google-10000-english.txt

【 在 lomizandtyd 的大作中提到: 】 : 这个游戏，等价于 huffman编码，编码对象是单词的不重复字母的组合。 : 既可以按词表中字母的数量进行编码 : 也可以按词表中字母对应词的词频进行编码 : ................... 强，稍后试一下，谢谢，

试试决策树？