es una técnica versátil para explorar el espacio de soluciones de varios tipos de problemas de ciencia de datos y construir de manera incremental soluciones candidatas, un poco como navegar por un laberinto. En este artículo, repasaremos brevemente el concepto de retroceso antes de sumergirnos en un par de ejemplos intuitivos y prácticos codificados en Python.
Nota: Todos los fragmentos de código de ejemplo en las siguientes secciones han sido creados por el autor de este artículo.
Descripción conceptual
En un alto nivel, la técnica de retroceso implica una exploración paso a paso del espacio de solución de un problema computacional (generalmente un problema que puede enmarcarse como una satisfacción de restricción o optimización combinatoria). En cada paso de la exploración, procedemos a lo largo de diferentes caminos, verificando que las limitaciones de problemas se cumplan a medida que avanzamos.
Si nos topamos con una solución válida durante nuestra exploración, lo tomamos nota. En este punto, podemos finalizar la búsqueda si nuestro problema solo requiere que encontremos una solución válida. Si el problema requiere encontrar múltiples (o todas) posibles soluciones posibles, podemos continuar explorando extensiones de la solución descubierta previamente.
Sin embargo, si en algún momento se violan las limitaciones del problema, volver hacia atrás; Esto significa volver al último punto en nuestra búsqueda donde se había construido una solución parcial (y donde las soluciones válidas aún parecían posibles), y continuando nuestra búsqueda a lo largo de una ruta diferente desde allí. Este proceso de exploración hacia adelante y hacia atrás se puede continuar según sea necesario hasta que se explore todo el espacio de la solución y se exploren todas las soluciones válidas.
Ejemplos prácticos
Resolviendo un sudoku
Un rompecabezas sudoku es un ejemplo clásico de un problema de satisfacción de restricción con aplicaciones prácticas en diversos campos que van desde investigación de operaciones a criptografía. La versión estándar del rompecabezas consiste en una cuadrícula de 9 por 9, hecha de nueve subcuadradas (o bloques) no superpuestas. En la configuración inicial del rompecabezas, algunas de las 81 celdas en la cuadrícula se preceden con dígitos que van del 1 al 9. Para completar el rompecabezas, las celdas restantes deben llenarse con dígitos de 1 a 9 mientras se adhieren a las siguientes restricciones: sin fila, columna o bloque 3 por 3 pueden contener un dígito duplicado.
El código de Python a continuación muestra cómo implementar un solucionador de Sudoku usando retroceso retroceso, junto con una función de conveniencia para imprimir bastante la cuadrícula. Tenga en cuenta que el solucionador espera que las celdas vacías se denoten (o inicialicen) con ceros.
from copy import deepcopy
def is_valid(board, row, col, num):
# Check if num is not in the current row or column
for i in range(9):
if board[row][i] == num or board[i][col] == num:
return False
# Check if num is not in the 3-by-3 block
start_row, start_col = 3 * (row // 3), 3 * (col // 3)
for i in range(start_row, start_row + 3):
for j in range(start_col, start_col + 3):
if board[i][j] == num:
return False
return True
def find_empty_cell(board):
# Find the next empty cell (denoted by 0)
# Return (row, col) or None if puzzle is complete
for row in range(9):
for col in range(9):
if board[row][col] == 0:
return row, col
return None
def solve_board(board):
empty = find_empty_cell(board)
if not empty:
return True # Solved
row, col = empty
for num in range(1, 10):
if is_valid(board, row, col, num):
board[row][col] = num
if solve_board(board):
return True
board[row][col] = 0 # Backtrack
return False
def solve_sudoku(start_state):
board_copy = deepcopy(start_state) # Avoid overwriting original puzzle
if solve_board(board_copy):
return board_copy
else:
raise ValueError("No solution exists for the given Sudoku puzzle")
def print_board(board):
for i, row in enumerate(board):
if i > 0 and i % 3 == 0:
print("-" * 21)
for j, num in enumerate(row):
if j > 0 and j % 3 == 0:
print("|", end=" ")
print(num if num != 0 else ".", end=" ")
print()Ahora, supongamos que ingresamos un rompecabezas sudoku, inicializando celdas vacías con ceros, y ejecutamos el solucionador de la siguiente manera:
puzzle = [
[5, 0, 0, 0, 3, 0, 0, 0, 7],
[0, 0, 0, 4, 2, 7, 0, 0, 0],
[0, 2, 0, 0, 6, 0, 0, 4, 0],
[0, 1, 0, 0, 9, 0, 0, 2, 0],
[0, 7, 0, 0, 0, 0, 0, 5, 0],
[4, 0, 6, 0, 0, 0, 7, 0, 1],
[0, 4, 2, 0, 7, 0, 6, 1, 0],
[0, 0, 0, 0, 4, 0, 0, 0, 0],
[7, 0, 0, 9, 5, 6, 0, 0, 2],
]
solution = solve_sudoku(puzzle)
print_board(solution)El solucionador producirá la siguiente solución en milisegundos:
5 6 4 | 1 3 9 | 2 8 7
1 9 8 | 4 2 7 | 5 6 3
3 2 7 | 8 6 5 | 1 4 9
---------------------
8 1 5 | 7 9 4 | 3 2 6
2 7 9 | 6 1 3 | 8 5 4
4 3 6 | 5 8 2 | 7 9 1
---------------------
9 4 2 | 3 7 8 | 6 1 5
6 5 3 | 2 4 1 | 9 7 8
7 8 1 | 9 5 6 | 4 3 2Descifrar un problema de la Olimpiada de Matemáticas
Olimpiadas de matemáticas son competiciones para estudiantes preuniversitarios y consisten en problemas matemáticos difíciles que deben resolverse en condiciones cronometradas sin el uso de calculadoras. Dado que explorar sistemáticamente el espacio de solución completo para tales problemas generalmente no es factible, los enfoques de solución exitosos tienden a depender del razonamiento analítico y el ingenio matemático, explotando restricciones explícitas e implícitas que obtienen la declaración del problema para optimizar la búsqueda del espacio de la solución. Algunos problemas tienen que ver con la satisfacción de la restricción y la optimización combinatoria, que también encontramos en problemas de ciencia de datos en la industria (por ejemplo, verificar si existe una ruta hacia un destino determinado, encontrando todas las rutas posibles hacia un destino, encontrando el camino más corto hacia un destino). Por lo tanto, incluso si existe un enfoque de solución matemática inteligente para un problema de la Olimpiada específica, puede ser instructivo investigar otros enfoques generalizables (como el retroceso) que explotan el poder de las computadoras de hoy y pueden usarse para resolver una amplia gama de problemas similares en la práctica.
Por ejemplo, considere el Siguiente problema Eso apareció en la Ronda 1 de la Olimpiada Matemática Británica en noviembre de 2018: “Una lista de cinco enteros positivos de dos dígitos se escribe en orden creciente en una pizarra. Cada uno de los cinco enteros es un múltiplo de 3, y cada dígito 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 aparece exactamente una vez en la pizarra. ¿De cuántas maneras se puede hacer?
Como sucede, la solución al problema anterior es 288. El siguiente video explica un enfoque de solución que explota hábilmente algunas características clave explícitas e implícitas de la declaración del problema específica (por ejemplo, la solución debe presentarse como una lista ordenada, y un número es un múltiplo de 3 si la suma de sus dígitos también es un múltiplo de 3).
El código de Python a continuación muestra cómo se puede usar el retroceso para resolver el problema:
def is_valid_combination(numbers):
# Checks if each digit from 0-9 appears exactly once in a list of numbers
digits = set()
for number in numbers:
digits.update(str(number))
return len(digits) == 10
def find_combinations():
multiples_of_3 = [i for i in range(12, 100) \
if i % 3 == 0 and '0' not in str(i)[0]]
valid_combinations = []
def backtrack(start, path):
if len(path) == 5:
if is_valid_combination(path):
valid_combinations.append(tuple(path))
return
for i in range(start, len(multiples_of_3)):
backtrack(i + 1, path + [multiples_of_3[i]])
backtrack(0, [])
return valid_combinations
print(f"Solution: {len(find_combinations())} ways")La función is_valid_combination() Especifica la restricción clave que debe mantener para cada lista válida de 5 números descubiertos durante la exploración del espacio de búsqueda. La lista multiples_of_3 Cuenta con los números candidatos que pueden aparecer en una lista válida de 5 números. La función find_combinations() aplica retroceso para probar eficientemente todas las combinaciones únicas de 5 números de multiples_of_3.
La función is_valid_combination() y la comprensión de la lista utilizada para generar multiples_of_3 Se puede modificar para resolver una amplia gama de problemas similares.
Más allá de retroceso
Como hemos visto, el retroceso es una técnica simple pero poderosa para resolver diferentes tipos de satisfacción de restricciones y problemas de optimización combinatoria. Sin embargo, también existen otras técnicas como la búsqueda de profundidad (DFS) y la programación dinámica (DP) y pueden parecer similares en la superficie, entonces, ¿cuándo tiene sentido usar el retroceso en lugar de estas otras técnicas?
El retroceso puede considerarse como una forma más estratégica de DFS, en la que la verificación de restricciones es una característica central de cada paso de decisión, y las rutas no válidas pueden abandonarse temprano. Mientras tanto, DP puede usarse para problemas que exhiben dos propiedades: subproblemas superpuestos y un subestructura óptima. Un problema tiene subproblemas superpuestos si los mismos subproblemas deben resolverse varias veces al resolver el problema más grande; Almacenar y reutilizar los resultados de los subproblemas recurrentes (p. Ej., Uso de la memoización) es una característica clave de DP. Además, un problema tiene una subestructura óptima si se puede construir una solución óptima al problema basándose en soluciones óptimas a sus subproblemas.
Ahora, considere el problema N-Queens, que mira cómo colocar norte reinas en un norte-por-norte tablero de ajedrez, de modo que no hay dos reinas se pueden atacarse entre sí; Este es un problema clásico que tiene aplicaciones en varios escenarios del mundo real donde encontrar soluciones sin conflictos es crucial (por ejemplo, asignación de recursos, programación, diseño de circuitos y planificación de rutas para robots). El problema de N-Queens no exhibe inherentemente subproblemas superpuestos o una subestructura óptima, ya que los subproblemas no necesariamente deben resolverse repetidamente para resolver el problema general, y la colocación de reinas en una parte de la junta no garantiza una ubicación óptima para todo el tablero. La complejidad inherente del problema N-Queens lo hace menos adecuado para explotar las fortalezas de DP, mientras que el retroceso se alinea más naturalmente con la estructura del problema.