3

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

我受到启发写了一个基于纸牌游戏 Scrabble Slam 的程序！但是，我是算法新手，想不出解决这个问题的有效方法：

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

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

sand --> sane --> sine --> line --> lins --> pin --> fins 等。

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

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

首先，它获取所有单词的列表，这些单词可以通过改变起始单词的一个字母来组成。该列表称为“相邻列表”。然后它会查看相邻列表中的所有单词，并找出其中哪些单词具有最相邻的单词。无论哪个单词有最相邻的单词，它都会选择将起始单词变成。

例如，单词 sane 可以变成另外 28 个单词，单词 sine 可以变成另外 27 个单词，单词 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()
4

2 回答 2

3

@Parseltongue您可能会发现，尽管对于给定的任务有一个最佳解决方案，但是没有已知的方法可以以最佳方式解决它。该任务是NP 类问题之一。

考虑一下：

sand --> [?]and

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

sand --> band, hand, land, wand

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

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

于 2011-08-12T09:10:00.020 回答
0

我和一个朋友实际上在数据结构和算法课程的实验室中开发了一个类似的程序（不过是在 Java 中）。任务是创建从一个单词到另一个单词的最短单词链。

我们建立了所有可用单词的树，其中一个节点连接到另一个节点，如果它们仅相差一个字母。为了速度，需要使用某种哈希表，例如字典。我们实际上从我们用作键的单词中删除了一个字母，从而利用了连接单词然后具有相同哈希的事实，但是如果没有代码就很难解释。

为了找到最短的链，我们只使用了广度优先搜索。然而，在图中找到最短路径比找到最长路径更容易。有关详细信息，请参阅最长路径问题。

要解决主要问题，您可以遍历所有单词。但是，如果速度很重要，那么尝试找到一个好的特殊启发式算法通常更容易。

于 2011-08-12T09:15:42.373 回答