Qué es un algoritmo de aproximación
Como vimos la última vez, algunos problemas tienen tantos casos que revisar cada uno en busca de la respuesta perfecta llevaría toda una vida. ¿Significa eso rendirse? No necesariamente. Aunque no puedas conseguir la respuesta perfecta, muchas veces puedes conseguir rápido una respuesta «suficientemente buena». Pierdes un poco y ganas mucho tiempo.
Dejar la perfección a un lado
Tenemos un problema difícil. Para encontrar la respuesta perfecta habría que revisar todos los casos, y son muchísimos.
Si llegas hasta el final, seguro que sale la mejor respuesta. Pero ¿cuándo será eso?
Pulsa y cuéntalo tú mismo.
Qué pasa si revisas todo en busca de la respuesta perfecta. (los casos se multiplican y el tiempo explota → no se ve el final)
Los números crecen demasiado rápido. Con solo añadir unos pocos elementos, hay varias veces más cosas que revisar.
Así que esperar hasta el final a la respuesta perfecta no siempre es realista. Pero eso no significa que podamos cruzarnos de brazos.
Una respuesta suficientemente buena, rápido
Aquí va una idea. ¿Y si no tiene que ser la mejor de todas?
En vez de apuntar a la perfección, sacas rápido una «respuesta razonablemente buena», eligiendo con soltura lo bueno que tienes delante, como hacía el método voraz.
Una respuesta aproximada rápida vs la respuesta perfecta. (la aproximada sale en un instante · la diferencia es pequeña)
La respuesta aproximada salió en un abrir y cerrar de ojos, y apenas se diferencia de la perfecta.
Se queda un poco corta, pero sirve. En muchos casos, con esto basta.
Garantizar lo buena que es
Aunque queda una preocupación: ¿podemos fiarnos de una «respuesta razonablemente buena»? ¿Y si es malísima?
Por eso los métodos ingeniosos vienen con una promesa: «esta respuesta no será mucho peor que la mejor».
Garantizado dentro de 1,5 veces el óptimo. (salga la respuesta que salga, queda dentro de esta línea → el peor caso está acotado)
Esto es lo realmente estupendo. Si trazas una línea como «dentro de 1,5 veces el óptimo», por mala que sea la respuesta, no puede cruzarla.
No es perfecta, pero sabemos exactamente cuánto puede quedarse corta. Eso es completamente distinto de una suposición vaga.
Cambiar precisión por tiempo
Al final, es una balanza. Si dedicas más tiempo, la respuesta es más precisa; si ahorras tiempo, la respuesta queda un poco más tosca.
No se puede decir de una vez por todas qué lado es mejor: el rápido si tienes prisa, el preciso si necesitas exactitud.
Usa los botones para añadir o ahorrar tiempo y elegir un punto entre los dos.
Más tiempo, más precisión; menos tiempo, menos precisión. (dónde parar lo elegimos nosotros)
Esta balanza es el corazón de todos los algoritmos: el camino rápido y el preciso, el sencillo y el minucioso.
Cada vez hemos elegido qué ceder y qué ganar. Conocer buenos métodos es saber leer esta balanza.
Hasta dónde hemos llegado
Hemos recorrido un largo camino. Empezamos resolviendo las cosas en orden, y luego ordenamos, buscamos, medimos costos, partimos, conectamos y elegimos.
También vimos que algunos problemas son realmente difíciles, y que aun así existen respuestas suficientemente buenas.
Pulsa para repasar todo el camino de una vez.
Cuatro cosas que nos ha dado esta área, en orden. (buenos métodos · rapidez · estrategia · conocer los límites y llegar a un acuerdo)
No todos los problemas se pueden resolver a la perfección. Pero eso no significa que estemos indefensos.
Con métodos rápidos y estrategias ingeniosas, y sabiendo dónde están los límites para llegar a un acuerdo sensato, se puede conseguir una respuesta útil incluso ante problemas difíciles.
Ese es el poder que nos dan los algoritmos.