Se considera que una solución óptima es la mejor solución posible para un conjunto dado de restricciones. Por lo general, esto significa que hay algún tipo de “puntaje” que se puede asignar a cada solución, y la solución óptima es la que tiene el mejor puntaje.
Aquí hay un ejemplo, supongamos que tenemos un sistema de metro que conecta las siguientes paradas, y queremos pasar de la parada A a la D en la menor cantidad de tiempo, donde el número al borde representa cuántos minutos dura ese viaje.
¿Cuál es la solución óptima?
- ¿Cómo se siente cuando te das cuenta de que no eres realmente bueno en programación y algoritmos?
- ¿Cuál es la diferencia principal entre algoritmo y pseudocódigo?
- ¿Qué estructura de datos usaría para diseñar un programa de planificación de producción?
- ¿Cuáles son los algoritmos hash más comunes además de MD5 y SHA?
- ¿Cuál es el algoritmo más extraño que hayas usado?
Las rutas posibles (que no implican visitar las mismas paradas varias veces en un bucle) de la A a la D son:
- A a B a D, que toma 1 + 4 = 5 minutos
- A a D directamente, que toma 4 minutos
- A a C a D, que toma 2 + 1.5 = 3.5 minutos
Dado que nuestro objetivo era minimizar el tiempo dedicado, la solución óptima sería de A a C a D.
Otros tipos de soluciones óptimas podrían relacionarse con tomar la mejor decisión con información incompleta, por ejemplo:
- Decides comenzar a esquiar como pasatiempo, pero no tienes tus propios esquís. Cada vez que vaya a esquiar tendría que gastar R dólares para alquilar esquís, podría comprar su propio par de esquís por B dólares. Por experiencia anterior, sabe que a veces se cansa de pasatiempos como esquiar y los abandona.
- ¿Cómo debe decidir cuántas veces debe alquilar esquís antes de comprarlos?
- Aquí la solución verdaderamente óptima, dada la información perfecta, sería decir:
- Si voy a esquiar más de piso (B / R) veces, debería comprar esquís de inmediato, de lo contrario siempre alquilaré.
- ¡Pero! No sabes cuántas veces irás a esquiar. ¿Cómo determinaría la cantidad óptima de veces para alquilar antes de comprar? Un enfoque estándar es determinar cualquier estrategia S de alquiler de esquí y comprar el costo total C que esa estrategia gasta, el costo óptimo K de la solución perfecta dada la información total (en este caso, K es menor de B o R * # de viajes de esquí), y encuentre la estrategia que minimiza la proporción de C / K.
- Para este ejemplo hipotético, la solución óptima es alquilar esquís hasta que hayas gastado B dólares en alquileres y luego comprarlos.
Hay muchos, muchos tipos de problemas de optimización, aquí hay una lista que muestra algunas aplicaciones prácticas de problemas de optimización: Ejemplos de problemas de optimización
