La búsqueda en anchura y en profundidad

La búsqueda en anchura (en inglés, breadth-first search) y la búsqueda en profundidad (depth-first search) son las dos maneras básicas de recorrer un grafo, es decir, cualquier conjunto de cosas conectadas: las casillas de un laberinto, las páginas de la web, los amigos de los amigos, las carpetas de un disco. Las dos parten de un punto y visitan todo lo que se alcanza desde él, pero en orden distinto. La anchura avanza por capas: primero los vecinos del punto de partida, luego los vecinos de esos vecinos, y así hacia fuera, como la onda de una piedra en un estanque. La profundidad sigue un camino hasta que no puede más, retrocede hasta la última bifurcación en la que quedaba algo por probar y continúa por ahí.

La figura de esta página es un laberinto con la salida abajo a la derecha. Las dos búsquedas pintan las casillas en el orden en que las visitan y, cuando llegan a la salida, dibujan el camino que han encontrado. La anchura encuentra siempre el más corto, porque llega a cada casilla por la capa más cercana a la entrada; la profundidad encuentra uno, a veces mucho más largo, y a veces habiendo mirado menos casillas. Ni una ni otra se pierde ni repite casilla, porque las dos marcan lo que ya han visto.

Lo sorprendente es que el programa es el mismo salvo por una pieza. Las dos búsquedas guardan en algún sitio las casillas que han descubierto y aún no han explorado, y sacan de ahí la siguiente. Si ese sitio es una cola, la siguiente es la más antigua, las casillas se exploran por orden de descubrimiento y la búsqueda es en anchura. Si es una pila, la siguiente es la más reciente, el algoritmo se mete por lo último que vio y la búsqueda es en profundidad. La pila y la cola explica por qué una sola regla cambia tanto. Lo demás, marcar lo visitado y apuntar desde dónde se llegó a cada casilla para reconstruir el camino, es idéntico, y el coste también: cada casilla se visita una vez y cada pasillo se mira dos, así que las dos búsquedas son lineales en el tamaño del grafo, como diría la notación O grande.

La anchura es la herramienta del camino más corto cuando todos los pasos cuestan lo mismo. Edward Moore la describió en 1959 para el problema del laberinto, y C. Y. Lee la publicó en 1961 para un uso muy concreto: trazar las pistas de una placa de circuito impreso esquivando las que ya están puestas, un algoritmo que aún se enseña con su nombre y que sigue en el fondo de los programas que diseñan chips. Con ella se calculan los grados de separación en una red social, se encuentra la mejor jugada en un rompecabezas de pocos movimientos y se sabe qué páginas están a dos clics de otra. Si los pasos tienen pesos distintos, un kilómetro por autopista y otro por camino, la cola ya no basta: hay que sacar siempre lo más cercano y no lo más antiguo, y eso es el algoritmo de Dijkstra, que es una búsqueda en anchura con un montículo en el lugar de la cola.

La profundidad es más antigua y más versátil. Charles Pierre Trémaux, ingeniero de telégrafos, describió en el siglo XIX una regla para salir de cualquier laberinto marcando los pasillos por los que se pasa, que Édouard Lucas recogió en sus Récréations mathématiques en 1882 y que es exactamente una búsqueda en profundidad hecha a pie. Robert Tarjan demostró en 1972 que, bien hecha, da en tiempo lineal respuestas que parecen más difíciles: si un grafo tiene ciclos, en qué piezas se descompone, en qué orden hay que hacer tareas que dependen unas de otras, qué nodos lo partirían en dos si se quitaran. La razón es que la profundidad se escribe de forma natural con recursividad, una función que se llama a sí misma por cada vecino, y la pila de llamadas hace de pila sin que nadie la programe. Explorar las carpetas de un disco, resolver un sudoku probando cifras y deshaciendo, o buscar jugadas en un juego hasta cierta profundidad, es búsqueda en profundidad.

Las dos tienen un punto débil y es el contrario. La anchura tiene que recordar la capa entera que está explorando, que en una cuadrícula crece con el perímetro y en una red social puede ser de millones de personas a tres pasos de alguien; la profundidad solo recuerda el camino actual, pero en un grafo infinito o enorme puede meterse por una rama y no volver nunca. Por eso los rastreadores que indexan la web avanzan en anchura desde un puñado de páginas semilla, para cubrir mucho antes de cubrir hondo, y los programas de ajedrez exploran en profundidad hasta un límite que van subiendo, una idea llamada profundización iterativa que combina lo mejor de las dos. Y el recolector de basura de un lenguaje de programación hace una de estas búsquedas cada vez que decide qué memoria sigue en uso: lo alcanzable desde las variables vivas se queda, lo demás se tira.

Lo que queda, al final, es una moraleja sobre la atención. Un laberinto no cambia según cómo se lo recorra, pero el recorrido cambia lo que se encuentra primero. Explorar en anchura es ser paciente y completo; en profundidad, comprometerse con una idea hasta agotarla. Las dos encuentran la salida. Una la encuentra más cerca y la otra, a menudo, antes.

La pila y la cola – El algoritmo de Dijkstra – La recursividad – El montículo binario – El recolector de basura