Subestructura óptima - Optimal substructure
En informática , se dice que un problema tiene una subestructura óptima si se puede construir una solución óptima a partir de soluciones óptimas de sus subproblemas. Esta propiedad se utiliza para determinar la utilidad de la programación dinámica y los algoritmos codiciosos para un problema.
Por lo general, se usa un algoritmo codicioso para resolver un problema con una subestructura óptima si se puede demostrar por inducción que esto es óptimo en cada paso. De lo contrario, siempre que el problema presente también subproblemas superpuestos , se utiliza la programación dinámica . Si no hay algoritmos codiciosos apropiados y el problema no presenta subproblemas superpuestos, a menudo una búsqueda larga pero sencilla del espacio de la solución es la mejor alternativa.
En la aplicación de la programación dinámica a la optimización matemática , el Principio de Optimidad de Richard Bellman se basa en la idea de que para resolver un problema de optimización dinámica desde un período inicial t hasta un período final T , implícitamente se tienen que resolver subproblemas a partir de fechas posteriores s , donde t <s <T . Este es un ejemplo de subestructura óptima. El Principio de Optimidad se utiliza para derivar la ecuación de Bellman , que muestra cómo el valor del problema a partir de t está relacionado con el valor del problema a partir de s .
Ejemplo
Considere la posibilidad de encontrar un camino más corto para viajar entre dos ciudades en automóvil, como se ilustra en la Figura 1. Es probable que este ejemplo muestre una subestructura óptima. Es decir, si la ruta más corta de Seattle a Los Ángeles pasa por Portland y luego por Sacramento, entonces la ruta más corta de Portland a Los Ángeles también debe pasar por Sacramento. Es decir, el problema de cómo llegar de Portland a Los Ángeles está anidado dentro del problema de cómo llegar de Seattle a Los Ángeles. (Las líneas onduladas del gráfico representan soluciones a los subproblemas).
Como ejemplo de un problema que probablemente no exhibirá una subestructura óptima, considere el problema de encontrar el boleto de avión más barato de Buenos Aires a Moscú. Incluso si ese boleto incluye paradas en Miami y luego en Londres, no podemos concluir que el boleto más barato de Miami a Moscú se detenga en Londres, porque el precio al que una aerolínea vende un viaje de varios vuelos generalmente no es la suma de los precios. en el que vendería los vuelos individuales del viaje.
Definición
Se puede dar una definición un poco más formal de subestructura óptima. Sea un "problema" una colección de "alternativas", y que cada alternativa tenga un costo asociado, c (a) . La tarea consiste en encontrar un conjunto de alternativas que minimice c (a) . Suponga que las alternativas se pueden dividir en subconjuntos, es decir, cada alternativa pertenece a un solo subconjunto. Suponga que cada subconjunto tiene su propia función de costo. Se pueden encontrar los mínimos de cada una de estas funciones de costo, al igual que los mínimos de la función de costo global, restringidos a los mismos subconjuntos . Si estos mínimos coinciden para cada subconjunto, entonces es casi obvio que se puede elegir un mínimo global no del conjunto completo de alternativas, sino sólo del conjunto que consiste en los mínimos de las funciones de costo local más pequeñas que hemos definido. Si minimizar las funciones locales es un problema de "orden inferior", y (específicamente) si, después de un número finito de estas reducciones, el problema se vuelve trivial, entonces el problema tiene una subestructura óptima.
Problemas con la subestructura óptima
- Problema de subsecuencia común más largo
- Subsecuencia creciente más larga
- Subcadena palindrómica más larga
- Ruta más corta para todos los pares
- Cualquier problema que pueda solucionarse mediante programación dinámica .
Problemas sin una subestructura óptima
- Problema del camino más largo
- Exponenciación de la cadena de suma
- Tarifa de aerolínea de menor costo. (Al utilizar la búsqueda de vuelos en línea, con frecuencia encontraremos que el vuelo más barato del aeropuerto A al aeropuerto B implica una sola conexión a través del aeropuerto C, pero el vuelo más barato del aeropuerto A al aeropuerto C implica una conexión a través de algún otro aeropuerto D.) Sin embargo, si el problema toma el número máximo de escalas como parámetro, entonces el problema tiene una subestructura óptima: el vuelo más barato de A a B que implica una sola conexión es el vuelo directo; o un vuelo de A a algún destino C, más el vuelo directo óptimo de C a B.
Ver también
Referencias
- ↑ a b Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009). Introducción a los algoritmos (3ª ed.). MIT Press . ISBN 978-0-262-03384-8 .