7.7.字梯的问题

让我们从下面的叫字梯的难题开始图算法研究。将单词 “FOOL” 转换为单词 “SAGE”。 在字梯中你通过改变一个字母逐渐发生变化。 在每一步，你必须将一个字变换成另一个字。 字梯益智游戏是刘易斯卡罗尔 1878 年发明的，爱丽丝梦游仙境的作者。下面的单词序列示出了对上述问题的一种可能的解决方案。

  1. FOOL
  2. POOL
  3. POLL
  4. POLE
  5. PALE
  6. SALE
  7. SAGE

有许多关于字梯问题的变种。例如，可能附加了完成转换的特定数量的步骤，或者可能需要使用特定的词。在本节中，我们将计算起始字转换为结束字所需的最小转换次数。

毫不奇怪，因为这一章是图，我们可以使用图算法解决这个问题。 这里是我们需要的步骤：

  • 将字之间的关系表示为图。
  • 使用称为广度优先搜索的图算法来找到从起始字到结束字的有效路径。