# TDA | Practica 1 Ejercicio 16
## Consigna
Tomás quiere viajar de Buenos Aires a Mar del Plata en su flamante Renault 12. Como está preocupado por la autonomía de su vehículo, se tomó el tiempo de anotar las distintas estaciones de servicio que se encuentran en el camino. Modeló el mismo como un segmento de $0$ a $M$, donde Buenos Aires está en el kilómetro $0$, Mar del Plata en el $M$, y las distintas estaciones de servicio están ubicadas en los kilómetros $0 = x_1 \leq x_2 \leq \ldots \leq x_n \leq M$.
Razonablemente, Tomás quiere minimizar la cantidad de paradas para cargar nafta. Él sabe que su auto es capaz de hacer hasta $C$ kilómetros con el tanque lleno, y que al comenzar el viaje este está vacío.
**a)** Proponer un algoritmo *greedy* que indique cuál es la cantidad mínima de paradas para cargar nafta que debe hacer Tomás, y que además devuelva el conjunto de estaciones en las que hay que detenerse. Probar su correctitud.
**b)** Dar una implementación de complejidad temporal $O(n)$ del algoritmo del inciso **a)**.
## Resolución
```python
def rutaEficiente(C, estaciones):
paradasRealizadas = [0] # Inicializamos con la estación de partida.
indiceUltimaParada = 0 # Índice de la última estación en la que se cargó combustible.
for i in range(1, len(estaciones)):
# Si no podemos llegar a la estación actual con el combustible desde la última parada, cargamos en la anterior.
if estaciones[i] - estaciones[indiceUltimaParada] > C:
paradasRealizadas.append(estaciones[i - 1]) # Agregamos la última estación que nos da la nafta.
indiceUltimaParada = i - 1
return len(paradasRealizadas) - 1, paradasRealizadas[1:] # Restamos 1 y omitimos la estación de partida para las paradas.
```
### Demostración
- **Definiciones Iniciales:**
- Sea $S_o$ una secuencia **óptima** de paradas.
- Sea $S_g$ la secuencia de paradas generada por el algoritmo **codicioso**.
- Paradas de $S_g$: $\{S_g[1], S_g[2], \dots, S_g[m]\}$.
- Paradas de $S_o$: $\{S_o[1], S_o[2], \dots, S_o[n]\}$, donde $m$ y $n$ representan el número de paradas en cada secuencia.
- Asumimos que ambas secuencias comparten la primera y última parada, es decir, $S_g[1] = S_o[1]$ y $S_g[m] = S_o[n]$.
- **Suposición:**
- Supongamos que $S_g$ no es óptima, es decir, $m > n$. Esto implica que existe una secuencia óptima $S_o$ con menos paradas que $S_g$.
- **Lema (Inducción en las estaciones óptimas):**
- **Caso Base ($i=1$):** Como $g_1$ era lo más que se podía alcanzar desde el comienzo, $o_1 \geq g_1$, sino nuestro algoritmo codicioso hubiera elegido $o_1$ también.
- **Paso Inductivo ($i = k + 1$):** Supongamos que demostramos que para $1 \leq i \leq k$ vale que $o_i \leq g_i$. Queremos verlo para $i = k + 1$. Dado $g_{k+1}$ lo podemos expresar como la estación anterior más una distancia menor o igual que $C$.
- $o_{k+1} = o_k + D$, con $0 < D \leq C$. $o_k$ está en el caso de la hipótesis inductiva, entonces:
- $o_{k+1} = o_k + D \leq g_k + D$.
- Veamos que entonces $g_{k+1}$ en realidad está adelante de $o_{k+1}$, $o_{k+1} - g_k \leq D$.
- **Conclusión de Inducción:**
- Por lo tanto, $o_{k+1} \leq g_{k+1}$. Esto demuestra que cada estación en $S_o$ no es más lejana que la correspondiente estación en $S_g$, y que por lo tanto $S_g$ es óptima.
- **Consideración de Casos Diferentes:**
1. Si $S_o[k]$ está más lejos que $S_g[k]$, entonces $S_g$ no sería codicioso, lo que contradice la definición del algoritmo.
2. Si $S_o[k]$ está más cerca que $S_g[k]$, entonces la subsecuencia $S_o[k, \dots, n]$ debe tener al menos tantas paradas como $S_g[k, \dots, m]$. Esto se debe a que $S_g$ es óptima en el subproblema de ir desde $S_g[k]$ hasta el final, por el principio de optimalidad. Como resultado, $S_o$ en total no puede tener menos paradas que $S_g$, lo cual contradice nuestra suposición.
- **Conclusión Final:**
- En ambos casos, llegamos a una contradicción. Por lo tanto, nuestra suposición inicial de que $S_g$ no es óptima debe ser falsa. En consecuencia, $S_g$ debe ser una secuencia óptima de paradas. $\square$