7.7. 字梯问题¶
7.7. The Word Ladder Problem
为了开始学习图算法，我们来考虑一个叫做“词阶梯”的谜题：将单词 FOOL 转换为单词 SAGE。在词阶梯谜题中，你必须通过逐步改变一个字母来完成转换。每一步你必须将一个单词转换成另一个单词；不允许将一个单词转换为一个非单词。这个谜题由《爱丽丝梦游仙境》的作者刘易斯·卡罗尔于 1878 年发明。以下单词序列展示了上述问题的一个可能解决方案。
FOOL
POOL
POLL
POLE
PALE
SALE
SAGE
词阶梯谜题有许多变体。例如，你可能会被要求在特定的步数内完成转换，或者你可能需要使用特定的单词。在本节中，我们感兴趣的是找出将起始单词转换为结束单词所需的最少变换次数。
不出所料，由于本章讨论的是图，我们可以使用图算法来解决这个问题。下面是我们将要进行的步骤概要：
- 将单词之间的关系表示为图。
To begin our study of graph algorithms let’s consider the following puzzle called a word ladder: transform the word FOOL into the word SAGE. In a word ladder puzzle you must make the change occur gradually by changing one letter at a time. At each step you must transform one word into another word; you are not allowed to transform a word into a non-word. The word ladder puzzle was invented in 1878 by Lewis Carroll, the author of Alice in Wonderland. The following sequence of words shows one possible solution to the problem posed above.
FOOL
POOL
POLL
POLE
PALE
SALE
SAGE
There are many variations of the word ladder puzzle. For example you might be given a particular number of steps in which to accomplish the transformation, or you might need to use a particular word. In this section we are interested in figuring out the smallest number of transformations needed to turn the starting word into the ending word.
Not surprisingly, since this chapter is on graphs, we can solve this problem using a graph algorithm. Here is an outline of where we are going:
- Represent the relationships between the words as a graph.
- Use the graph algorithm known as breadth-first search to find an efficient path from the starting word to the ending word.
创建日期: 2024年9月9日