7.9. Implementación de la búsqueda en anchura¶
Con el grafo construido, ahora podemos concentrarnos en el algoritmo que usaremos para encontrar la solución más corta al problema de la escalera de palabras. El algoritmo de grafos que vamos a utilizar se denomina algoritmo “búsqueda en anchura”. La búsqueda en anchura (BEA) es uno de los algoritmos más sencillos para buscar en un grafo. También sirve como prototipo para otros varios algoritmos de grafos importantes que estudiaremos más adelante.
Dado un grafo \(G\) y un vértice inicial \(s\), una búsqueda en anchura procede explorando las aristas en el grafo para encontrar todos los vértices en \(G\) para los cuales hay una ruta a partir de \(s\). Lo notable de una búsqueda en anchura es que encuentra todos los vértices que estén a una distancia \(k\) de \(s\) antes de encontrar cualesquiera vértices que estén una distancia \(k+1\). Una buena manera de visualizar lo que hace el algoritmo de búsqueda en anchura es imaginar que está construyendo un árbol, un nivel del árbol a la vez. Una primera búsqueda en anchura agrega todos los hijos del vértice inicial antes de que comience a descubrir a alguno de los nietos.
Para realizar un seguimiento de su progreso, BEA pinta cada uno de los vértices en blanco, gris o negro. Todos los vértices se inicializan en blanco cuando se construyen. Un vértice blanco es un vértice no descubierto. Cuando un vértice es descubierto inicialmente es pintado de gris, y cuando BEA ha explorado un vértice completamente se pinta de negro. Esto significa que una vez que un vértice está pintado de negro, no tiene vértices blancos adyacentes a él. Un nodo gris, por otro lado, puede tener algunos vértices blancos adyacentes a él, lo que indica que todavía hay vértices adicionales por explorar.
El algoritmo de búsqueda en anchura mostrado a continuación en el Programa 2 utiliza la representación de un grafo mediante una lista de adyacencia que desarrollamos anteriormente. Además, utiliza una Cola, un punto crucial como veremos, para decidir qué vértice explorar a continuación.
Además, el algoritmo BEA utiliza una versión extendida de la clase Vertice. Esta nueva clase Vértice añade tres nuevas variables de instancia: distancia, predecesor y color. Cada una de estas variables de instancia también tiene los métodos apropiados para consulta (obtener) y asignación. El código para esta clase Vértice expandida se incluye en el paquete pythoned, pero no lo mostraremos aquí, ya que no hay nada nuevo para aprender viendo las variables de instancia adicionales.
El algoritmo BEA comienza en el vértice inicial s y pinta a inicio de gris para mostrar que está siendo explorado. Los otros dos valores, distancia y predecesor, se inicializan en 0 y None respectivamente para el vértice inicial. Finalmente, inicio se coloca en una Cola. El siguiente paso es comenzar a explorar sistemáticamente los vértices en la parte delantera de la cola. Exploramos cada nuevo nodo en el frente de la cola iterando sobre su lista de adyacencia. A medida que se examina cada nodo en la lista de adyacencia, se comprueba su color. Si es blanco, el vértice no ha sido explorado, y suceden cuatro cosas:
El nuevo vértice inexplorado
vecino, es coloreado de gris.Al predecesor de
vecinose le asigna el nodo actualverticeActualA la distancia a
vecinose le asigna la distancia averticeActual + 1vecinose agrega al final de una cola. La adición devecinoal final de la cola efectivamente programa este nodo para una exploración adicional, pero no hasta que todos los otros vértices de la lista de adyacencia deverticeActualhayan sido explorados.
Programa 2
from pythoned.grafos import Grafo, Vertice
from pythoned.basicas import Cola
def bea(g,inicio):
inicio.asignarDistancia(0)
inicio.asignarPredecesor(None)
colaVertices = Cola()
colaVertices.agregar(inicio)
while (colaVertices.tamano() > 0):
verticeActual = colaVertices.avanzar()
for vecino in verticeActual.obtenerConexiones():
if (vecino.obtenerColor() == 'blanco'):
vecino.asignarColor('gris')
vecino.asignarDistancia(verticeActual.obtenerDistancia() + 1)
vecino.asignarPredecesor(verticeActual)
colaVertices.agregar(vecino)
verticeActual.asignarColor('negro')
Veamos cómo la función bea construiría el primer árbol de búsqueda en anchura correspondiente al grafo de la Figura 1. Partiendo de fool tomamos todos los nodos que son adyacentes a fool y los agregamos al árbol. Los nodos adyacentes incluyen pool, foil, foul y cool. Cada uno de estos nodos se agrega a la cola de nuevos nodos a expandir. La Figura 3 muestra el estado del árbol en progreso junto con la cola después de este paso.
En el paso siguiente bea elimina el nodo siguiente (pool) del frente de la cola y repite el proceso para todos sus nodos adyacentes. Sin embargo, cuando bea examina el nodo cool, encuentra que el color de cool ya ha cambiado a gris. Esto indica que hay una ruta más corta para cool y que cool ya está en la cola para una expansión adicional. El único nodo nuevo agregado a la cola mientras se examina pool es poll. El nuevo estado del árbol y de la cola se muestra en la Figura 4.
El vértice siguiente en la cola es foil. El único nodo nuevo que foil puede agregar al árbol es fail. A medida que bea continúa procesando la cola, ninguno de los dos nodos siguientes agrega nada nuevo a la cola o al árbol. La Figura 5 muestra el árbol y la cola después de expandir todos los vértices del segundo nivel del árbol.
Figura 5: Árbol de la búsqueda en anchura después de completar un nivel¶
Figura 5: Árbol de la búsqueda en anchura después de completar un nivel
Usted debe seguir ejecutando el algoritmo por su cuenta para que se sienta cómodo con la forma en que funciona. La Figura 6 muestra el árbol de búsqueda en anchura final después de que todos los vértices de la Figura 3 han sido expandidos. Lo sorprendente de la solución de la búsqueda en anchura es que no sólo hemos resuelto el problema de FOOL-SAGE con el que empezamos, sino que hemos solucionado muchos otros problemas a lo largo del camino. Podemos comenzar en cualquier vértice en el árbol de búsqueda en anchura y seguir las flechas del predecesor de nuevo hacia la raíz para encontrar la escalera de palabras más corta desde cualquier palabra hasta retroceder a fool. La siguiente función (Programa 3) muestra cómo seguir los enlaces del predecesor para imprimir la escalera de palabras.
Programa 3
def recorrer(y):
x = y
while (x.obtenerPredecesor()):
print(x.obtenerId())
x = x.obtenerPredecesor()
print(x.obtenerId())
recorrer(g.obtenerVertice('sage'))