时间戳

首页 > 解决方案 > 算法问题：仅使用给定字典中的单词从给定单词到另一个单词的转换

algorithm - 算法问题：仅使用给定字典中的单词从给定单词到另一个单词的转换

问题描述

问题的详细描述如下：

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

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

我知道这个词可以使用广度优先搜索来解决。在我提出正常的 BFS 解决方案后，面试官问我是否可以使其更快。我没有想出加速的方法。面试官告诉我，我应该使用 PriorityQueue 来进行“Best-First-Search”。并且优先级由当前单词和目标之间的汉明距离给出。

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

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

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

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

标签： algorithmgraph

解决方案

首先，我建议对图搜索算法做一些透彻的阅读，这将把这个问题解释成你想要的任何细节（甚至远远超出）。

TL;博士：

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

它在一个方面与 BFS 不同：首先扩展哪个节点。它使用距离分数的概念，由两个元素组成：

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

如果我们要沿着通过 X 的路径，从 start 到 target 的总步数不能少于这个分数。如果实际静止距离更长（字典中不存在直接路径所需的某些单词），则可能会更多。

A* 告诉我们：在所有开放（未扩展）节点中，首先尝试可能给出最短整体解决方案路径的节点，即得分最低的节点。为了实现这一点，优先级队列非常适合。

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

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

推荐阅读