Técnicas Algorítmicas Esenciales: Backtracking, Programación Dinámica y Grafos en Python

Algoritmos de Backtracking

El Backtracking es una técnica algorítmica para encontrar soluciones a problemas de forma recursiva, construyendo soluciones paso a paso y eliminando aquellas que no cumplen las restricciones.

Problema del Laberinto

Implementación de un algoritmo de backtracking para encontrar un camino en un laberinto.

def generar_sucesores(estado: tuple, laberinto: list[list[int]], visitados: set) -> list:
    sucesores = []
    n = len(laberinto)
    x, y = estado
    direcciones = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    for dx, dy in direcciones:
        nx, ny = x + dx, y + dy
        sucesor = (nx, ny)
        if 0 <= nx < n and 0 <= ny < n and not laberinto[nx][ny] and sucesor not in visitados:
            sucesores.append(sucesor)
    return sucesores

def es_solucion(estado: tuple, salida: tuple) -> bool:
    return estado == salida

def tratar_solucion(camino: list, soluciones: list):
    soluciones.append(camino[:])
    print(camino)

def backtracking(candidatos: list, soluciones: list, laberinto: list[list[int]], salida: tuple, nivel: int = 0) -> bool:
    if es_solucion(candidatos[-1], salida):
        tratar_solucion(candidatos, soluciones)
        return True

    hijos = generar_sucesores(candidatos[-1], laberinto, set(candidatos))
    salir = False
    pos = 0
    while pos < len(hijos) and not salir:
        candidatos.append(hijos[pos])
        salir = backtracking(candidatos, soluciones, laberinto, salida, nivel + 1)
        candidatos.pop()
        pos += 1
    return salir

# Parámetros de ejemplo para la llamada inicial: laberinto, inicio, fin
# Ejemplo de llamada: backtracking(camino_actual, soluciones, laberinto, salida)

Problema de las N-Reinas

Resolución del clásico problema de las N-Reinas, donde se busca colocar N reinas en un tablero N×N sin que se ataquen entre sí.

def es_seguro(tablero: list[list[int]], fila: int, columna: int) -> bool:
    # Comprobar columna
    for i in range(fila):
        if tablero[i][columna] == 1:
            return False

    # Comprobar diagonal principal (arriba-izquierda)
    for i, j in zip(range(fila, -1, -1), range(columna, -1, -1)):
        if tablero[i][j] == 1:
            return False

    # Comprobar diagonal secundaria (arriba-derecha)
    # N debe estar definido globalmente o pasarse como parámetro
    # Asumimos N es el tamaño del tablero
    N = len(tablero)
    for i, j in zip(range(fila, -1, -1), range(columna, N, 1)):
        if tablero[i][j] == 1:
            return False
    return True

def problema_n_reinas(tablero: list[list[int]], soluciones: list[list[list[int]]], nivel: int = 0) -> None:
    N = len(tablero) # Obtener N del tablero
    if nivel == N:
        soluciones.append([row[:] for row in tablero])
        return

    hijos = [] # Generamos los nuevos hijos
    for col in range(N):
        if es_seguro(tablero, nivel, col):
            hijos += [col]

    for col in hijos:
        tablero[nivel][col] = 1
        problema_n_reinas(tablero, soluciones, nivel + 1)
        tablero[nivel][col] = 0

# Ejemplo de uso:
# N = 8
# tablero = [[0] * N for _ in range(N)]
# soluciones = []
# problema_n_reinas(tablero, soluciones)

Recorrido del Caballo

Implementación del problema del Recorrido del Caballo, buscando un camino que visite cada casilla de un tablero una única vez.

def generar_sucesores(estado: tuple, tablero: list[list[int]], F: int, C: int) -> list:
    sucesores = []
    x, y = estado
    dirs = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]

    for dx, dy in dirs:
        nx, ny = x + dx, y + dy
        if 0 <= nx < F and 0 <= ny < C and tablero[nx][ny] == 0: # Casilla no visitada
            sucesores.append((nx, ny))
    return sucesores

def es_solucion(paso: int, F: int, C: int) -> bool:
    return paso == F * C # Si se han recorrido todas las casillas

def tratar_solucion(tablero: list[list[int]]):
    # Imprime el tablero con el recorrido del caballo
    for fila in tablero:
        print(' '.join(f'{x:2}' for x in fila))
    print()

def backtracking(tablero: list[list[int]], F: int, C: int, x: int, y: int, paso: int) -> bool:
    if es_solucion(paso, F, C):
        tratar_solucion(tablero)
        return True # Caso base

    sucesores = generar_sucesores((x, y), tablero, F, C) # movimientos válidos
    for nx, ny in sucesores:
        tablero[nx][ny] = paso + 1 # Marcar casilla
        if backtracking(tablero, F, C, nx, ny, paso + 1):
            return True
        tablero[nx][ny] = 0 # Backtrack: desmarcar
    return False

def resolver_recorrido_caballo(F: int, C: int, x_inicial: int, y_inicial: int):
    tablero = [[0 for _ in range(C)] for _ in range(F)] # Crear tablero vacío
    tablero[x_inicial][y_inicial] = 1 # Primer paso

    if not backtracking(tablero, F, C, x_inicial, y_inicial, 1):
        print("No se encontró solución.")

# Ejemplo de uso:
# F, C = 8, 8
# x_inicial, y_inicial = 0, 0
# resolver_recorrido_caballo(F, C, x_inicial, y_inicial)

Para los problemas de la mochila que siguen, se utiliza la siguiente función auxiliar para definir objetos:

def _objeto(nombre: str, valor: float, volumen: float) -> dict:
    return {'nombre': nombre, 'valor': valor, 'volumen': volumen} # Diccionario para objeto

Problema de la Mochila (Backtracking)

Resolución del problema de la mochila utilizando backtracking para encontrar la combinación de objetos de mayor valor que no exceda una capacidad dada.

def sumar(mochila: list[_objeto], campo: str) -> float:
    # Suma el valor o volumen de los objetos
    assert campo == 'valor' or campo == 'volumen'
    suma = 0
    for objeto in mochila:
        suma += objeto[campo]
    return suma

def mochila_backtracking(objetos: list[_objeto], capacidad: float, solucion: list[_objeto], candidatos: list[_objeto] = [], nivel: int = 0) -> None:
    if sumar(candidatos, 'valor') > sumar(solucion, 'valor'):
        solucion.clear()
        solucion.extend(candidatos)

    hijos = []
    volumen_actual = sumar(candidatos, 'volumen')

    for objeto in objetos:
        if volumen_actual + objeto['volumen'] <= capacidad and objeto not in candidatos:
            hijos.append(objeto)

    for hijo in hijos:
        candidatos.append(hijo)
        mochila_backtracking(objetos, capacidad, solucion, candidatos, nivel + 1)
        candidatos.pop()

# Ejemplo de uso:
# objetos = [_objeto('Tablet', 100, 1), _objeto('Laptop', 500, 5), _objeto('Auriculares', 50, 0.5)]
# capacidad = 4
# mejor_solucion = []
# mochila_backtracking(objetos, capacidad, mejor_solucion)
# print(f"Mejor combinación de objetos: {[obj['nombre'] for obj in mejor_solucion]}")
# print(f"Valor total: {sumar(mejor_solucion, 'valor')}")

Problema de las Jarras de Agua (Búsqueda en Profundidad – DFS)

Resolución del problema de las jarras de agua, buscando una secuencia de operaciones para alcanzar un estado deseado.

def operaciones(estado: tuple) -> dict:
    # Diccionario con operaciones posibles sobre las jarras
    jarra_4, jarra_3 = estado
    return {
        "Llenar jarra de 4 litros": (4, jarra_3),
        "Llenar jarra de 3 litros": (jarra_4, 3),
        "Vaciar jarra de 4 litros": (0, jarra_3),
        "Vaciar jarra de 3 litros": (jarra_4, 0),
        "Verter de jarra de 4 a jarra de 3": (max(0, jarra_4 - (3 - jarra_3)), min(3, jarra_4 + jarra_3)),
        "Verter de jarra de 3 a jarra de 4": (min(4, jarra_4 + jarra_3), max(0, jarra_3 - (4 - jarra_4))),
    }

def generar_sucesores(estado: tuple, visitados: set) -> list:
    # Genera sucesores del estado actual
    sucesores = []
    for _, sucesor in operaciones(estado).items():
        if sucesor not in visitados:
            sucesores.append(sucesor)
    return sucesores

def busqueda_en_profundidad(estado_inicial: tuple) -> list:
    # Encuentra el camino hasta que la jarra de 4L tenga 2L
    visitados = set()
    pila = [(estado_inicial, [estado_inicial])] # Pila para DFS

    while pila:
        estado_actual, camino = pila.pop()
        jarra4, _ = estado_actual
        if jarra4 == 2:
            return camino # Solución encontrada

        visitados.add(estado_actual)
        sucesores = generar_sucesores(estado_actual, visitados)

        for sucesor in reversed(sucesores):
            pila.append((sucesor, camino + [sucesor]))
    return [] # No hay solución

Concepto General de Backtracking

El Backtracking se asemeja a un recorrido en profundidad dentro de un árbol cuya existencia solo es implícita (árbol de expansión).

Idea Principal:

• Al llegar a un nodo (al entrar en una llamada recursiva) se tiene una solución parcial formada por k-1 etapas.
• Se generan todas las decisiones posibles a partir de la solución parcial actual.
• Para cada una de esas decisiones, se incorpora a la solución parcial (por lo que ahora tendrá k etapas) y se comprueba si se ha conseguido una solución total.

Gestión de Soluciones:

Una vez comprobada la solución, tendremos dos opciones:

1. Si es una solución: se gestiona (se guarda en una estructura de soluciones, se compara con otras anteriores) y termina la búsqueda.
2. Si no: si se detecta que la solución parcial es completable, se hace una nueva llamada recursiva con la nueva solución parcial y el nuevo nivel.

Modificaciones Comunes:

• Si lo que se buscaba era una solución al problema, el algoritmo debe terminar en el punto (1).
• Si lo que se querían todas las soluciones, el procedimiento recursivo necesitará otra estructura para almacenar las soluciones encontradas, por ejemplo, una lista que se actualice en (1).
• Si se buscaba la mejor solución al problema, el procedimiento necesitará un parámetro que guarde la mejor solución encontrada hasta el momento para decidir si actualizarla en (1).

Eficiencia:

Suponiendo que hay n etapas y m posibles decisiones en cada una de ellas, el orden de eficiencia está en O(mⁿ). En general, la eficiencia depende de:

• El tiempo necesario para generar las decisiones posibles.
• La cantidad de decisiones posibles que se obtienen.
• En mucha menor medida, el tiempo que se tarda en comprobar es_solucion y tratar_solucion.

Algoritmos de Grafos

Algoritmo de Warshall (Conectividad)

Implementación del algoritmo de Warshall para determinar la existencia de caminos entre todos los pares de nodos en un grafo.

def warshall_haycamino(grafo):
    nodos = {}
    pos = 0
    for v in grafo:
        nodos[v] = pos
        pos += 1

    n = len(nodos)
    relacionados = [[False] * n for _ in range(n)]

    for origen in nodos:
        i = nodos[origen]
        relacionados[i][i] = True
        for destino, peso in grafo[origen].items():
            j = nodos[destino]
            relacionados[i][j] = True

    for k in range(n):
        for i in range(n):
            for j in range(n):
                relacionados[i][j] = relacionados[i][j] or (relacionados[i][k] and relacionados[k][j])
    return nodos, relacionados

# Ejemplo de uso:
# grafo = {
#     'a': {'b': 4, 'c': 3},
#     'b': {'d': 5},
#     'c': {'b': 2, 'd': 3, 'e': 6},
#     'd': {'f': 5, 'e': 1},
#     'e': {'g': 5},
#     'g': {'z': 4},
#     'f': {'g': 2, 'z': 7},
#     'z': {}
# }
# nodos, relacionados = warshall_haycamino(grafo)
# print('Relacionados:')
# for fila in relacionados:
#     for elem in fila:
#         print('true   ' if elem else 'no   ', end='')
#     print()

Algoritmo de Floyd-Warshall (Caminos Más Cortos entre Todos los Pares)

Implementación del algoritmo de Floyd-Warshall para encontrar los caminos más cortos entre todos los pares de vértices en un grafo ponderado.

def floyd_warshall(grafo):
    nodos = {}
    pos = 0
    for v in grafo:
        nodos[v] = pos
        pos += 1

    distancias = []
    caminos = []
    for _ in nodos:
        distancias.append([float('inf')] * len(nodos))
        caminos.append([None] * len(nodos))

    for origen in grafo:
        i = nodos[origen]
        distancias[i][i] = 0
        caminos[i][i] = origen
        for destino, peso in grafo[origen].items():
            j = nodos[destino]
            distancias[i][j] = peso
            caminos[i][j] = origen

    n = len(nodos)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if distancias[i][k] + distancias[k][j] < distancias[i][j]:
                    distancias[i][j] = distancias[i][k] + distancias[k][j]
                    caminos[i][j] = caminos[k][j]
    return nodos, distancias, caminos

# Ejemplo de uso:
# grafo = {
#     'a': {'b': 4, 'c': 3},
#     'b': {'d': 5},
#     'c': {'b': 2, 'd': 3, 'e': 6},
#     'd': {'f': 5, 'e': 1},
#     'e': {'g': 5},
#     'g': {'z': 4},
#     'f': {'g': 2, 'z': 7},
#     'z': {}
# }
# nodos, distancias, caminos = floyd_warshall(grafo)
# print('Distancias:')
# for fila in distancias:
#     for elem in fila:
#         print(f'{elem:5}', end='')
#     print()
# print('Caminos:')
# for fila in caminos:
#     for elem in fila:
#         print(f'{elem:5}' if elem else 'no   ', end='')
#     print()

Algoritmos de Programación Dinámica

Problema de la Mochila (Programación Dinámica)

Resolución del problema de la mochila utilizando programación dinámica para encontrar el valor máximo que se puede obtener sin exceder la capacidad.

def mochila_dinamica(objetos: list[_objeto], capacidad: int):
    n = len(objetos)
    capacidades = []
    for i in range(capacidad * 2 + 1):
        capacidades += [i / 2]

    matriz = []
    for f in range(n + 1):
        matriz += [[]]
        for c in range(len(capacidades)):
            matriz[f] += [0]

    for i in range(1, n + 1):
        for j in range(1, len(capacidades)):
            if objetos[i - 1]['volumen'] <= capacidades[j]:
                anterior = capacidades[j] - objetos[i - 1]['volumen']
                col = 0
                while capacidades[col] < anterior:
                    col += 1
                nuevo = objetos[i - 1]['valor'] + matriz[i - 1][col]
                matriz[i][j] = max(nuevo, matriz[i - 1][j])
            else:
                matriz[i][j] = matriz[i - 1][j]
    return matriz[n][-1]

# Ejemplo de uso:
# objetos = [_objeto('Tablet', 100, 1), _objeto('Laptop', 500, 5), _objeto('Auriculares', 50, 0.5)]
# capacidad = 4
# print(mochila_dinamica(objetos, capacidad))

Problema del Mínimo Coste en Matriz

Cálculo del camino de mínimo coste en una matriz, permitiendo movimientos hacia abajo y hacia la derecha.

def minimo_coste(matriz_dada: list[list[int]]) -> int:
    filas = len(matriz_dada)
    columnas = len(matriz_dada[0])
    matriz = [[0] * columnas for _ in range(filas)]
    matriz[0][0] = matriz_dada[0][0]

    for i in range(1, filas):
        matriz[i][0] = matriz[i - 1][0] + matriz_dada[i][0] # solo movernos hacia abajo

    for j in range(1, columnas):
        matriz[0][j] = matriz[0][j - 1] + matriz_dada[0][j] # movernos hacia la derecha

    for i in range(1, filas):
        for j in range(1, columnas):
            matriz[i][j] = min(matriz[i - 1][j], matriz[i][j - 1]) + matriz_dada[i][j]
    return matriz[filas - 1][columnas - 1]

Problema de la Mochila con Billetes (Programación Dinámica con Cantidad Limitada)

Resolución del problema de la mochila para un sistema de cambio de moneda, donde cada billete tiene una cantidad limitada.

def billetes_usados(valor: int, cantidad: int) -> dict:
    return {'valor': valor, 'cantidad': cantidad}

def mochila(billetes: list, capacidad: int):
    INF = float('inf')
    lon = len(billetes)
    dp = [INF] * (capacidad + 1)
    dp[0] = 0 # 0 billetes para lograr 0€
    usados = [[0] * (capacidad + 1) for _ in range(lon)] # matriz para reconstruir solución

    for fila in range(1, lon + 1):
        billete = billetes[fila - 1]
        for cap in range(capacidad, -1, -1): # recorrer hacia atrás
            if dp[cap] != INF:
                max_u = min(billete['cantidad'], (capacidad - cap) // billete['valor']) # cuántos caben
                for u in range(1, max_u + 1):
                    nueva_cap = cap + billete['valor'] * u
                    if nueva_cap > capacidad:
                        break
                    if dp[nueva_cap] > dp[cap] + u:
                        dp[nueva_cap] = dp[cap] + u
                        # Actualizar la matriz de usados para reconstruir la solución
                        for i in range(lon):
                            usados[i][nueva_cap] = usados[i][cap]
                        usados[fila - 1][nueva_cap] = u

    if dp[capacidad] == INF:
        print(f"No se puede devolver exactamente {capacidad}€")
        return None
    else:
        print(f"Sí se puede devolver {capacidad}€ con {dp[capacidad]} billetes:")
        for i in range(lon):
            if usados[i][capacidad] > 0:
                print(f" - {usados[i][capacidad]} billete(s) de {billetes[i]['valor']}€")
        return dp[capacidad]

# Ejemplo de uso:
# billetes = [billetes_usados(1, 8), billetes_usados(2, 3)]
# capacidad = 13
# mochila(billetes, capacidad)