TheWordLadderProblem.ptx

<section xml:id="graphs_the-word-ladder-problem">
        <title>The Word Ladder Problem</title>
        <p>To begin our study of graph algorithms let's consider the following
            puzzle called a word ladder. Transform the word <q>FOOL</q> into the word
            <q>SAGE</q>. 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 <em>Alice in Wonderland</em>. The following sequence of words
            shows one possible solution to the problem posed above.</p>
        <pre>FOOL
POOL
POLL
POLE
PALE
SALE
SAGE</pre>
        <p>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.</p>
        <p>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:</p>
        <p><ul>
            <li>
                <p>Represent the relationships between the words as a graph.</p>
            </li>
            <li>
                <p>Use the graph algorithm known as breadth first search to find an
                    efficient path from the starting word to the ending word.</p>
            </li>
        </ul></p>
        <conclusion><p>
            <!-- extra space before the progress bar -->
        </p></conclusion>
    </section>