Búsqueda en anchura y sus usos

En la lección introductoria, jugaste con tener un personaje que se movía por un laberinto para llegar a una meta. Empezaste diciendo que la meta estaba a cero pasos de sí misma. Después encontraste todas las casillas que estaban a un paso de la meta. Después todas las casillas a dos pasos de la meta. Después tres pasos, y así sucesivamente, hasta que llegaste a la casilla en donde empezó el personaje. Si llevaste un seguimiento de cuál casilla a una distancia $k$‍ venías para pasar a una casilla a una distancia $k+1$‍, podrías dar marcha atrás para encontrar un camino desde el personaje a la meta.

Aquí hay una foto de lo que vimos en la lección introductoria:

Ahora puedes reconocerla como un grafo no dirigido. Cada vértice corresponde a una casilla que no es parte de una pared, y cada arista incide en casillas adyacentes.

El camino encontrado por el procedimiento anterior tiene una propiedad importante: ningún otro camino desde el personaje a la meta pasa por menos casillas. Eso es porque usamos un algoritmo llamado búsqueda en anchura para encontrarlo. La búsqueda en anchura, también conocida como BFS (breadth-first search en inglés), encuentra los caminos más cortos desde un vértice de origen dado a todos los demás vértices, en términos del número de aristas en los caminos.

Aquí hay otro ejemplo de búsqueda en anchura: el juego de los "seis grados de Kevin Bacon". Aquí, los jugadores tratan de conectar actores y actrices de películas con Kevin Bacon de acuerdo con una cadena de quién apareció con quién en una película. Mientras más corta la cadena, mejor, y es sorprendente cuántos actores y actrices pueden conectarse con Kevin Bacon en una cadena de seis o menos. Como un ejemplo, toma a Kate Bell, una actriz australiana. Ella estuvo en MacBeth con Nash Edgerton en 2006; Edgerton estuvo en The Matrix Reloaded con Laurence Fishburne en 2003; y Fishburne estuvo en Mystic River con Kevin Bacon en 2003. Por lo tanto, el "número Kevin Bacon" de Kate Bell es 3. De hecho, hay varias maneras de encontrar que el número Kevin Bacon de Kate Bell es 3. Puedes buscar el número Kevin Bacon de cualquier actor o actriz en el sitio web del Oráculo de Bacon.

Como podrás haber adivinado, el sitio web del Oráculo de Bacon mantiene un grafo no direccionado en el que cada vértice corresponde a un actor o una actriz, y si dos personas aparecieron en la misma película, entonces hay una arista incidente en sus vértices. Una búsqueda en anchura del vértice de Kevin Bacon encuentra la cadena más corta a todos los demás actores y actrices.

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.