Saltar al contenido

El árbol de decisión

Lección 1 de 5 · 5 min

El árbol de decisión

Paso 1 de 8

Todo problema de backtracking es este árbol. La raíz es el camino vacío; cada nivel elige una letra más.

La idea

El backtracking es una búsqueda en profundidad (DFS) sobre un árbol que nunca construyes. Cada nodo es una respuesta parcial, cada arista es una elección y cada hoja es un candidato terminado.

El bucle siempre son los mismos tres movimientos: hacer push de una elección al camino, hacer la llamada recursiva para extenderlo y luego hacer pop. Ese pop es todo el truco: restaura el camino para que la siguiente opción empiece exactamente desde el mismo estado, y por eso una sola lista sirve para toda la búsqueda.

Ejemplo del mundo real

Probar las llaves de un llavero sin etiquetas en un edificio con varias puertas cerradas. Tomas una llave, avanzas más adentro y, cuando una puerta no abre, devuelves esa llave al llavero antes de probar la siguiente; si no, el llavero queda mal para todos los intentos que siguen.

El código

Te toca

¿Qué imprime esto?

out = []
walk(["a", "b"], [], out)
print(out)

Mini quiz

1 / 3

¿Cuáles son los tres movimientos de todo bucle de backtracking?