7.7. El problema de la escalera de palabras

Para comenzar nuestro estudio de los algoritmos de grafos, consideremos el siguiente rompecabezas llamado escalera de palabras. Transforme la palabra “FOOL” (tonto, en inglés) en la palabra “SAGE” (sabio, en inglés). En un rompecabezas de escalera de palabras usted debe hacer que el cambio se produzca gradualmente mediante el cambio de una letra a la vez. En cada paso usted debe transformar una palabra en otra palabra, no se le permite transformar una palabra en una cadena que no sea una palabra. El rompecabezas de escalera de palabras fue inventado en 1878 por Lewis Carroll, el autor de Alicia en el País de las Maravillas. La siguiente secuencia de palabras en inglés muestra una posible solución al problema planteado anteriormente.

FOOL
POOL
POLL
POLE
PALE
SALE
SAGE

Hay muchas variantes del rompecabezas de escalera de palabras. Por ejemplo, podrían darle a usted un número determinado de pasos en los que se debe realizar la transformación, o podría tener que utilizar una palabra en particular. En esta sección nos interesa averiguar el menor número de transformaciones necesarias para convertir la palabra inicial en la palabra final.

No es de extrañar, ya que este capítulo trata sobre grafos, que podamos resolver este problema usando un algoritmo de grafos. El siguiente es un esquema de hacia dónde vamos:

• Representar las relaciones entre las palabras como un grafo.

• Usar el algoritmo de grafos conocido como búsqueda en anchura para encontrar una ruta eficiente desde la palabra inicial hasta la palabra final.

You have attempted of activities on this page