# TDA | Teorica backtracking y programación dinamica
- Problemas bien resueltos y de optimización
- Los algoritmos polinomiales se consideran satisfactorios $\ O(n^k)$ y los supra-polinomiales se consideran no-satisfactorios
- Un problema de optimización consiste en encontrar la mejor solución dentro de un conjunto:
$$
z^* = \max_{x \in S} f(x) \quad \text{o bien} \quad z^* = \min_{x \in S} f(x)
$$
- La función $f:S ⇒ R$ se denomina **función objetivo** del problema.
- El conjunto S es la región factible y los elementos $x \in S$ se llaman soluciones factibles.
- Algoritmos de fuerza bruta y backtracking
- optimización combinatoria consiste en generar todas las soluciones factibles y quedarse con la mejor
- Se los suele llamar también algoritmos de busqueda exhaustiva o generate n test
- tecnica trivial pero muy general\
- Facil de implementar y es un algoritmo exacto, si hay solución siempre la encuentra.
- Complejidad exponencial ☠️
- Problema de la mochila buen caso de estudio
$$
\begin{aligned}&\text{Mochila}(S \subseteq \{1, \ldots , n\}, k : \mathbb{Z}) \\&\text{if } k = n + 1 \text{ then} \\&\quad \text{if peso}(S) \leq C \land \text{beneficio}(S) > \text{beneficio}(B) \text{ then} \\&\quad \quad B \leftarrow S \\&\quad \text{end if} \\&\text{else if peso}(S) \leq C \land \text{benef}(S) + \sum_{i=k+1}^{n} b_i > \text{benef}(B) \\&\text{then} \\&\quad \text{Mochila}(S \cup \{k\}, k + 1); \\&\quad \text{Mochila}(S, k + 1); \\&\text{end if}\end{aligned}
$$
## Concepto de backtracking
- Recorrer sistem´aticamente todas las posibles configuraciones
del espacio de soluciones de un problema computacional,
eliminando las configuraciones parciales que no puedan
completarse a una soluci´on.
$$
\begin{aligned}&\text{algoritmo BT}(a,k) \\&\text{si } a \text{ es solución entonces} \\&\quad \text{sol} \leftarrow a \\&\quad \text{encontró} \leftarrow \text{verdadero} \\&\text{sino} \\&\quad \text{para cada } a' \in \text{Sucesores}(a, k) \\&\quad \quad \text{BT}(a', k + 1) \\&\quad \quad \text{si encontró entonces} \\&\quad \quad \quad \text{retornar} \\&\quad \quad \text{fin si} \\&\quad \text{fin para} \\&\text{fin si} \\&\text{retornar}\end{aligned}
$$
## Programacion dinamica
- Se divide el problema en subproblemas que se resuelven recursivamente como d&c
- Ej: numero combinatorio si n>=0 y k acotado entre 0 y n definimos el numero combinatorio como vimos en algebra1.
- No es buena idea computar esta definicion
```
Algoritmo Combinatorio(n, k)
Entrada: Dos enteros n y k
Salida: El número de combinaciones de n elementos tomados de k en k
Si k == 0 o k == n entonces
Retornar 1
Sino
a = Combinatorio(n-1, k-1)
b = Combinatorio(n-1, k)
Retornar a + b
Fin Si
Fin Algoritmo
```
concepto de superposicion de estados
- podemos decir que se realizan muchas veces llamadas a la funcion recursiva con los mismos parametros
#### DP tiene dos enfoques fijos
- Enfoque top down
- **Se implementa recursivamente**, pero se guarda el resultado de cada llamada recursiva en una estructura de datos **(memorización)**. Sí una llamada recursiva se repite, se toma el resultado de esta estructura.
- Enfoque bottom-up
- resolver primero los subproblemas mas peques y guardamos (habitualmente en una tabla) todos los resultados (es iterativo).
#### Ejemplo: Cálculo de coeficientes binomiales (imagen)
- Por definicion
- complejidad $O(n)$ lineal ojo tamanio de entrada logaritmica $O(log \ n)$
- inconvenientes: inestabilidad numerica y/o manejo de enteros muy grandes
- funcion recursiva:
- Complejidad $\Omega({n \choose k})$
- programacion dinamica (botton up)
- Complejidad $O(nk)$
- espacio $\Theta(k)$ : solo necesitamos almacenar ala fila anterior de la que estamos calculando
- se podria mejorar un poco sin cambiarl a complejidad aprovechando que ${n \choose k}$ = ${k \choose n-k}$.
#### Problema del cambio
- Supongamos que queremos dar el vuelto a un cliente usando el mınimo numero de monedas posibles, utilizando monedas de 1, 5, 10 y 25 centavos. Por ejemplo, si el monto es $0,69, deberemos entregar 8 monedas: 2 monedas de 25 centavos una de 10 centavos, una de 5 centavos y cuatro de un centavo.
- **Problema**: dadas las denominaciones $a_1 \ , \ ...,a_k$ $\in$ $\mathbb{Z}+$ de monedas (con $a_i$>$a_{i+1}$ para $i=1,...,k-1$) tales que:
$$
t = \sum_{i=1}^{k}x_i \ a_i
$$
- minimizando $x_1 + ... + x_k$.
- f(s) cantidad minima de monedas para entregar S centavos para $s=0,...,t$
función recursiva:
$f(s) =$ \begin{cases}
0 & \text{si } s = 0\\
\min_{i:a_i \leq s} 1 + f(s - a_i) & \text{si } a_k \leq s \\
\infty & \text{ninguno de los casos anteriores}
\end{cases}
### Teorema:
- f(s) es el valor óptimodel problema del cambo para entregar $s$ centavos. Caso contrario no tiene solución.
##### ¿Como conviene implementar esta recursión?
##### Datos de entrada:
### Problema de la mochila
- Capacidad de $C \in \mathbb{Z}_+$ de la mochila (peso maximo)
- Cantidad $n \in \mathbb{Z}_+$ de Objetos.
- Peso $p_i \in \mathbb{Z}_{>0}$ del objeto $i$, para $i=1,..,n$.
- Beneficio $b_i \in \mathbb{Z}_+$ del objeto $i$ para $i=1,..,n$.
***Problema***: Determinar qué objetos debemos incluir en la mochila sin excedernos del peso máximo C, de modo tal que ****maximizar**** el beneficio total entre los objetos seleccionados.
#### problema de la mochila con programacion dinamica
- Definimos $m(k,D)$ = valor optimo del problema con los primeros k objetos y una mochila de capacidad $D$.
- Podemos representar los valores de este parametro en una tabla de dos dimensiones:
- 
- sea $S^*$ incluido {$1,...,k$}
- una solucion optima para la instancia $(k,D)$
$$
m(k, D) =
\begin{cases}
0 & \text{si } k = 0\\
0 & \text{si } D = 0\\
m(k - 1, D) & \text{si } k \notin S^*\\
b_k + m(k - 1, D - p_k) & \text{si } k \in S^*
\end{cases}
$$
definimos entonces...
`DIAPO PENDIENTE`
#### problema de la subsecuencia comun mas larga
- Dada una secuencia A, una subsecuencia se obtiene eliminando cero o mas simbolos de A.
- Por ejemplo, `[4,7,2,3]` y `[7,5]` son subsecuencias de `A=[4,7,8,2,5,3]` pero `[2,7]` no lo es
- **problema**: encontrar la subsecuencia comun mas larga **(scml)** de dos secuencias dadas.
- ejemplo: si `A=[9,5,2,8,7,3,1,6,4]` y `B=[2,9,3,5,87,4,1,6]` y la scml es `[9,5,7,7,1]`
- Dadas las secuencias A=[$a_1,...,a_r$] y B=$[b_1,...,b_r]$
- `diapos PENDIENTE`