algorithm - 通过有效词从一个词到另一个词的最短路径（无图）

Question

我遇到了这种编辑距离问题的变体：

找到从一个词到另一个词的最短路径，例如storm->power，使用isValidWord()函数验证每个中间词。没有其他对单词字典的访问权限，因此无法构建图形。

我试图弄清楚这一点，但它本身似乎不是与距离相关的问题。也许使用简单的递归？但是，你怎么知道你正朝着正确的方向前进呢？

其他人觉得这很有趣吗？期待一些帮助，谢谢！

Answer 1

这是刘易斯卡罗尔的一个谜题，被称为字梯。Donald Knuth 在 The Stanford Graphbase中对此进行了介绍。这也是

您可以将其视为广度优先搜索。您将需要访问字典，否则您必须搜索的空间将是巨大的。如果您只能访问一个有效的单词，您可以生成单词的所有排列，然后只需使用 isValidWord() 将其过滤掉（Norvig 的“如何编写拼写校正器”是生成编辑的一个很好的解释）。

您可以通过尝试最小化您当前所在位置与您可能所在位置之间的编辑距离来指导搜索。比如生成所有节点的空间进行搜索，按照最小编辑距离排序。首先跟随最接近目标的链接（例如最小化编辑距离）。在示例中，跟随最接近“电源”的节点。

我也觉得这很有趣，所以这里有一个 Haskell 实现，它运行得相当好。评论中有一个指向Clojure 版本的链接，该版本具有一些非常好的可视化效果。

Answer 2

您可以同时从两侧进行搜索。即在storm 中更改一个字母并通过isValidWord() 运行，在power 中更改一个字母并通过isValidWord() 运行。如果这两个词是相同的，那么你已经找到了一条路径。