首先，这不是家庭作业问题。我从1988年就不用做作业了!
- 我有一个长度为N的单词列表
- 我最多有13个字符可供选择。
- 可以有多个相同的字母
给定单词列表，哪13个字符最可能拼写单词。我可以抛出一些使问题更难解决的单词，例如:
speedometer has 4 e's in it, something MOST words don't have,
so I could toss that word due to a poor fit characteristic, or it might just
go away based on the algorithm
我已经看了@字母分布，我已经建立了一个单词的图表(一个字母一个字母)。我遗漏了一些东西，或者这个问题比我想象的要难得多。如果可能的话，我宁愿不完全使用蛮力，但我现在已经到了那个地步了。
我想到了遗传算法，但我以前从未尝试过....
似乎我需要一种方法来评分每个字母基于它与其他字母在....中的单词的关联
这听起来像是一个很难的组合问题。你有一个包含D个单词的字典，你可以选择N个字母(可能有重复)来覆盖/生成D中尽可能多的单词。我有99.9%的把握可以证明它是一个np完全优化问题(假设可能是字母表，即包含超过26个项目的一组字母)，但我把实际的缩减作为练习留给读者:)
假设它很难，你有通常的路线:
- 分支与绑定 随机搜索
- <
- 近似算法/gh>
我能想到的最好的是分支和绑定。创建一个由
组成的"中间状态"数据结构- 您已经使用过的字母(具有多重性)
- 仍然可以使用的字符数
- 信件仍然可用
- 列表中仍然存在的单词数(前一组的计数)
- 当前状态下不允许输入的字数
- 您选择的字母已经覆盖的单词数
从
开始- 空集 13
- {a, b，…, Z}
- 您的整个列表
- N
- 0
- 0
将该数据结构放入队列。
每一步
Pop an item from the queue
Split into possible next states (branch)
Bound & delete extraneous possibilities
从一个状态，我将生成如下可能的下一个状态:
For each letter L in the set of letters left
Generate a new state where:
you've added L to the list of chosen letters
the least letter is L
so you remove anything less than L from the allowed letters
所以，举个例子，如果你的剩余集合是{W, X, Y, Z}，我将生成一个将W添加到我的选择中的状态，{W, X, Y, Z}仍然可能，一个将X作为我的选择，{X, Y, Z}仍然可能(但不包括W)，一个将Y作为我的选择，{Y, Z}仍然可能，以及一个将Z作为我的选择，{Z}仍然可能。
做所有不同的计算来找出新的状态。
每个州至少有"你选择的字母已经涵盖的单词数量"的单词，最大这个数字加上"你的列表中仍然存在的单词数量"。在所有状态中，找出最大的最小值，并删除所有大于最大值的状态。
无需对速度计进行特殊处理。
我无法想象这将会很快，但它会工作。
可能有一些优化(例如，将列表中的每个单词存储为出现次数为A-Z的数组，并将具有相同结构的单词组合在一起:2次出现AB.....。T => BAT和TAB)。如何排序和跟踪最小值和最大值可能也会有所帮助。可能不足以产生渐近差异，但对于一个大到足以让它在合理时间内运行而不是在极端时间内运行的问题。
完全的暴力强制应该可以工作，尽管实现会变得相当混乱。
与其把像speedometer这样的词扔出去，难道你不能只考虑这个字符是否出现在这个词中(不管有没有)来生成关联图吗?很多时候，它似乎与13个字符的最终最佳选择没有任何关系)。这也会使它比完全的暴力更简单。
欢迎评论。
除去包括字母大小在内的每个参数的边界，从最大覆盖问题中得到一个简单的目标保持约简，该问题是np困难的，难以近似，其比率优于(e - 1)/e≈0.632。它是固定参数的，可以通过蛮力处理字母大小。
我同意Nick Johnson的蛮力建议;在最坏的情况下，只有(13 + 26 - 1)个选择(26 - 1)多集，也就是大约50亿个。如果你把每个字母的数量限制在可能有用的范围内，这个数字就会小得多。即使它太慢，您也应该能够回收数据结构。
我完全不明白"我最多有13个字符可供选择。"。如果你有一个1000字的列表，那么你的意思是你必须把它减少到13个字符吗?
基于我(错误)理解的一些想法:
如果你只处理英语单词，那么你可以跳过元音，因为辅音同样具有描述性。我们的大脑可以填补元音——也就是短信/推特语言:)
也许对于1-3个字母的单词，剥离元音会丢失太多信息。但仍然:
词干提取会使单词更短。先词干，然后去掉元音。然后做一个直方图....spdmtr 's 4 's在t上，smthingMST单词没有，它是冷的TSS:《世界末日》是一部电影天哪，这可能是我的错为什么BSD的长度