算法问题：使用给定字典中的词将一个单词转换为另一个单词

Question

问题的详细描述如下：

给定两个单词（beginWord和endWord），以及一个字典单词列表，查找是否存在从beginWord到endWord的转换序列，使得：

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

我知道可以使用广度优先搜索来解决这个问题。在我提出了普通的BFS解决方案之后，面试官问我能否加速。我没有想出加速的方法。面试官告诉我应该使用PriorityQueue来进行“最佳优先搜索”，并且优先级由当前单词和目标之间的汉明距离给出。

我不太理解为什么这样可以加快搜索。我觉得通过使用PriorityQueue，我们尝试搜索使进展的路径（即减少汉明距离）。

这似乎是一种贪心方法。我的问题是：

为什么这个解决方案比广度优先搜索解决方案更快？我认为实际路径可能是这样的：一开始没有取得任何进展，甚至增加了汉明距离，但在达到一个单词后，汉明距离逐渐减小。在这种情况下，我认为优先队列解决方案会更慢。

任何建议都将不胜感激！谢谢

- Patrick

---

这与比较Dijkstra算法和A*算法非常相似。它仍然可能探索所有可能性，但是首先选择最有前途的。 - Henry

@Henry 谢谢回复。我还是没太明白。为什么它类似于比较Dijkstra算法和A算法？我觉得Dijkstra已经是最优的了。A比这还要快吗？我感到困惑的是：如果我们还想找到到达目的地的最小步数，我们还能使用优先队列解决方案吗？我感到困惑，因为我觉得广度优先搜索已经提供了最佳性能。 - Patrick

区别在于一个“盲目”搜索所有方向直到偶然找到解决方案的算法和另一个具有某种概念并尝试朝着目标方向的方法。后一种方法通常更好，除了一些簿记工作外，从不更差。 - Henry

我认为使用priorithqueue的方式并没有从根本上加速算法，只是增加了“可能性”。 - ZhaoGang

它只是在单次执行中更有可能更快地得到答案，但并不保证。我认为如果这个算法被多次执行，它会加速。 - ZhaoGang

A*是一种机会主义优化。真正的优化（面试官显然也错过了）是从两端同时运行BFS，直到它们在中途相遇。如果距离为d，平均分支因子为f，单个BFS将探索k ** d个节点，而两个BFS仅探索2 * k ** (d / 2)个节点。 - user58697

Answer 1

首先，我建议您对图搜索算法进行深入阅读，这将详细解释您想要的所有问题（甚至超出您的预期）。

简而言之：

您的面试官实际上推荐了类似于A*算法的东西。

与BFS不同的是：要首先扩展哪个节点。它使用距离得分的概念，由两个元素组成：

1. 在节点X处，我们已经“旅行”了迄今为止的变换次数所给出的距离。 2. 要从X到达目标，我们仍然需要走一些路程，至少N步，其中N是节点和目标之间不同字符的数量。

如果我们要沿着X的路径走，从开始到目标的总步数不能少于此分数。如果真正的剩余距离更长（直接路径所需的某些单词不存在于字典中），则可以更多。

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

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

A*不是贪心算法。它最终会探索整个搜索空间，只是比盲目的BFS更有序。

- Ralf Kleberhoff