PYTHON-给定一个起始单词，哪个字母序列将使您可以最大化可以拼写的有效单词的数量

Question

编辑:新问题。鉴于我怀疑这个问题比我原先想象的更难——可能是 NP 复数，我有一个不同的问题:什么是有用的算法可以接近最大化使用的字母数？

我受到启发，根据纸牌游戏 Scrabble Slam 编写了一个程序!然而，我是算法的新手，想不出解决这个问题的有效方法:

您从一个包含英语有效的 4 个字母单词的字符串开始。您可以一次在该词上放置一个字母，这样通过放置该字母就可以形成一个新的字典有效词。您拥有的字母等于字母表中的字母。

例如，如果起始词是“cart”，这可能是一个有效的移动序列:

sand --> sane --> sine --> line --> lins --> pins --> fins 等

目标是通过使用尽可能多的字母表中的字母(不多次使用一个字母)来最大化序列中的单词数。

我的算法找不到最长的序列，只能猜测最长的可能是什么。

首先，它得到一个列表，其中包含可以通过更改起始单词的一个字母而形成的所有单词。该列表称为“adjacentList”。然后它查看 adjacentList 中的所有单词，并找出这些单词中哪些单词具有最相邻的单词。无论哪个单词的相邻单词最多，它都选择将起始单词变成。

例如，sane 这个词可以变成 28 个其他词，sine 这个词可以变成 27 个其他词，word line 可以变成 30 个其他词——这些选择中的每一个都是为了最大化可以拼写越来越多的单词的可能性。

解决这个问题的最佳方法是什么？什么样的数据结构是最优的？如何改进我的代码以使其更高效、更简洁？

##Returns a list of all adjacent words.  Lists contain tuples of the adjacent word and the letter that
##makes the difference between those two words.

def adjacentWords(userWord):
    adjacentList, exactMatches, wrongMatches = list(), list(), str()
    for dictWords in allWords:
        for a,b in zip(userWord, dictWords):
            if a==b: exactMatches.append(a)
            else: wrongMatches = b
        if len(exactMatches) == 3:
            adjacentList.append((dictWords, wrongMatches))
        exactMatches, wrongMatches = list(), list()
    return adjacentList
    #return [dictWords for dictWords in allWords if len([0 for a,b in zip(userWord, dictWords) if a==b]) == 3]


def adjacentLength(content):
    return (len(adjacentWords(content[0])), content[0], content[1])

#Find a word that can be turned into the most other words by changing one letter
def maxLength(adjacentList, startingLetters):
    return max(adjacentLength(content) for content in adjacentList if content[1] in startingLetters)

def main():
    startingWord = "sand"
    startingLetters = "a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z".replace(" ", "").split(',')

    existingWords = list()
    while True:
        adjacentList = adjacentWords(startingWord)
        letterChoice = maxLength(adjacentList, startingLetters)
        if letterChoice[1] not in existingWords:
            print "Going to use letter: "+ str(letterChoice[2]) + " to spell the word "+ str(letterChoice[1]) + " with "+ str(letterChoice[0]) + " possibilities."
            existingWords.append(letterChoice[1])
            startingLetters.remove(str(letterChoice[2]))
            startingWord = letterChoice[1]


main()

Answer 1

@蛇佬腔 您可能会发现，虽然给定任务有一个最佳解决方案，但还没有已知方法以最佳方式解决它。此任务是 NP-class 之一问题。

考虑一下:

sand --> [?]and 

此时您必须遍历 [?] 和 的所有可能组合，以找出符合条件的单词。在最坏的情况下，没有启发式算法，即 26 次迭代。

sand --> band, hand, land, wand

现在，获取每个找到的单词并迭代第二个字母等。
您可以看到，您必须进行的迭代次数呈指数增长。

这在某种程度上与国际象棋的问题非常相似。无论你的计算机多么强大，它都无法预测所有可能的走法，因为组合太多了。