> ## Documentation Index
> Fetch the complete documentation index at: https://apuntes.simulab.es/llms.txt
> Use this file to discover all available pages before exploring further.

# Backtracking (vuelta atrás): mochila 0/1, árbol de búsqueda y podas

> El esquema de backtracking explicado en C: árbol de búsqueda, decisiones, podas, y las variantes para obtener todas las soluciones, una solución o la óptima, con la mochila 0/1 y la descomposición en sumandos.

<Card title="Abrir el simulador" icon="flask" href="https://simulab.es/programacion/backtracking">
  Mochila 0/1 y descomposición en sumandos en C: árbol de búsqueda con podas, todas las soluciones, una o la óptima.
</Card>

Muchos problemas consisten en tomar una serie de decisiones: qué objetos meter en una mochila, qué casilla rellenar en un sudoku, dónde colocar cada reina en un tablero. Probar todas las combinaciones es inviable, pero muchas se pueden descartar a medio camino. El **backtracking** (vuelta atrás) explora las decisiones una a una y **retrocede** en cuanto una opción ya no puede llevar a una solución.

## Lo que vas a aprender

* El esquema general de backtracking.
* El árbol de búsqueda y cómo se recorre.
* Qué es una poda y por qué ahorra tanto trabajo.
* Las tres variantes: todas las soluciones, una o la óptima.

## Cómo se usa el simulador

* Elige el problema: **mochila 0/1** o **descomposición** en sumandos.
* Elige la variante: **todas las soluciones**, **una solución** o **la óptima**.
* **Datos**: número de objetos (2 – 5), capacidad y la tabla de pesos y beneficios.
* Avanza con **⏮**, **◀**, **▶ Ejecutar**, **▶** y **⏭**. Se resaltan la línea del **código en C**, el **vector de decisiones** y el **árbol de búsqueda** (nodo actual, podado o solución). Los contadores dan los nodos generados, los podados y las soluciones.

## Fundamentos teóricos

### El esquema

La solución es un vector de decisiones $x[1], x[2], \dots, x[n]$. En cada nivel $k$ se prueban todas las opciones para $x[k]$:

```c theme={null}
void backtracking(int k) {
    for (cada opción v de x[k]) {
        x[k] = v;
        if (es_correcta(k)) {          // ¿puede llevar a una solución?
            if (k == n) tratar(x);     // solución completa
            else backtracking(k + 1);  // siguiente decisión
        }
    }
}
```

### El árbol de búsqueda

Cada nivel es una decisión y cada hoja, una secuencia completa. En la mochila 0/1, cada objeto tiene dos ramas (fuera o dentro): $2^n$ hojas.

### Podas

Si una solución parcial **ya no puede ser correcta**, no se exploran sus descendientes. En la mochila: si el peso ya supera la capacidad, se corta la rama. En la variante óptima también se puede podar si ni metiendo todos los objetos restantes se superaría el mejor beneficio encontrado.

### Las tres variantes

| Variante | Qué cambia |
| - | - |
| Todas las soluciones | Se trata cada hoja válida |
| Una solución | Se corta la búsqueda al encontrar la primera (con una variable `encontrada`) |
| La óptima | Se recorren todas guardando la mejor en `x_mejor` y `v_mejor` |

### Coste

En el peor caso, el tamaño del árbol: **exponencial** ($2^n$ en la mochila). Las podas no cambian el peor caso, pero en la práctica reducen muchísimo el trabajo.

## Ejemplos resueltos

<AccordionGroup>
  <Accordion title="Ejemplo 1 · Mochila 0/1" defaultOpen>
    Capacidad 8. Pesos 3, 4, 2, 5 y beneficios 8, 10, 3, 12.

    Hay $2^4 = 16$ combinaciones. Se podan las que pesan más de 8 (por ejemplo, objetos 1, 2 y 3: peso 9).

    Algunas válidas: (1, 0, 0, 1) pesa 8 y vale 20; (1, 1, 0, 0) pesa 7 y vale 18; (0, 1, 1, 0) pesa 6 y vale 13.

    **Óptima: objetos 1 y 4, beneficio 20.**
  </Accordion>

  <Accordion title="Ejemplo 2 · Cuánto se poda">
    Sin podas, el árbol completo de 4 objetos tiene $1 + 2 + 4 + 8 + 16 = 31$ nodos. Con capacidad 8, todas las ramas que empiezan por meter los objetos 1 y 2 (peso 7) se cortan en cuanto se añade otro objeto.
  </Accordion>
</AccordionGroup>

## Experimenta con el simulador

<Steps>
  <Step title="Podas">
    Con la mochila, baja la capacidad. ¿Aumentan los nodos podados?
  </Step>

  <Step title="Variantes">
    Compara los nodos generados para "todas", "una" y "la óptima".
  </Step>

  <Step title="Descomposición">
    Cambia al problema de descomposición y mira cómo se construyen las soluciones.
  </Step>
</Steps>

## Errores frecuentes

* **No deshacer la decisión** al volver atrás cuando se usan variables acumuladas (como el peso actual).
* **Podar demasiado pronto** y perder soluciones válidas.
* **Confundir backtracking con fuerza bruta**: la diferencia está en las podas.

## Herramientas relacionadas

<CardGroup cols={3}>
  <Card title="Recursión" icon="arrows-rotate" href="/programacion/c/recursion">
    Funciones que se llaman a sí mismas.
  </Card>

  <Card title="Combinatoria" icon="calculator" href="/matematicas/estadistica/combinatoria">
    Cuántas combinaciones hay.
  </Card>

  <Card title="Recorridos de grafos" icon="diagram-project" href="/programacion/algoritmos/grafos">
    DFS, una exploración en profundidad.
  </Card>
</CardGroup>


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.