7.8. Construcción del grafo de la escalera de palabras¶
Nuestro primer problema es averiguar cómo convertir una gran colección de palabras en un grafo. Lo que nos gustaría es tener una arista de una palabra a otra si las dos palabras se diferencian por una sola letra. Si podemos crear tal grafo, entonces cualquier ruta de una palabra a otra es una solución al rompecabezas de la escalera de palabras. La Figura 1 muestra un pequeño grafo de algunas palabras en inglés que resuelven el problema de la escalera de palabras de FOOL a SAGE. Observe que el grafo es un grafo no dirigido y que las aristas no están ponderadas.
Figura 1: Un pequeño grafo de una escalera de palabras¶
Figura 1: Un pequeño grafo de una escalera de palabras
Podríamos utilizar varios enfoques diferentes para crear el grafo que necesitamos para resolver este problema. Comencemos con la suposición de que tenemos una lista de palabras que son todas de la misma longitud. Como punto de partida, podemos crear un vértice en el grafo por cada palabra de la lista. Para averiguar cómo conectar las palabras, podríamos comparar cada palabra en la lista con cada una de las otras. Cuando comparamos, miramos cuántas letras son diferentes. Si las dos palabras en cuestión son diferentes en una sola letra, podemos crear una arista entre ellas en el grafo. Para un pequeño conjunto de palabras, ese enfoque funcionaría bien; sin embargo supongamos que tenemos una lista de 5,110 palabras. A grandes rasgos, la comparación de una palabra con otra palabra en la lista es un algoritmo \(O(n^2)\). Para 5,110 palabras, \(n^2\) son más de 26 millones de comparaciones.
Podemos hacerlo mucho mejor usando el siguiente enfoque. Supongamos que tenemos un gran número de baldes, cada uno de ellos con una palabra de cuatro letras en el exterior, excepto que una de las letras de la etiqueta ha sido sustituido por un guión bajo. Por ejemplo, considere la Figura 2, podríamos tener un balde etiquetado como “pop_”. A medida que procesamos cada palabra en nuestra lista comparamos la palabra con cada balde, usando el ‘_’ como un comodín, de modo que tanto “pope” como “pops” coincidirían con “pop_”. Cada vez que encontremos un balde coincidente, pondremos nuestra palabra en ese balde. Una vez que tengamos todas las palabras en los baldes apropiados sabremos que todas las palabras en el balde deben estar conectadas.
Figura 2: Baldes de palabras para palabras que se diferencian por una sola letra¶
Figura 2: Baldes de palabras para palabras que se diferencian por una sola letra
En Python, podemos implementar el esquema que acabamos de describir usando un diccionario. Las etiquetas de los baldes que acabamos de describir son las claves de nuestro diccionario. El valor almacenado para esa clave es una lista de palabras. Una vez que tenemos el diccionario construido podemos crear el grafo. Iniciamos nuestro grafo creando un vértice para cada palabra en el grafo. Luego creamos aristas entre todos los vértices que encontramos para palabras encontradas bajo la misma clave en el diccionario. El Programa 1 muestra el código en Python necesario para construir el grafo.
Programa 1
from pythoned.grafos import Grafo
def construirGrafo(archivoPalabras):
d = {}
g = Grafo()
archivo = open(archivoPalabras,'r')
# crear baldes de palabras que se diferencian por una letra
for linea in archivo:
palabra = linea[:-1]
for i in range(len(palabra)):
balde = palabra[:i] + '_' + palabra[i+1:]
if balde in d:
d[balde].append(palabra)
else:
d[balde] = [palabra]
# agregar vértices y aristas para palabras en el mismo balde
for balde in d.keys():
for palabra1 in d[balde]:
for palabra2 in d[balde]:
if palabra1 != palabra2:
g.agregarArista(palabra1,palabra2)
return g
Puesto que éste es nuestro primer problema de grafos de un caso real, usted podría preguntarse: ¿qué tan ralo es el grafo? La lista de palabras de cuatro letras que tenemos para este problema es de 5,110 palabras. Si tuviéramos que usar una matriz de adyacencia, la matriz tendría 5,110 * 5,110 = 26,112,100 celdas. El grafo construido por la función construcciónGrafo tiene exactamente 53,286 aristas, por lo cual ¡la matriz tendría sólo el 0.20% de las celdas llenas! Ésa es una matriz muy rala.