Algoritmo para convertir una palabra a otra palabra cambiando cada letra por iteración que debería formar otra palabra significativa?

Question

Quiero hacer un algoritmo para cambiar una palabra a otra. Por ejemplo, la palabra dada es "MUD" y necesito convertirla a "BED". Para cada iteración puedo cambiar un carácter, pero eso debería formar otra palabra significativa. Por ejemplo, "MUD" puede cambiarse como "MAD". De esta manera, necesito encontrar el camino más corto para convertir el "MUD" a "BED".

Se proporciona un método diferente para encontrar la palabra válida. IsWord() es un método que nos dará el resultado booleano si la cadena dada es válida o no. Entonces no necesitas preocuparte por eso.

Tampoco necesito preocuparme por la eficiencia o las líneas de código, etc. ¿Alguien tiene alguna idea de cómo hacer este algoritmo? Si es así, por favor, ayúdame.

Gracias de antemano.

(sé que tenemos que utilizar el árbol y tiene que hacer el recorrido binario, pero no tengo ni idea de cómo usarlo en este algoritmo)

Answer 1

Esto se llama word ladder. Echa un vistazo a la publicación The Longest Word Ladder Puzzle Ever en Wolfram Blog.

Answer 2

crear un gráfico de la siguiente manera:

Cada palabra es un nodo y dos nodos están conectados si puede pasar de una palabra a otra en un solo paso.

Ahora encuentre la distancia más corta y la ruta entre la palabra original y la palabra final.

Consulte: http://en.wikipedia.org/wiki/Shortest_path_problem sobre cómo calcular el camino más corto.

Answer 3

En cada iteración, crea todas las palabras nuevas posibles a partir de las palabras que tienes y recógelas en una lista, conjunto o lo que sea. Elimine los duplicados y las palabras que ya tenía antes. Por ejemplo:

1. (BED) 
2. (BAD, BET, ....) 
3. (MAD, BAN, ...., BUT, BOT, ....) 

O se termina con una lista vacía, entonces el problema no tiene solución, o la palabra buscada se encuentra en la lista.

Answer 4

Empieza por tener una cola ordenada con elementos (cadenas). Cada elemento tiene una calificación/distancia (de acuerdo con una heurística) a la palabra objetivo. Esto puede ser un Hamming Distance. Y la cola ordenada usa esta distancia para presionar la palabra más cercana al objetivo.

Tome su primera palabra, agréguela a la cola. Extraiga de la cola el primer elemento, expanda todos sus elementos secundarios (palabras que se pueden obtener mediante una única conversión) y colóquelos en la cola. Haga esto hasta que el elemento que obtiene de la cola sea el que está buscando o la cola está vacía.