寻找双词对/单词阶梯的最佳算法是什么？

Question

寻找双词对/单词阶梯的最佳算法是什么？

algorithm

5

有没有一种高效的算法可以找到一个双词/单词阶梯？可以通过蛮力方法来完成，但肯定有更好的方法。如何实现？

http://en.wikipedia.org/wiki/Word_Ladder

- user251502

4个回答

1

根据您的维基百科页面，有以下规则：

添加一个字母
删除一个字母
更改一个字母
使用不同顺序的相同字母（变位词）

将其分解为这4个子问题可能会有所帮助。

对于变位词，有一个非常简单的算法。创建一个哈希表，其中每个单词都与其按字母顺序排序的字母一起存储。例如，如果您有单词“races”，它将变成“acers”，然后匹配变位词“cares”的“acers”。这些往往工作得非常快。

至于添加一个字母和删除一个字母，基本上与变位词相同，只需创建排序字母列表，然后为您可以添加或删除的每个字母分支，直到找到一个。

如果您沿着同样的路径前进，更改一个字母似乎是最困难的，因为它有很多分支。

- Nick Larsen

我不认为在这里对字母进行排序/哈希会有用——它破坏了我们想要保留的结构（字母顺序），因此在排序字母并进行更改后，我们最终不得不搜索所有单词，其字母在排序后与新排序字母相同。 - j_random_hacker

抱歉，我没有意识到允许重新排列字母（尽管你明确写了！）在这种情况下，我可以看到优势。+1。 - j_random_hacker

0

Levenshtein Distance 似乎是一个不错的起点。计算 Levenshtein 距离所允许的步骤非常接近单词阶梯中所允许的步骤，唯一的异常是重新排列字母。您可能可以想出一个很好的启发式方法来结合 A* 和 L.D。

- Peter Recore

Levenshtein算法如果没有进行重大修改，可能不是一个好的起点，因为它对编辑距离的概念没有考虑哪些编辑会产生有效的单词，哪些不会，因此它始终低估单词之间的距离，使其成为A*算法中不可接受的启发式算法。 - kybernetikos

0

在这个游戏版本中，您只能执行一个操作：用另一个字母替换一个字母。

这使得构建搜索图相当容易，但是对于长度为4或5的单词来说速度较慢...

从根词开始，通过确定单词之间只有1个字母不同并且字母的位置很重要，检查相邻的单词。

我认为可以从广度优先搜索开始构建搜索树。问题是当你遇到永远不能连接的单词时，在你能确定它们不能连接之前，它会让您穿过大部分的图形。广度优先搜索保证可以给出从根词到目标词的最短路径。请注意，最短路径不一定是最快找到的路径。

- Dream Lane

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Hogan · Accepted Answer

如果您把这看作是一个路径查找问题，可以尝试A*算法。(基于启发式搜索的答案空间。)此外，您只想找到一个解决方案还是最佳解决方案？快速概述A*的工作原理(并稍微应用于这个问题)。要使用A*，您需要一个评估给定状态(完成状态)的函数。您希望对接近目标的状态赋予更高的值。对于这个问题，有两个示例函数:1. (每个正确的字母* 1)-(与目标不同的字母数* 10)2. (每个正确的字母* 100)-(与目标不同的字母数)正如您所看到的，第一个更喜欢单词大小接近正确的字母第二个更喜欢字母正确。不确定哪一个更好——不过您也可以做一个平衡公式。假设我们正在尝试从bot -> boat。

您需要评估男孩的所有可能变化，让我们使用第一个函数作为例子，那么您需要评估的两个示例是boot和bat（以及其他）。boot的值为3，而bat的值为-7。根据这个函数，Boot更好，因此我们将在其他任何变化之前评估Boot的所有可能变化并找到解决方案。

清楚如泥？也许维基百科能更好地解释。

http://en.wikipedia.org/wiki/A*_search_algorithm

注：

A*算法在函数设计正确的情况下，如果为给定问题存在这样的函数，则可以找到最佳解。这是A*算法的一个不错的特点。
A*算法的一种改进是短路状态查找（例如，在上面的例子中，“正3”是一个非常好的分数（4是最高分），因此您的算法可以停止查找其他状态并转而移动到非常接近的状态。）
A*算法的两个难点是1）找到正确的函数和2）能够枚举所有可能的状态。我认为使用良好的词典文件和一些快速的哈希/搜索函数可以轻松完成第二步。