算法题: Word transformation from a given word to another using only the words in a given dict

Question

问题详细描述如下:

给定两个单词(beginWord 和 endWord)和字典的单词列表，找出是否存在从 beginWord 到 endWord 的转换序列，这样:

1. 一次只能更改一个字母
2. 每个转换后的单词必须存在于单词列表中。请注意，beginWord 不是转换后的词。

我知道这个词可以用广度优先搜索来解决。我提出正常的BFS方案后，面试官问我能不能做得更快。我没有想出加快速度的方法。面试官告诉我应该使用 PriorityQueue 来代替“最佳优先搜索”。优先级由当前词和目标之间的汉明距离决定。

不太明白为什么这样可以加快搜索速度。我觉得通过使用 priorityQueue 我们尝试搜索取得进展的路径(即减少汉明距离)。

这似乎是一个贪婪的方法。我的问题是:

为什么这个解决方案比广度优先搜索解决方案更快？我感觉实际的路径可以是这样的:一开始没有任何进展，甚至增加了汉明距离，但是到了一个词之后汉明距离逐渐下降。这种场景下，我觉得优先级队列方案会比较慢。

任何建议将不胜感激!谢谢

Answer 1

首先，我建议您通读一些有关图搜索算法的文章，这将解释问题的任何您想要的细节(甚至远远超出)。

长话短说:

您的面试官有效地推荐了一些接近 A* 算法的东西。

它和BFS有一个不同点:先扩展哪个节点。它使用距离分数的概念，由两个元素组成:

• 在节点 X 处，我们已经“行进”了由到目前为止的转换次数给出的距离。
• 要从 X 到达目标，我们还需要多走一些路，至少 N 步，其中 N 是节点和目标之间不同的字符数。

如果我们要沿着 X 的路径走，从开始到目标的总步数不能小于这个分数。如果真正的静止距离更长(一些直接路径所需的单词在字典中不存在)，则可以更多。

A* 告诉我们:在所有开放(未扩展)节点中，首先尝试可能给出最短整体解决方案路径的节点，即得分最低的节点。要实现这一点，优先级队列是一个很好的选择。

在许多情况下，A* 可以显着减少搜索空间(与 BFS 相比)，并且仍然保证找到最佳解决方案。

A* 不是贪心算法。它最终将探索整个搜索空间，只是顺序比盲 BFS 好得多。