University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
School of Computer Science
My Home Page

CSC 477/677 Using the A* Algorithm to Find a Word Ladder
A word ladder is a sequence of words, where each differs from
its predecessor by one letter. For example
WARM
WARD
CARD
CORD
COLD
is a word ladder, and is in fact the shortest possible
word ladder from WARM to COLD. (There are others of the same length.)
In a computer science class at Duke University, students were required
to write a program to find the shortest word ladder between two five letter
English words, using Donald Knuth's database of five letter words.
You can read their assignment
here.
These students were instructed to use a simple breadth-first search
algorithm, using a queue. However, you can do much better, by using
the A* algorithm. Explain, in detail, how you would do this.
One detail you may not omit: exactly what heuristic
would you use?
Do not turn in any actual computer code.