ESQUEMAS ALGORÍTMICOS
This page intentionally left blank
JUAN RAMÓN RICO
ESQUEMAS ALGORÍTMICOS
PUBLICACIONES DE LA UNIVERSIDAD DE ALICANTE
Publicaciones de la Universidad de Alicante Campus de San Vicente s/n 03690 San Vicente del Raspeig
[email protected] http://publicaciones.ua.es Teléfono: 965903480 Fax: 965909445
© Juan Ramón Rico, 2003 © de la presente edición: Universidad de Alicante
I.S.B.N.: 84-7908-757-9 Depósito Legal: MU-1778-2003
Diseño de portada: candela + alenda Impresión: Compobell, S.L. C/. Palma de Mallorca, 4 - bajo 30009 Murcia
Reservados todos los derechos. No se permite reproducir, almacenar en sistemas de recuperación de la información ni transmitir alguna parte de esta publicación, cualquiera que sea el medio empleado —electrónico, mecánico, fotocopia, grabación, etc.—, sin el permiso previo de los titulares de la propiedad intelectual.
Contenido 1. Preliminares /. / Introducción 1.2 ;Oué es un algoritmo? 1.3 ¿Oué es la algoritmia? 1.4 Notación para los programas 1.3 Notación matemática. 2. Programación dinámica 2. / Introducción 2.2 Esquema recursivo 2.2A Principio de inducción general 2.2.2 Principio de optimalidad 2.3 Esquema iterativo 2.3.1 Estructura indexada de datos 2.3.2 Esquema Iterativo 2.4 Problemas resueltos 2.4.1 Hallar e! camino mínimo en un grafo multietapa 2.4.2 Mínima distancia de edición entre dos cadenas 2.4.3 Secuencia mínima para calcular el producto entre matrices 2.5 Ejercicios 2.5.1 Inversiones 2.5.2 Transporte de mármoi 2.5.3 Conexiones en Internet 2.5.4 Evacuación de una isla 2.5.5 Dónde llenar el depósito de gasolina 2.5.6 Salir del laberinto 2.6 Soluciones 3
Ramificación y poda 3. l Introducción 3.2 Esquema básico de resolución de problemas 3.3 Refinamientos sobre el esquema básico 3.3.1 Primer refinamiento 3.3.2 Segundo refinamiento 3.3.3 Solución subóptima 3.4 Teoría de juegos 3.5 Problemas resueltos 3.5.1 El problema de la mochila discreto 0/1 3.5.2 El Viajante de Comercio 3.6 Ejercicios 3.6.1 Dónde llenar el depósito de gasolina 3.6.2 Reservas de laboratorio 3.6.3 Puzzle 3.6.4 Construcción de edificios 3.6.5 Cena de empresa 3.6.6 Viaie en autobuses 3.7 Soluciones
11
13 14 14 16 16
21
21 33
41
44 AA 44
47
49 49 53 54 61 66 70 70 71 71 72 72 73
93 93 99 105 106 109 112 113 117 118 123 729 130 131 131 132 132 133 735
Referencias
149
índice analítico
151 7
This page intentionally left blank
Prefacio
En este libro se describe la materia que sustenta la asignatura de Esquemas Algorítmicos que se imparte en el tercer curso de Ingeniería en Informática como troncal, en Ingeniería Técnica en Informática de Gestión y de Sistemas como optativa, en la Escuela Politécnica Superior.
El autor, profesor que coordina la asignatura en el momento de redactar este libro, pretende dotar al alumno de una guía básica que le permita alcanzar los conocimientos necesarios para ser capaz de evaluar algoritmos de optimización en cuanto a su eficiencia.
El libro comienza con el capítulo 1 que contiene conceptos preliminares. En él se repasa las nociones básicas como la de algoritmo, algoritmia y notación matemática que se utilizará a io largo de este libro. El capítulo 2 está dedicado a la programación dinámica. Primero se hace una introducción para que el alumno tenga una idea intuitiva de este esquema de programación, para posteriormente profundizar en su descripción y en su eficiencia. Como apartado final de este capítulo se presenta problemas resueltos y comentados, así como, ejercicios complementarios con sus soluciones correspondientes. Él capítulo 3, mantiene la misma estructura que el capítulo anterior se explica el esquema de programación de ramificación y poda. Luego, se comienza con una introducción para intuir el comportamiento del algoritmo. Se profundiza más en la descripción y desarrollo de este esquema en los apartados del esquema básico y refinamientos sobre el esquema básico. Para concluir este capítulo 3, se presentan problemas resueltos y comentados, así como, ejercicios complementarios con las soluciones correspondientes, Para finalizar, únicamente decir que esta obra no pretende ser una versión definitiva de la asignatura si no que es una primera versión desarrollada a partir de los apuntes de esta asignatura y que pretende completarlos. Por último, agradecer a los alumnos que han cursado la asignatura en años anteriores sus preguntas y comentarios que han contribuido a la realización de esta obra. Gracias a todos por vuestra contribución y vuestro interés.
Juan Ramón Rico
This page intentionally left blank
1. Preliminares
Planteamiento: La forma que tenemos de resolver problemas es mediante algoritmos. Estos consisten en una serie de pasos ordenados de forma que son capaces de resolver un problema. Se debe comprender las fases que constituyen el ciclo de desarrollo de un algoritmo porque son fundamentales para entender su utilidad y aplicación en la práctica. Un algoritmo se idea, se expresa, se valida, se analiza y se testea, cada una de estas fases es necesaria para que tengamos un algoritmo consistente y eficaz. Todos estos conceptos fueron vistos en la asignatura Programación Metódica de 2Q, en esta unidad pretendemos repasarlos. Además, presentaremos las matemáticas que se utilizarán para resolver problemas en apartados posteriores.
Objetivos: • Que el alumno conozca las fases de desarrollo de un algoritmo. • Que el alumno entienda la utilidad de las fases de desarrollo de un algoritmo.
11
This page intentionally left blank
Preliminares
1.1 Introducción Este libro se establece como un complemento de la asignatura del mismo nombre, Esquemas Algorítmicos. Pretende ser una guía para que el alumno pueda aprender y comprobar su nivel de conocimientos. A lo largo de este libro se presentarán dos esquemas eficientes para disminuir la complejidad temporal de algunos problemas. Los esquemas son características comunes a un tipo de problema dado, por lo que si examinamos dicho esquema seremos capaces de resolver cualquier problema que cumpla con las mencionadas características comunes. Los esquemas de programación como divide y vencerás, vuelta atrás (backtracking), algoritmos voraces (greedy), así como el cálculo de complejidades y verificación de programas son conceptos que se han visto en la asignatura de Programación Metódica. Este libro tomará como base alguno de estos conceptos para construir nuevos esquemas, calcular sus complejidades y verificarlos. En la Figura 1 y en la Figura 2 se puede observar las principales funciones de complejidad temporal. Podemos distinguir entre las complejidades polinómicas y exponenciales: • •
Polinómicas: Las variables están en la base y tienen exponente constante. Exponenciales: Existe algún término con exponente variable.
Figura I . Complejidades polinómicas más representativas.
13
Preliminares
Figura 2. Principales complejidades exponenciales.
1.2 ¿Qué es un algoritmo? Un algoritmo, nombre que proviene de! matemático persa del siglo IX Khowárizmí, es un conjunto de reglas para efectuar algún cálculo, bien sea a mano o, más frecuentemente, en una máquina. En este libro nos preocupan fundamentalmente los algoritmos que van a ser utilizados en el ordenador. Sin embargo, también podrían incluirse otros métodos sistemáticos para calcular un resultado; los métodos que aprendimos en la escuela para sumar, multiplicar y dividir números, son también algoritmos. Cuando se utiliza un algoritmo para calcular la respuesta de un problema concreto, aplicando las reglas correctamente, la respuesta será correcta. Pero cuando necesitamos que el tiempo de respuesta sea lo menor posible, tenemos que aplicar un algoritmo más eficiente. Si necesitamos una respuesta exacta habrá que estudiar la complejidad temporal del algoritmo actual y encontrar otro algoritmo más eficiente que la mejore. Si queremos una respuesta aproximada, podemos aplicar algoritmos heurísticos (no es el objetivo de este libro).
1.3 ¿Qué es la algoritmia? Se puede definir la algoritmia como la ciencia que estudia los algoritmos. Cuando nos disponemos a resolver un problema, es posible que haya toda una gama de algoritmos disponibles. En este caso, es importante decidir cuál de ellos hay que utilizar. Dependiendo de nuestras prioridades y de los límites del equipo que esté disponible para nosotros, quizá necesitemos seleccionar el algoritmo que requiera menos tiempo, o el que utilice menos espacio, o el que sea más fácil de programar y así sucesivamente. La respuesta puede depender de muchos factores, tales como los números implicados, la forma en que se presenta el problema, o la velocidad y capacidad de almacenamiento del equipo de computación disponible. La algoritmia es la ciencia que nos permite evaluar el efecto de estos diferentes factores externos sobre los algoritmos disponibles, de tal modo que sea posible seleccionar el que más se ajuste a nuestras circunstancias particulares; también es la ciencia que nos indica la forma de diseñar un nuevo algoritmo para una tarea concreta.
14
Preliminares
Podemos distinguir 5 áreas de trabajo fundamentales en algoritmia:
Cómo se idean algoritmos. Esta parte es más bien un arte depende de los conocimientos de la persona o equipo tenga para solucionar el problema. No se puede automatizar. Se suele estudiar varias técnicas que puedan dar buenos resultados y elegir la más conveniente. Nos basaremos en los esquemas estudiados en la asignatura de Programación Metódica (divide y vencerás; vuelta atrás), y desarrollaremos otros como los de programación dinámica y ramificación y poda.
Cómo se expresan los algoritmos. Existen tres paradigmas ampliamente utilizados: imperativo, funcional y lógico. El primero, está basado en órdenes, es el que vamos a utilizar en este libro y que se puede implementar en lenguajes imperativos como C, Pascal, Modula, etc. El paradigma funcional y el lógico se basan en el procesamiento de listas y en la demostración de cláusulas, respectivamente. Un ejemplo de lenguaje de programación funcional es LISP y de programación lógica es Prolog. Los paradigmas anteriores pueden complementarse con la Programación Orientada a Objetos (POO) que es una evolución de! tratamiento tradicional entre los datos y las funciones o procedimientos que los manipulan. Se trabaja con entidades independientes llamadas clases. Éstas tienen estados internos y métodos asociados para que estos objetos cambien su estado o se relacionen con otros. La POO tiene como característica la encapsulación, polimorfismo y la abstracción. Existen clases simples y complejas, éstas últimas pueden generarse mediante herencia o agregación.
Cómo se validan algoritmos. Una vez que se ha ideado un algoritmo hay que demostrar que el algoritmo siempre funcionará correctamente. Es decir, el algoritmo tiene que ser correcto y responder a los parámetros de entrada con la respuesta adecuada. En una segunda fase se verifica el programa. Cuando tenemos el programa en uno de los paradigmas anteriores hay que demostrar que el diseño de nuestro programa nos dará el resultado correcto.
Análisis de los algoritmos. Cuando los algoritmos los tenemos diseñados y sabemos que su funcionamiento es correcto debemos calcular la complejidad espacial y temporal. Con lo que tendremos la rapidez y los recursos que consumirá nuestro algoritmo para luego poder compararlo objetivamente con otros algoritmos existentes.
15
Preliminares
Cómo se testean algoritmos. Cuando queremos detenernos en detalles de nuestro algoritmo una vez programado podemos utilizar: • •
Depurador: Orientado a la depuración de errores con ejecuciones paso a paso, punto de parada y visualización de valores internos del programa. Perfilador1: Orientado ai análisis de tiempos para mejorar la eficiencia. Evaluación de tiempos de funciones o procedimientos y la totalización cuando finaliza el programa. Con ello podemos saber realmente que funciones debemos optimizar para que el rendimiento de nuestro programa mejore temporalmente.
1.4 Notación para los programas Es importante decidir la forma en que vamos a describir nuestros algoritmos. Si intentamos explicarlos en lenguaje natural, descubriremos rápidamente que estos lenguajes no están en absoluto adaptados para este tipo de cosas. Para evitar la confusión, en el futuro especificaremos nuestros algoritmos dando el correspondiente programa. Suponemos que el lector está familiarizado con lenguajes de programación estructurados. Sin embargo, no nos limitaremos estrictamente a ningún lenguaje de programación concreto: de esta manera, los objetivos de un algoritmo no resultarán oscurecidos por detalles de programación relativamente poco importantes. Hay algunos aspectos de nuestra notación para los programas que merecen especial atención. Utilizaremos frases en español en nuestros programas siempre que esto produzca sencillez y claridad. De manera similar, utilizaremos el lenguaje matemático, tal como el del álgebra y de la teoría de conjuntos, siempre que sea necesario.
1.5 Notación matemática Esta sección revisa la notación matemática que utilizaremos a lo largo de libro. Es una revisión rápida, por lo que suponemos que el lector está familiarizado con la mayor parte de ella. Sin embargo, recomendamos leerla porque presentamos la mayoría de los símbolos que se van a utilizar.
Cálculo booleano Existen dos valores Verdadero y Falso. Una variable booleana solamente puede tomar uno de estos dos valores. Si p es una variable booleana, escribimos p es Verdadero, o bien simplemente p. En la Tabla 1 se puede ver un resumen de las principales operaciones entre los valores booleanos.
p
Variables
Falso Falso Verdadero Verdadero
Q Falso Verdadero Falso Verdadero
conjuncton
Disyuncion
P-Q Falso Falso
P-Q Falso Verdadero Verdadero Verdadero
Falso Verdadero
Negacton
Implicaton
Verdadero Verdadero Falso Falso
P=q p-q Verdadero Verdadero Falso Verdadero
Tabla I . Operaciones básicas booleanas
1
Perfilador está traducido de la palabra inglesa proíiling.
16
p
Preliminares
Teoría de conjuntos Aun cuando revisemos aquí los principales símbolos que se utilizan en la teoría de conjuntos, suponemos que el lector ya está familiarizado con la noción de conjunto. Por lo tanto en lo que sigue no se proporciona una definición formal. A todos los efectos prácticos, resulta suficiente pensar que un conjunto es una colección no ordenada de elementos distintos. Un conjunto se dice finito si contiene un número determinado de elementos; en caso contrario el conjunto es infinito. Si X es un conjunto finito, X , es la cardinalidad (n- de elementos).El conjunto vacío,0, tiene cardinalidad 0. La forma más sencilla de representar un conjunto es entre llaves. Por ejemplo, {2,3,5,7} que es el conjunto de números primos de una sola cifra. Las partes de un conjunto se define como todos los subconjuntos que se pueden forman con los elementos de ese conjunto sin repetirse y de tamaño O hasta el mismo tamaño del conjunto. Por ejemplo 7:'({a,b,c})-(0,{a},{b},{c}1{a,b},{a,c},{b,c},{a,b,c}) Normalmente se utilizan letras minúsculas para elementos {.\,y,;} y mayúsculas para los conjuntos {X,Y,7}. También destacar que las letras iniciales del abecedario suelen representar elementos constantes {a=1,b=3,c=7} y las letras finales representan variables (Vxe Y,B\e /F). También podemos utilizar cuantificadores, los símbolos V y 3 se leen "para todo" y "existe" respectivamente. Un resumen de las operaciones que podemos realizar entre conjuntos y sus elementos lo tenemos reflejado en la Tabla 2. Simbolo
Ejemplo
Explicacion j Un elemento pertenece o no a un conjunt Resto de la división entera El conjunto de los números pares | X está inc'uido en Y, o puede llegar a ser el mismo en el segundo cas j Unión de qtos. Elementos que pertenecen a X o a Y i intersección de cjtos. Elmentos que pertenece a X y a Y Diferencia entre X e Y. Elementos de X que no pertenecen a Y. | Producto cartesiano. Combinación de tupias de X con Y. (x,y) e Xx Tabla 2. Operaciones básicas realizadas sobre conjuntos y elementos.
Enteros, reales e intervalos Denotaremos el conjunto de los números enteros por Z-{...,-2,-1,0,1,2,...} y el de los naturales por .'Y={0,1,2,...}, y el de los naturales positivos por ^Th={1,2,3,....}. De igual forma el conjunto de los números reales se representa por 7!. Un intervalo es un conjunto de números reales que están comprendidos entre dos límites. Sean a y b dos números reales tales que a
Expresion
Tabla 3. Tipos de intervalos.
17
Preliminares
Funciones y relaciones Sean X e Y dos conjuntos. Todo subconjunto A de su producto cartesiano XxX es una relación. Cuando xeX e ye Y, decimos que x está relacionado con y según A, lo cual se denota xAy, si y sólo si ix,y)eA. Por ejemplo, uno puede pensar en la relación "<" con respecto a los números enteros como el conjunto de los pares de enteros tales que el primer componente del par es menor o igual que el segundo. Considérese cualquier relación/entre X e Y. La relación se llama fundón si, para cada xeX, existe sólo un v perteneciente a Y tal que el par (x,y)ef. Esto se denota con la expresión f:X->Y, lo que se lee "fes una función de X en Y". El conjunto X se llama dominio y el conjunto Y se llama imagen. Podemos definir distintos tipos de funciones según la propiedades que cumplan sus elementos (Tabla 4). Función
Expresión
Inyectiva
Suprayectiva Biyectiva
¡ Inyectiva y Suprayectiva
Tabla 4. Tipos de (unciones
y su expresión asociada.
Sea P un predicado sobre X y lo definimos como P:X-*{verdadero, falsa}. También diremos que P es una propiedad de X. Por ejemplo, la imparidad es una propiedad de los enteros, que es verdadera para los enteros impares y falsa para los pares. Por ejemplo si tenemos P:¡verdadero, falso/'1->f verdadero, falsoj mediante P(p,q.r)=(pAq) v (-,q/\r) en Cuyo caso P(verdadero,falxr>, verdadero)- verdadero. Considérese un conjunto arbitrario X y una propiedad P sobre X. Escribiremos (VxeX)[P(x)¡ para indicar que todos los elementos x de X tienen la misma propiedad. De manera similar, (3xeX)fP(x)] significa que existe al menos un elemento de x en X que tiene la propiedad P. Finalmente, escribiremos (3!xeX)[P(x)¡ para expresar que existe un solo elemento que cumple la propiedad P(x). Si X es el conjunto vacío, (VxeX)fP(x)] siempre es verdadero.
Sumas y productos Considérese una función /• T-> 9? y un entero n>0. La suma de los valores tomados por/sobre los n primeros números positivos, se denota mediante
que se lee "la suma de \osf(i) cuando / va desde / hasta n". De forma similar, tenemos los productorios, cuyos valores se acumulan utilizando la operación producto y se denotan mediante
18
Preliminares
En algunas ocasiones resulta útil considerar sumas condicionales. Si P es una propiedad de los enteros, denota la suma de/(7) para todos los enteros / tal que sea válido P(i). O incluso utilizar una notación mixta.
De igual forma se puede definir los productorios como
Bibliografía: [HS.78]
Capítulo 1.
[BB,97j
Preliminares (Capítulo 1).
19
This page intentionally left blank
2. Programación dinámica 2.1 Introducción
Planteamiento: Cuando tenemos que resolver un problema de optimización (obtener el mejor resultado cumpliendo una serie de condiciones) es interesante enfocarlo desde diferentes perspectivas, una de ellas es la programación dinámica. Si podemos aplicar esta técnica, podría suponer una mejora en el coste temporal del algoritmo que resuelve nuestro problema. Por ello es una opción que siempre debemos tener presente. Recordamos que los algoritmos de optimización tienen una complejidad temporal y pretendemos con esta técnica mejorar dicha complejidad.
Objetivos: Que el alumno conozca los fundamentos de la programación dinámica. Que el alumno comprenda la mejora de un algoritmo cuando se cambia su resolución de recursiva a iterativa2.
2
Cuando hablamos de paso, de un algoritmo de recursivo a iterativo, nos referimos a una transformación de forma que aprovechamos resultados anteriores y nos supone una mejora en la complejidad temporal.
21
Programación dinámica
2.1 Introducción
En la estrategia divide y vencerás consiste en dividir un problema en subproblemas, éstos a su vez se pueden volver a dividir, así sucesivamente hasta llegar a problemas básicos que se pueden resolver directamente. Una vez resueltos los subproblemas se combinan sus soluciones para resolver los problemas superiores. Frecuentemente sucede que la división más natural dictada por la estructura del problema conduce a un gran número de subproblemas idénticos. Si se resuelve cada subproblema independientemente sin tener en cuenta las posibles repeticiones, el resultado es un algoritmo tremendamente ineficiente. Por otro lado, si se resuelve cada subproblema distinto una sola vez y se conserva el resultado, el algoritmo obtenido es mucho más eficiente. La idea principal de la programación dinámica (PD) es simple: no calcular dos veces lo mismo y utilizar un almacén que se irá rellenando a medida que se resuelven subproblemas. La programación dinámica es un método ascendente. Se resuelven primero los subproblemas menores. Combinando sus resultados se obtienen las soluciones de subproblemas mayores hasta llegar al problema original. En cambio, divide y vencerás es una técnica descendente: se comienza por el ejemplar original que se subdivide en subproblemas cada vez más pequeños a medida que progresa el algoritmo. La estrategia de divide y vencerás es un método de diseño de algoritmos que puede considerarse como un caso especial de la programación dinámica.
EJEMPLO 2.1.1
Queremos calcular números combinatorios, para ello vamos a utilizar la siguiente fórmula recursiva:
Si se calcula el número combinatorio directamente con la fórmula anterior se obtiene la función:
función entonces devuelve 1 sino
fin si
devuelve
fin función Lo que sucede que muchos valores de C(iJ) con /<« y j
Se generará una pequeña traza para ilustrar gráficamente las repeticiones en el esquema recursivo (Figura 3):
22
2.1 Introducción
Programación dinámica
Figura 3. Tra/.a do C(5.2) con el algoritmo recursivo.
Se puede resolver de otro modo. Se almacena en una matriz C(i,j) según filas y columnas hasta llegar a C(n,k) que es el problema original (en realidad es el triángulo de Pascal). Un ejemplo lo tenemos en la Tabla 5.
T.ibla 5. Traza de C(5.2) con el algoritmo iterativo.
En realidad no es necesario guardar memoria para una matriz nxk, bastaría con mantener 2 vectores de tamaño k. En la Tabla 6 se ve las complejidades y las operaciones que realizarían ambos algoritmos, recursivo e iterativo. Si utilizáramos ordenador de 106 operaciones por segundo los tiempos que se obtendrían están presentados entre paréntesis. Con ello se ve la diferencia entre el tiempo de respuesta aplicando programación dinámica al problema de los números combinatorios.
N
K
50 60 70
25 30 50
Recursivo
n k
(operaciones)
l'3-IO'4(4años) T 2 - l O ' 7 (3.750 años) I ' 6 - 1 0 ' 7 (5.133 años)
Iterativo n.k (operaciones) 1.250(1 mseg) 1.800 (2 mseg) 3.5QQ (3 mseg)
Tabla 6. Comparativa ¡Je tiempos entre el algoritmo recursivo e iterativo para números combinatorios.
23
Programación dinámica
2.1 Introducción
Podemos observar en las figuras 4 y 5 como el crecimiento en el número de operaciones del algoritmo recursivo es mucho mayor que en el iterativo. Estas gráficas están realizadas respecto del mismo número de elementos para las variables n y k. pata
Figura 4. Relución de número opeíaciones en el algoritmo recursivo respecto de '/i' y 'k'.
Figura 5. Relación de número operaciones en el algoritmo iterativo respecto de '/i' y 'k'.
24
2.1 Introducción
Programación dinámica
EJEMPLO 2.1.2. Vamos a resolver el problema de la Mochila (discreto 0/1): Un explorador se encuentra un tesoro, en el que hay diversas piezas con distintos valores y pesos (conocidos) únicamente tiene una mochila, con la que puede transportar un peso máximo M (entero). El problema que tenemos que resolver es ¿qué piezas debería introducir el explorador en la mochila para obtener el mayor beneficio posible? En este ejemplo se va a enunciar de una manera más formal: Sea A el conjunto de objetos encontrados, donde a¡ son los distintos objetos pertenecientes al conjunto A={(i¡, «2 ««}• Sea peso: A Sea valor: A
peso(3i) es el peso del objeto a, valorfa) es el valor del objeto a,
Debemos encontrar un subconjunto ScA tal que maximice el siguiente sumatorio...
teniendo en cuenta !a restricción
Este problema se podría resolver probando con todos los posibles subconjuntos de A y, viendo cual sería el que maximiza el valor del subconjunto que cumple la restricción. El conjunto .4 tiene 2 i A ' subconjuntos distintos. Con lo que la complejidad del algoritmo será exponencial, O(2* A '). Se aplicará el esquema de divide y vencerás. Para ello se comenzará considerando el elemento a,,. Existen dos posibilidades, que el elemento se introduzca o no en la mochila. SÍ pertenece el elemento «„ a la solución. Entonces el resto de elementos cumplirán
sujeto a
25
2,1 Introducción
Programación dinámica
•
NO pertenece el elemento «„ a la solución. Entonces el resto de elementos cumplirán
sujeto a
Expresaremos la solución al problema de una forma recursiva (esquema recursivo). Para ello representamos nuestro problema como una tupia P=(A,M) donde A es el conjunto de piezas y M es el peso máximo de la mochila. Lo más sencillo es establecer un algoritmo de fuerza bruta que recorra todas las posibilidades y nos responda con la mejor solución.
Elaborando un diseño divide y vencerás para resolver este problema se podrían generar dos llamadas con sus operaciones correspondientes:
El esquema recursivo completo de divide y vencerás quedaría como sigue:
El valor de -<*> sólo se emite cuando el problema está fuera de ámbito, es decir, se produce un error porque se ha sobrepasado el peso que se puede transportar en la mochila. Como nuestro objetivo es maximizar el valor global, la solución con -°° nunca la escogerá, a no ser que el problema no tenga solución.
Traza de Esquema de la Mochila
26
2.1 Introducción
Programación dinámica
Figurad. Subprohlcnuis generados con la llamada Mochila! !a¡.a;.a;).6)
Ya estamos en condiciones de hallar la complejidad del algoritmo recursivo anterior representado en la Figura 6. Sea m el número de elementos del tesoro que tenemos que examinar. Y sea c,, c2 constantes correspondientes al número de operaciones.
Tenemos un problema de coste exponencial. La solución de programación dinámica consiste en observar que se puede estar resolviendo el mismo problema varias veces.
EJEMPLO 2.1.3.
Vamos a identificar unas condiciones bajo las cuales los subproblemas derivados de otros superiores se van a repetir. Sea un problema P=(A,M) y un conjunto de soluciones ScA de forma que:
3
Este sumatorio se puede sustituir 2'"-1 por...
27
Programación dinámica
2.1 Introducción
Si tenemos dos elementos consecutivos a,,,a,,.,eA y sus pesos son iguales, es decir, peso(«,,) = peso(cí,,./), entonces....
28
2.1 Introducción
Programación dinámica
Cuando a,,eS y a,,.¡£S, se generará una llamada a la función mochila: => Mochila(A - la,,, a,,./1, M - peso(a,,) ) Cuando a,,eS y a^/eS, de nuevo se generará otra llamada a la función mochila: => Mochila(A - la,,, a,,.,I, M - peso(a,,.,) ) Se ha partido de la igualdad entre pe,w(a,j y peso(a,,.i) con lo que las llamadas serán exactamente iguales y los cálculos se repetirán a partir de esta llamada y para todos sus descendientes. Veamos un traza:
Aquí tenemos que pesóla,) - pex<>{a2) entonces las repeticiones que tendremos serán:
Figura 7 . Repeticiones de suhprobk-mas pura la llamada Mochilaí |a,.a ; .a<|.6i
¿Qué se puede hacer?. La solución es guardar los resultados de los problemas intermedios para evitar resolverlos más de una vez. Planteamos el esquema iterativo (Solución Iterativa) como una matriz Mochila(/¡, Af] donde n es el número de elementos a examinar y M es el peso máximo de la Mochila. ¿Por qué se utiliza esta matriz de dimensiones nxM? Si nos fijamos en la Figura 7, el problema queda definido por una tupia P=(elementos,peso). Los elementos pueden tener un valor de O a n, mientras que el peso puede tener un valor de ü a M, por lo que con una matriz de dimensiones nxM se pueden almacenar todos los posibles problemas generados.
29
2.1 Introducción
Programación dinámica
El Algoritmo Iterativo queda como sigue:
para j=0 hasta M Mochila[0,j] = 0 fin para para /= / hasta n para j-0 hasta M
fin para fin para La solución viene determinada en la casilla Moc/ulaln, M] Se ha encontrado la solución a este problema para un problema genérico. Obviamente ia complejidad temporal es O(n-M) menor que O(2") obtenida con el algoritmo recursivo si M«2".
EJEMPLO 2.1.4. n=3
valor peso
0 1 2 3
(i) n
i
¡
2
3
j 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6
30
peso(di)
4
2
2
M=6
a¡ 3 4
0
1
0 0 0 0
0 0 0 0
a2 1 2
2
0 0
I
2
«t 2 2 (j)M 3
0 0
1
7
4
0 3 3 3
Sí
NO
valor(a¡) + Mochilaf i-1, j - peso(a¡) ] 3 + Machila[0, -4] = -oo 3 + MochilalO. -3¡ = -« -? + MochilalO, -2J = -<« 3 + Mochila 10. -// = -«> 3 + MochilalO, 0} = 3 3 + MochilalO, IJ = 3 3 + MochilalO, 2] = 3 / +Mochilal/, -2] = -oo 1 + Mochila! 1, -// = -«, / + Mochilall, O/ = 1 1 + Mochilall, ¡¡-I 1 + Mochilall. 2] = 1 1 + Mochilall, 3] = / / + Mochilall, 4] = 4 2 + Mochilaf2, -21 = -°° 2 + Mochila[2. -I] - -°° 2 + Machi la ¡2, 0¡ = -« 2 + Machi la,' 2. ¡¡ = -00 2 + Mochila! 2, 2] - 2 2 + Machila¡2. .?/ = 2 2 + Mochilal2, 4] = J
Mochila[ i-l,j]
0 0 0 0 0 0 0 0 0 0 0 3 3 3 0 0 0 0 3 3 4
5
6
0 3 3 3
0 3 4 (5) Max 0 0 0 0 3 _•? 3 0 0 1 1 3 3 4 0 0 2 2 3 3 (5)
2.1 Introducción
Programación dinámica
Observamos que las funciones que se utilizan en el esquema iterativo son exactamente iguales al del esquema recursivo, ya que la Figura 6 puede reescribirse por la Figura 8. Los problemas representados en la Figura 8 están expresados en términos de parejas de enteros. Por ejemplo, el nodo principal (3,6) consulta dos casillas la (2,4) y la (2,6). La primera (2,4) suponiendo que el elemento 3 se ha introducido en la mochila y la casilla (2,6) suponiendo que no.
Figura 8. Codificación del problema con un par de índices enteros
CONCLUSIONES: Este algoritmo iterativo de programación dinámica es útil si M « 2". El algoritmo se puede modificar fácilmente para saber que objetos son los que hay que coger. Se puede reducir la complejidad espacial a un par de vectores de tamaño M.
La filosofía de la programación dinámica consiste en: 1.- Plantear la solución en forma recursiva. 2.- Transformar la solución a una forma iterativa.
Bibliografía: [HS.78]
Capítulo 1, Capítulo 5 (The general Method, 0/1 - knapsack).
[Mi,86]
Capítulo 9 (Introduction & examples).
[Sn,92l
Capítulo 1.
[BB,90]
Capítulo 5.
[BB.97]
Capítulo 8.
31
This page intentionally left blank
2.2 Esquema rectirsivo
Planteamiento: Propondremos un esquema recursivo para la resolución de problemas de programación dinámica, por ello debemos definir perfectamente, todas y cada una de la funciones que lo integran, así como su relación con el esquema general. También deberemos demostrar que el algoritmo es correcto bajo ias propiedades y principios que establezcamos.
Objetivos: Que el alumno conozca el funcionamiento del esquema recursivo de programación dinámica. Que el alumno identifique las funciones básicas del algoritmo recursivo en la resolución de un problema. Que el alumno comprenda el funcionamiento de las funciones básicas y su interrelación. Que el alumno comprenda la corrección del esquema recursivo de programación dinámica.
.: 33
Programación dinámica
2.2 Esquema recursivo
Para abordar programación dinámica es conveniente comenzar con un diseño de nuestro problema de manera recursiva, ya que, es la forma más fácil de implementar y de entender. A continuación pasaremos a forma iterativa donde se aprovechan los resultados de los subproblemas, generados y guardados en un almacén, para solucionar problemas mayores hasta llegar al original. Definiremos A como el espacio de problemas, 5 como el espacio de decisiones y p como es espacio de soluciones. Estas definiciones generales las deberemos de concretar para cada problema dado. A lo largo de este capítulo ampliaremos la información sobre estas tres definiciones. Dado un problema, éste se descompone en subproblemas semejantes al original. La función encargada de descomponer un problema en subproblemas derivados la llamaremos descomposición. Ésta recibirá un problema y producirá un conjunto de pares (subproblema con la decisión relacionada). Sea Pe A, siendo A un conjunto cualquiera de problemas, entonces tenemos que... descomposición(P) = / (X/, X2 X,,,x) X/eA, xeó } donde X es subproblema derivado de P y, x es una decisión asociada al subproblema X.
EJEMPLO 2.1.1.
En el caso del problema de la mochila podríamos comenzar definiendo formalmente sus parámetros de entrada y de salida. Sea A el conjunto de elementos que tenemos que examinar. Definición de problema Cjto. de elementos x Peso máximo Definición de decisión Si se coge o no, un elemento de A Definición de solución Beneficio máximo Para plantear como se va a resolver este problema podemos hacerlo definiendo la función descomposición que descompondrá estos problemas en subproblemas similares. Sea P-( (a,,a2
aj, M) la función queda de la siguiente forma:
Vamos a pasar a plantear el esquema principal en el que integraremos tanto la función descomposición como otras básicas, necesarias para resolver problemas de programación dinámica.
34
Programación dinámica
2.2 Esquema recursivo
Esquema recursivo de programación dinámica :• función PDR ( P : A): p si Contorno(P) entonces devuelve Inicio(P) si no devuelve Combinarf Cálculo(PDR(X,),..., PDR(X,,),x) } V(X¡,..., Xn,x)e Descomposición( P) fin si fin función donde: 1.- Función Contono: Esta función indica si un determinado problema es básico o no. Entrada: A un problema. Salida: ,2J un booleano {verdadero, falso] según estemos en un problema básico o no. Contorno: 2.- Función Inicio: Esta función es la encargada de devolver la solución correspondiente a un problema básico. Entrada: A un problema. Salida: p una solución.
¡nido: 3.- Función Descomposición: Se encarga de devolver todos los subproblemas derivados directamente del actual que se le pasa como parámetro. Entrada: A un nodo del árbol de estados. Salida: ^(A* x 8) conjunto de subproblemas y sus correspondientes decisiones. Descomposición: 4.- Función Cálculo: Esta función se encarga de calular una solución a partir de un subproblema y una decisión. Entrada: p+ al menos una solución de un subproblema y 8 decisión que generó el subproblema. Salida: Nueva solución p.
Cálculo: 5.- Función Combinar: Esta función escoge ¡a mejor solución. Entrada: p* conjunto de varias soluciones (al menos una). Salida: 8 mejor solución.
Combinar
35
2.2 Esquema recursivo
Programación dinámica
EJEMPLO 1.1.2.
Aplicando el esquema al caso de la mochila donde un problema queda definido como P-(A,M) con 4=conjunto de elementos y /Vfepeso máximo:
Contorno(P)= ¡nicio(P) s Descomposición( P) =
Cálculo(r,d) = Combinar =
Máximo
Expresando gráficamente las funciones arriba definidas obtendríamos:
Figura 9. Traza con la función de programación dinámica recursiva (PDR).
El árbol anterior (Figura 9) contiene cada una de las funciones definidas en el esquema y se puede observar exactamente en el lugar en el que actúa. Las flechas ¿T significa si la función se ha aplicado en orden descendente o ascendentemente, respectivamente.
36
2.2 Esquema recursivo
Programación dinámica
Corrección de un algoritmo
Para demostrar la corrección de ios algoritmos recursivos generalmente se utiliza el método de inducción. Principio de Inducción
Sea
P(x) el predicado que deseamos demostrar y sea bel) una cte.
Podríamos interpretar el enunciado anterior como que si se cumple un predicado para unos casos básicos y para casos mayores que los básicos demostramos que estos dependen de los anteriores. Entonces quedaría demostrado que el predicado se cumple en el conjunto D. Si desglosamos la expresión anterior por términos: Sea b una constante. Esta expresión nos dice que hay un número finito de casos base, para los cuales sabemos que se cumple P(x). Podemos comprobarlo uno por uno, ya que el número de casos es finito. Si de casos anteriores v, somos capaces de deducir casos mayores como .\. Demostramos que si p(y) P{x). Si se cumplen los dos casos anteriores podemos deducir que cualquier elemento del conjunto D cumple la propiedad P. Cuando hagamos una demostración por inducción aparecerán siempre tres apartados: Base de inducción (B.I.): Casos básicos de la demostración. Simplemente se enuncian. Hipótesis de inducción (H.I.): La expresión que se pretende demostrar, suponernos que se cumple siempre para casos menores a uno dado. Paso de inducción (P.I.): A partir de casos menores tenemos que llegar al caso actual y la expresión quedará demostrada por el método de inducción.
37
Programación dinámica
2.2 Esquema recursivo
EJEMPLO 1.1.3. Queremos demostrar que la siguiente fórmula es cierta para cualquier número entero.
En este caso el dominio D = 1)
Base inducción:
2)
Hipótesis de Inducción: Sea
3)
Paso Inducción:
entonces
es cierto que:
Vamos a demostrar que se cumple P(x).
EJEMPLO 1.1. 3. Queremos demostrar que la siguiente expresión es cierta para cualquier número entero.
¿Estamos demostrando un imposible? El error radica en aplicar la Hipótesis de Inducción cuando loi. No podemos asegurar que siempre n será mayor que I, entonces la deducción de que (a1 = I) es incorrecta.
EJEMPLO 1.1.4. Vamos a demostrar que "todos los qatos son del mismo color" B.I.: H.I.: P.I.:
Sea un conjunto con 1 gato => Es del mismo color Cualquier conjunto de gatos cuya talla es menor que la de todos los gatos => Son del mismo color. Sea A un conjunto de gatos, Card(A) = m Dividimos A en 2 subconjuntos no vacíos, tales que, Aplicando la hipótesis de inducción todos los gatos de A¡ son del mismo color, también todos los gatos de A2 son del mismo color, como hay gatos comunes a los 2 conjuntos =? A/ y A? son del mismo color.
38
2.2 Esquema recursivo
Programación dinámica
¿Qué ocurre en este caso? Existe un conjunto con m=2 que no cumple las condiciones que no se puede aplicar la H.l. ni obtener la conclusión final que buscábamos.
por to
Con estos dos últimos ejemplos se pretende demostrar que existen casos en los que no es fácil aplicar e! principio de inducción. En general el principio de inducción no se puede aplicar para demostrar algoritmos, porque no se puede establecer una correspondencia con 'Y de forma fácil, en el espacio del problema. Para solucionar este problema vamos a generalizar el principio de inducción. Lo primero que haremos es definir una relación de orden estricto sobre el conjunto en el que trabajemos.
DEFINICIÓN 1.1.1. Una relación de orden estricto sobre un conjunto es aquella que cumple las propiedades: Irreflexiva, antisimétrica y transitiva. Sea R una relación sobre los conjuntos A,B y C.
Sea una relación de orden R sobre un conjunto D. Esta relación de orden puede ser de dos ticos: Total o lineal: Cuando todos los elementos del conjunto están relacionados entre sí. Parcial: Cuando existen elementos en el conjunto que no están relacionados.
39
2.2 Esouema recursivo
Programación dinámica
EJEMPLO 1.1.5. En
orden total o lineal
En En
orden parcial, ya que, orden total o lineal
Para definir el concepto de elemento base, primero debemos de introducir el concepto de minimal.
DEFINICIÓN 1.1.2. Un minimal, en un conjunto ordenado (D,<), es el elemento
EJEMPLO 1.1.6. En
es el cero.
En En
no existe minimal
Expresado de una forma gráfica el principio de inducción general necesita cuando se dibuja el esquema de relación, que toda rama tenqa principio. Veamos...
DEFINICIÓN 1.1.3.
Una relación de orden es Noetheriana en un conjunto subconjunto no vacío de D, tiene por lo menos un minimal.
ordenado (£>,<), si todo
EJEMPLO 1.1.7. En En
40
es Noetheriano porque tenemos un elemento base que es el 0. no es Noetheriano porque no tenemos elemento base.
2.2 Esquema recursivo
Programación dinámica
Teorema: Toda relación de orden estricta sobre un conjunto finito es Noetheriana. Demostración: La demostración la realizaremos por reducción al absurdo4. Sea A un conjunto finito A={a,,, «,. a, antisimétrica, transitiva).
a,J, con una relación de orden estricta (irreflexiva,
Suponemos por R.A. que la relación no es noetheriana, por lo tanto, iBcA B no tiene minimal, es decir, Va/eB, Ba¡eB I «,<«„ como se cumple la propiedad irreflexiva (i¿j), y con la propiedad antisimétrica y transitiva se evita formar bucles, por lo tanto, estamos en una serie infinita de elementos. Si ¡B ¡= <x =$ ¡A /= « y, hemos partido de la hipótesis de que A es finito. Hemos llegado a una contradicción, (c.q.d.)
2.2.1
Principio de inducción general
DEFINICIÓN 2.2.1.1.
Sea (D,<) una relación de orden estricta y noetheriana, definida sobre el conjunto D, entonces:
Se puede interpretar la definición anterior como: si se cumple un predicado para un conjunto de casos básicos v para el resto de los elementos del conjunto demostramos que dependen de los anteriores. Entonces quedaría demostrado que el predicado se cumple para todo el conjunto D. Si desglosamos la expresión del principio de inducción general anterior en términos: Sea Minimal(D) el conjunto de casos básicos para los cuales se cumple la propiedad P. Para cualquier elemento del conjunto (aeD) demostramos que se cumple la propiedad P(a) sabiendo que P(a) se deduce de elementos menores (heD I b
4
La demostración por Reducción al Absurdo (R.A.) pretende llegar a una contradicción neqando a-^b (que es lo que queremos demostrar). El razonamiento lógico es el siguiente: Si tenemos demostrar (a-»b) por R.A. entonces tenemos que encontrar un absurdo en
41
Programación dinámica
2.2 Esquema recursivo
Para poder demostrar la corrección del algoritmo recursivo de PD (Programación Dinámica) habrá que definir un orden noetheriano sobre el espacio de problemas. Este orden vendrá inducido por la función descomposición de la siguiente forma: Sea A el espacio de problemas y 5 el espacio de decisiones. Sea problemas cualesquiera diremos que A
dos
para cada problema determinado habrá que demostrar que: 1. Descomposición induce una relación de orden estricto noetheriano. 2. Todos los rninimales vienen dados por contorno.
EJEMPLO 2.2.1.1.
En el caso del problema de la mochila se demostraría teniendo en cuenta el tamaño de elementos del problema que nos pasan: 1 .a) La relación es de orden Irreflexiva: Siempre que aplicamos descomposición quitamos un elemento al conjunto, entonces es evidente que nunca cumplira Antisimétrica: Por la misma razón que en la propiedad anterior entonces nunca ya que B tiene un elemento menos. Transitiva: 1.b) Noetheriano Supongamos por R.A. que no lo es, entonces, 3/4eA un subconjunto que no tiene minimal, podemos construir una serie del problema en la que haya un elemento «e A que irá reduciendo el tamaño del conjunto hasta que llegue a un elemento, tal que, el tamaño del problema sea O (cero) y, este es minimal. Hemos llegado a una contradicción lueao c.a.d. (También podemos hacer referencia al teorema anterior que nos dice que toda relación de orden estricta sobre un conjunto finito es Noetheriana). 2) Todos los rninimales vienen dados por contorno Es así por construcción del algoritmo.
EJEMPLO 2.2.1.2. Vamos a ver primero como quedará el esquema PDR (Programación Dinámica Recursiva) para el caso de la mochila y, luego demostraremos que es correcto. función PDR si Contorno(P) entonces devuelve Inicio(P) si no devuelve Combinar! Cálculo
fin si fin función
42
2.2 Esquema recursivo
Programación dinámica
donde P=(A,M) con Aserto, de elementos y Mspeso máximo.
Contorno(P)= Inicio(P) s Descomposición(P) = Cálculo(r,d) = Combinar =
Máximo
Teorema 2.2.1. Sea VPe A donde P=(A,M) con Ascjto. de elementos y Mspeso máximo.
con
todos los subconjuntos de elementos
que caben en la mochila. Demostración: B.I.: H.I.:
P.I.:
en el segundo
en el primer término recorremos todo término
Examinamos todos las
recorremos
posibilidades. (c.q.d.)
4?
2.2 Esquema recursivo
Programación dinámica
Existe una propiedad importante que cumplen la mayoría de problemas que pueden resolverse por programación dinámica. Si demostramos que se cumple el principio de optimalidad para un problema podemos buscar su solución por programación dinámica. Sí (Principio de Optimalidad) => (Programación Dinámica)
2.2.2
Principio de optimalidad
Diremos que en un espacio de problemas A se cumple el principio de optimalidad si VPeA {di,...,d,,,}, d,e5 es la secuencia óptima de decisiones que resuelven P, entonces:
si X¡:(Xi,...,X(n,dm) eDescomposición(P)
d¡,...,d,,,.i resuelve X¡ EJEMPLO 2.2.2.1. Aplicado al caso de la mochila
Sea P=(fa, aj. M) Sea (dhai)... (d,,,,aj con ¿¿e/OJ}
la secuencia de decisiones que resuelve P, entonces...
J' es cualquier secuencia que cumpla la restricción de caber en la mochila y, d es la secuencia que maximiza el valor, cumpliendo también con la restricción. Además...
descomposición({ai,...,a,»}, M) =
Hay que demostrar que (d¡,a,)... (dm,am) es solución de ({a, a,,,.,}, M-dm peso(aj).
Supongamos que no es cierto por R.A.
: 44
2.2 Esquema recursivo
Programación dinámica
EJEMPLO 2.2.2.2. Todo problema que cumple el principio de optimalidad se puede resolver por programación dinámica, pero ¿qué ocurre en sentido inverso?. Queremos hallar el camino mínimo en un grato. Para hallar el peso total un camino multiplicaremos el peso de las aristas que son reales positivos.
Si hallamos el camino mínimo usando el producto 1-»3-»4, comprobamos que es un camino mínimo, sin embargo, 1—>3, no lo es para los nodos 1 y 3.
Bibliografía: [HS,78]
Capítulo 3, Capítulo 5,
[Mi.86]
Capítulo 9 (The Theorical Foundations of Dynamic Programming).
[Sa,81]
Capítulo 2 (Program Correctness), Capítulo 6.
[Sn,92]
Capítulo 2, Capítulo 13.
[BB.901
Capítulo 5.
[BB.97]
Capítulo 8.
45
This page intentionally left blank
2.3 Esquema iterativo
Plateamiento:
Este tema es el más interesante de la programación dinámica, ya que, el esquema iterativo es el que nos podrá reducir la complejidad del problema. Se tendrá que observar las llamadas a subproblemas del esquema recursivo para establecer una relación de orden lineal con estas llamadas. Posteriormente estableceremos un sistema de almacenamiento para evitar la repetición de la misma llamada y, por último resolver los subproblemas de menor a mayor, hasta obtener el resultado final.
Objectivos:
Que el alumno conozca las condiciones bajo las cuales podemos aplicar el esquema iterativo. Que el alumno conozca el funcionamiento del esquema iterativo del programación dinámica. Que el alumno conozca la relación entre las funciones del esquema recursivo y el iterativo. Que el alumno comprenda la necesidad de establecer, en un problema, una relación de orden lineal y un almacenamiento indexado para la solución de subproblemas. Que el alumno comprenda la correspondencia entre la resolución de un problema por el esquema recursivo y el iterativo.
47
Programacl6n dlnamlca
2.3 Esquema iterativo
Este apartado es el mas interesante de la programacion dindmica, con el esquema iterativo reduciremos la complejidad temporal de la solucion del problema. Se tendra que observar las llamadas a subproblemas del esquema recursivo para establecer una relacion de orden lineal con estas. Posteriormente estableceremos un sistema de almacenamiento para evitar la repetici6n de la misma llamada y, por ultimo resolveremos los subproblemas de menor a mayor, hasta obtener el resultado final.
EJEMPLO 2.2.1.
Repeticibn de subproblemas que surgen de la descomposicion del problema original.
Como se ha dicho en el parrafo anterior la soluci6n iterativa se caracteriza por: a) Almacenamiento de los resultados de cada subproblema: Ello permite utilizer dicho resultados sin tener que calcularlos de nuevo para cada llamada. b) Resolver los problemas en un determinado orden: Sabemos que secuencia tendra la resolucion de problemas. Resolveremos de menor a mayor y cuando se necesiten los resultados de subproblemas menores, estos ya estaran resueltos. Como consecuencia directa de los puntos anteriores, el programa iterativo necesitara rticis espacio de memoria para guardar los resultados que en el esquema recursivo. Definicion 1.1.1: Sea DI el conjunto de los subproblemas de A Sea As A, DA queda definido por:
edescomposicl6n( Evidentemente DA sera finite (orden Noetheriano), ya vimos, que la funcion de descomposicion inducfa un orden en A (Definicion 2.2.1 .1 .) y, por tanto, en DA. Este orden que se induce directamente no tiene porque ser lineal (total). Por ello vamos a extenderlo de forma que sea lineal y, preserve el orden inducido por descomposicidn5: Como <• es lineal, todo par de elementos de DA estaran relacionados y se podran escribir en Ifnea de forma que Vs,eDA con I D/s, I =n: (siendo s: minimal)
5
El sfmbolo <• significa orden lineal 48
2.3 Esquema iterativo
Programación dinámica
Vamos a definir las funciones genéricas que proporcionarán el recorrido por el conjunto (DA,<-): i) Primer subproblema px ¡i) Siguiente subproblema .v.v
(Siendo T un subproblema ficticio, fin de conjunto)
2.3.1
Estructura indexada de datos
Supongamos que tenemos una tabla indexada por DA, llamada almacén:Vp[DA], con todos los posibles vectores DA y sus soluciones asociadas p. Pretendemos que almacén/B] almacene el resultado del subproblema VBeDA.
Contorno(B) almacén[B] = Inicio(B) ,Contomo(B) almacénlB] = CombinarfCálculo(PDR(Xi) PDR(X,,),x)f V(X/ X,,,x)eDexcHinposición(B) Supongamos que almacén se rellena siguiendo el orden dado por <•, entonces \/X<-B, PDR(X) se hallará resuelto, antes que para B, y por tanto, estará en almacén.
almacénlB] = Coinbinar{Cálculo(alniacén[X¡],...,cümacéii[X,,],.K)l V(X¡ X,,,x)€ Descomposición B)
2.3.2
Esquema Iterativo
función PDI var almacén : Vp[DA] X,S: .v .•
fin var S = ps() repetir si Contorno(S) entonces almacén! S] = Inicio(S)
sino
almacén[S] = Combinar {Cálculo( almacén[X/] ulinacén[X,,],x)} V(X¡ X,,,x) e Descomposición(S)
fin si
S = ss(S) hasta devuelve almacén[A]
jin junción
49
Proclamación dinámica
2.3 Esquema iterativo
Este esquema iterativo propuesto es equivalente al esquema recursivo, en cuanto a que es capaz de resolver el mismo problema, lo que demostraremos a continuación. TEOREMA 2.3.1.1: Sea VAeA tenemos que los dos esquemas son capaces de resolver el mismo problema. PDR(A) = PDJ(A) Demostración: = cilmacén[B) por inducción utilizando <•.
B.I.:
pseDA PDR(ps) - Inicio(ps) - almacénfps] PDR(X) = almacénfX]
P.I.:
PDR(B) =
Se deduce de la demostración PDR(A) = almacénlA] - PDl(A).
anterior
que AeDA, (c.q.d.)
y
EJEMPLO 2.3.2.1.
por
tanto,
Vamos a ver por último como quedará el esquema PDI (Programación Dinámica Iterativa) para el caso de la mochila donde el problema es P=(S,M) donde 5 es el conjunto de piezas y M es el peso máximo de la mochila. función va almacén [PJ: p
fin var S = px() repetir si Contorno(S) entonces (ilmacénfSI = Inicio(S) si no almacén[S¡ = Combinar/Calculof almacénfX ¡) almacénfX,,),*)} Descomposición(S) fin si S = ss(S) hasta devuelve almacen¡ PJ fin función
50
2.3 Esquema iterativo
Programación dinámica
Las funciones del recorrido serían sobre ei orden total son: función ps() devuelve (0,0) fin función función ss((s,m) si m < M entonces devuelve (s, m) sino si s < S entonces devuelve (s, 0) si no devuelve fin si fin si fin función Las funciones se conservan del esquema PDR al PDI. En casos prácticos si queremos evitar almacenar todos los casos de contorno (que puede-ser un número elevado) hay que matizar el acceso al almacén para que no se salga de rango. función almacén(P:A): p si Contorno(P) entonces devuelve ínicio(P) si no devuelve tilmacén[P] fin si fin función
Bibliografía: [HS.78]
Capítulo 5.
[Mi,86]
Capítulo 9 (Techniques for Reducing Computations in Dynamic Programming).
[Sa,81]
Capítulo 2 (Program Correctness), Capítulo 6.
[BB,90l
Capítulo 5.
[BB.971
Capítulo 8.
:¡ 51
This page intentionally left blank
2.4 Problemas resueltos
Planteamiento: Con esta unidad totalmente práctica se pretende ilustrar la aplicación directa de la teoría vista en las unidades pertenecientes a este módulo. Veremos el planteamiento de un problema, la resolución del mismo por el esquema recursivo de programación dinámica, demostración del principio de optimalidad y resolución por el esquema iterativo de programación dinámica. Finalmente obtendremos las complejidades resultantes del algoritmo recursivo e iterativo para comprobar la mejora.
Objetivos: Que el alumno aplique los métodos vistos en este módulo a problemas prácticos. Que el alumno conozca distintas formas de resolver un mismo problema aplicando técnicas de programación dinámica. Que el alumno adquiera destreza en el uso de técnicas de programación dinámica aplicadas a problemas.
53
2.4 Problemas resueltos
Programación dinámica
2.4.1
Hallar el camino mínimo en un grafo multietapa.
Sea un grafo mulíietapa G=(N,A) donde N son los nodos y -4 las aristas, siendo un grafo dirigido y, ponderado por una función d(A)...
donde AcNxN y, los nodos N estarán divididos en K>2 conjuntos disjuntos N,, ¡<¡
Figura 10. Gral'o de 9 nodos con 5 etap:
Como podemos observar en la Figura 10 tenemos como ejemplo un grafo multietapa con 5 niveles y 9 nodos. El problema que se plantea es el de encontrar el camino mínimo desde el nodo Inicial al nodo Final, y nuestra solución se puede expresar como:
el coste del camino c será D(c), que será la suma del peso de las aristas que lo forman:
denotaremos con C(a,b), el conjunto de todos los caminos posibles de a-*b, El problema consiste en encontrar un camino tal que...
54
2.4 Problemas resueltos
2.4.1.1
Programación dinámica
Principio de optimalidad
Demostraremos como este problema de hallar el camino mínimo cumple el principio de optimalidad. Sea e/,,, = (a/, a2 a,,) el camino mínimo entre ai—>an, entonces su distancia será...
la distancia mínima entre «/—*/„./ será...
si no fuera así por reducción al absurdo, existiría otro camino que mejoraría el coste íf,-*/„.,
entonces
hemos llegado a una expresión absurda, porque D(c/.J es el mínimo y hemos encontrado otro menor. c.q.d.
Este problema se puede resolver desde dos visiones diferentes. Una, recorriendo las aristas en sentido contrario desde delante hacia atrás. Y la otra visión es resolverlo de atrás hacia delante.
2.4.1.2
Algoritmo recursivo (hacia atrás)
Un problema vendrá determinado por el estado de llegada, suponiendo hay N nodos y A aristas fijas (Grafo Multietapa Esquema Recursivo)6.
entonces el esquema POR queda: (Nodos) (Aristas) (Distancia) Contorno(a) = (a=I) Iniciad) =0 Cálculoi r, ( a , b ) ) = r + d(u,b) Descomposición(a) = { (b, (b,a)) Combinar = Mín
si a es el nodo inicial r. distancia actual más la arista (b,a)<=A, beN,./, aeNJ
Hay que comprobar que la descomposición induce un orden Noetheriano:
(1
Recordaremos que C(í,a) son todos los posibles caminos entre el nodo inicial y en nodo a.
55
2.4 Problemas resueltos
Programación dinámica
por tanto, cumple las propiedades: Irreflexiva, Antisimétrica y Transitiva. Además es Noetheriano, siempre llegamos a N, = {1} que es minimal.
Teorema:
Demostración: Sabemos que la función descomposición nos induce un orden Noetheriano.
La demostración la hemos realizado para una nodo cualquiera del grafo, ahora tenemos que particularizarlo para en caso en que el no de partida sea F (nodo Final)
Corolario:
Si además, quisiéramos conocer el camino bastaría cambiar la función cálculo y combinar que son las actúan sobre las soluciones. (Nodos) (Aristas) (Distancia x Cadena de Nodos) Contorno(a) = (a-l) si 'a' es el nodo inicial fnicio(a) = (0,a) Cálculo((r,c),(a,b)) = ( r + d(a,b), c-b ) Y distancia actual y 'c' camino actual Descompoxición(ci) = / (b, (b,a)) I (b,a)eA, beN,./, cieNvj Combinar((r/,cl) (rm,c,,,)) s(>,,c/) / /•/ = Mín{r,,r2 r,,,)
!56
2.4 Problemas resueltos
2.4.1.3
Programación dinámica
Algoritmo iterativo
Supongamos que los n nodos del grato conservan el nivel de las etapas ordenan de la siguiente forma:
se
Vamos a etiquetar cada nodo con un entero desde / hasta « (número de nodos). Dentro de cada nivel se le asignará un número arbitrario correspondiente a ese nivel.
Ahora tenemos ios nodos con un orden lineal (en este caso el mismo que tienen los naturales). función ps() devuelve 1 fin función
N¡=I
función xx(i) si (i < n) entonces devuelve i+1 si no devuelve f fin si fin función función PDI(P) = i = px() repetir si Contomo(i) entonces almacén/i I = Inicio(i) si no almacén[ i ¡ = Cvmbmar{Cálculo(it¡macéiila],(b,c))} Descontposición(i) fin si i = sx(i) hasta i devuelve almacén! P¡ fin función Funciones del esquema iterativo PDI quedan como siguen: Contorno(a) = f a = / j Inicio(l) =0 Cálculo( r, (a,b)) = r + d(a,b) Descomposición( Combinar = Mín
si a es el nodo inicial r: distancia actual más la arista
57
2.4 Problemas resueltos
Programación dinámica
Podemos observar que estas funciones son prácticamente idénticas a las expuestas en el esquema recursivo. Vamos a realizar una traza (Tabla 7) correspondiente a la Figura 10:
Nodo
/
2 .? 4 5 6 7 8 9
Cálculo
Nivel
(0) tabla[l]+d(i,2) = 0+9 = (9) tablall]+d(l,3) = 0+7=(7) tablall]+d(l,4) = 0+3 = (3) tahla[2/ +(1(2.5) = 9+4 = 13 iahla[31+d(3,5) = 7+2 = 9 tab!a[4]+d(4,5) = 3+2 = (5) tabla[3]+d(3,6) = 7+3 = 10 tabla[4J+d(4,6) = 3+5 = (8) tahia[5]+d(5,7) = 5+6= II tabla[6]+d(6,7) = 8+ll =(11) tcibla[6]+d(6,8) = 8+4 = (12) tablal7l+d(7,9) = ¡1+4= 15 taNci[8]+d(8.9) = 12+2 = (14)
N, N2
NJ
N4
/V5
Tabla 7. Traza del algoritmo iterativo
2.4.1.4
Complejidad temporal
Vamos a comparar las complejidades temporales de los esquemas POR y PDI aplicados al cálculo del camino mínimo en un grafo multietapa.
Sea: N= Número de nodos del grafo. K = Número de etapas del grafo. m = Máximo número de nodos en un nivel. Esquema recursivo PDR: Cada nodo del árbol puede expandirse tanto con conexiones tenga este nodo, es decir m, y este proceso se repetirá hasta llegar al último nivel K. Y sean c/, c? dos constantes correspondientes al número de operaciones. Se puede plantear la siguiente fórmula recurrente:
58
2.4 Problemas resucites
Programación dinámica
Esquema iterativo PDI: Tenemos que recorrer las K etapas del grato elemento a elemento y, a su vez estos elementos se calculan con sus adyacentes m. Y sea c, una constante correspondiente al número de operaciones.
Para ver la ganancia se puede confeccionar una tabla (Tabla 8) con las dos complejidades y ver el número de operaciones que efectúan los algoritmos.
m
Complejidad PDI PDR m2K mK
K 5 5 !ü 10
5 10 10 15
9765625
125 250
10'° lf 10
1000 1500
3125
Tabla 8, Número de operaciones reaii/.ailus con el algoritmo recursivo y el iterativo
Complejidad espacial en el PDI: Obviamente es 0(N) para guardar los resultados en cada nodo, pero en la práctica es O(m), porque necesitamos guardar sólo 2 niveles a la vez para calcular los resultados.
A continuación enunciaremos brevemente como queda la solución al problema del cálculo del camino mínimo en un graío multietapa con la segunda visión comentada, de atrás hacia delante.
2.4.1.5
Algoritmo recursivo (hacia delante)
El problema viene determinado por el nodo salida. entonces: (Nodos) (Aristas) (Distancia) Contorno(a) Inicio(F) sO Cólculo( Descomposición(a) Combinar(a) = Mín
siendo'a'el nodo final siendo Y distancia actual
El desarrollo sería similar al seguido al principio de este apartado.
59
Programación dinámica
2.4 Problemas resueltos
Ejercicios: Terminar de analizar el Algoritmo Recursivo hacia delante. Extender la solución del cálculo del camino mínimo en un grato multietapa para un grato cualquiera.
60
2.4 Problemas resueltos
2.4.2
Programación dinámica
Mínima distancia de edición entre dos cadenas.
La aplicación que le daremos a la mínima distancia de edición entre dos cadenas será de reconocimiento de formas. Tenemos dos imágenes de figuras en 2D, codificadas como cadenas de direcciones (dígitos). Disponemos de funciones básicas para explicar la transformación de símbolos. Estas funciones son: Borrados, inserciones o sustituciones de pixels para que una imagen sea igual a la otra. ¿Queremos averiguar cuánto se parecen estas figuras? Para entender mejor el problema lo acompañaremos de un ejemplo gráfico e iremos comentando las observaciones paso a paso. Sea un alfabeto / - (1,2,3,4,5,6,7,8} que codifica las ocho direcciones en un plano discreto representado en la Figura 11.
Figura 11. Direcciones en un plano
Hgura 12. liiuigen 1
Figura 13. imagen 2
Tenemos la Figura 12 que es la primera imagen con la codificación 3345. Por otro lado tenemos la Figura 13 con la codificación 233566. Una posible explicación de !o que ha sucedido con la Figura 12 para transformarse en la Figura 13 es....
Figura 14 . Una po»¡b¡e transformación de la cadena 3345 en 233566
Además cada una de estas transformaciones lleva asociado un peso o coste de transformación. Inserción P:(a)
P¡: I —> /p
Borrado P¡,(a)
Ph : I -> 7<
Sustitución P,(a,b)
P,: / x / -> :ÁJ
Si partimos de la posible transformación representada en la Figura 14, obtenemos una explicación de lo que ha ocurrido, y por lo tanto, un camino que nos dice que hacer para pasar de la Figura 12 a la Figura 13.
61
2.4 Problemas resueltos
Programación dinámica
Sea t el camino.... t = (i(2), s(3.3). s(3.3). b(4), s(5,5), 1(6), i(6)) y el coste total de la transformaciones sumando sus respectivos pesos P(t) = P,(2) + Ps(3,3) + PJ3.3) + P,,(4) + PJ5,5) + P¡(6) + P,(6) Para cada par de cadenas codificadas se puede encontrar varias transformaciones. El problema es hallar la transformación de mínimo peso. Si llamamos 7",.,,,., al conjunto de todos las transformaciones posibles, entre la cadena V y la cadena V. El problema es encontrar /", para que:
El conjunto de todas las posibles transformaciones entre !v'e V, se puede representar mediante el diagrama cartesiano (Figura 15). Basándonos en las direcciones de la Figura 16.
Figura 16. Direcciones de las transformaciones Figura 15. Tahla de transformaciones
Podemos ver claramente como el problema es encontrar el camino de mínimo peso que parte del origen y llega al destino. ¿Se cumple el principio de optimalidad? Sí cumple este principio, pero dejamos ai lector como ejercicio que lo demuestre.
2.4.2.1
Algoritmo recursivo
Sea l=/l,2J,4,5,6,7,8l direcciones reflejadas en la Figura 11. La resolución a nuestro problema según el esquema recursivo queda como sigue7:
Contorno( (x,y)) = Inicio( (A, A.) j =
Cálculo( r, d ) =
1
Las letras del final del alfabeto (x.y,z) representan cadenas de símbolos. Y las letras iniciales del alfabeto como a,b,c representan un único símbolo.
62
2.4 Problemas resueltos
La operación
Programación dinámica
respresenta la operación concatenación entre cadenas.
Descomposición( (x, y)) =
Mí/?
Combinar =
Evidentemente descomposición induce una relación de orden en (f x I*), ya que, utilizando la función prefijos de una cadena (8> ... f.v'.v'j < f.v.y)
<=>
.v'eP./.vy A v'e-P,/vj,
(.v'.y'Mxy)
además (A.,?i) es minimal, por lo que es un orden Noetheriano.
Teorema: Transformación de mínimo peso resueito con el esquema recursivo.
Demostración:
8
La función P¿x) devuelve el conjunto de los prefijos de una cadena dada. P,( abcde ) = /A, a, ab, abe, abccl, abcdej P¿ abba ) = /A, a, ab, abb, abbaj
M
Programación dinámica
2.4.2.2
2.4 Problemas resueltos
Algoritmo iterativo
Para definir un orden tota! noetheriano vamos a definir primero el conjunto de todas las cadenas posibles que se pueden examinar. Sea DM.v) el conjunto de todos los prefijos extraídos de las cadenas x e v. A.,..v; = / (x',y')/x'<=P¿x)Ay'ePA\) / una relación de orden estricta en D ( v v ) que preserva ia relación < podría ser con la función de prefijos estrictos9:
se puede comprobar que si f.v'y'j < f.v.vj => (.\',\') <• f.v.v) La forma de recorrer el problema vendrá dada por las funciones básicas /«O y .s.vfj, que se pueden definir como:
entonces devuelve
si no
si no
entonces devuelve
r(x)
devuelve
fin si fin c/
Este recorrido se transforma en realidad en el recorrido de una matriz con las longitudes de ambas cadenas desde el inicio (A,,X) hasta llegar (x,y) como representa la Figura 15.
2.4.2.3
Complejidad temporal
Vamos a comparar las complejidades temporales de los esquemas PDR y PDI aplicados al cálculo de ia mínima distancia de edición entre cadenas.
Sea: .v = longitud de la primera cadena. y = longitud de la segunda cadena. Esquema recursivo PDR: Cada nodo del árbol de búsqueda de soluciones puede expandirse con las 3 operaciones básicas de inserción, borrado y sustitución. En el peor caso se expandirá el árbol la longitud de la cadena más larga de las dos de que disponemos.
q
Los prefijos estrictos los representaremos como Prs(x). Ejemplos:
64
2.4 Problemas resueltos
Programación dinámica
Se puede plantear la siguiente fórmula recurrente:
Esquema iterativo PDI: Habrá que revisar cada uno de los elementos de D(A.,.,. Tenemos que recorrer la matriz de dimensiones x por v, calculando cada casilla, que se compone de 3 accesos directos (inserción, borrado, sustitución - ver la Figura 15 y Figura 16).
Para ver la ganancia se puede confeccionar una tabla (Tabla 9) con las dos complejidades y ver el número de operaciones que efectúan los algoritmos.
x
3 4 10 11
y
3 5 11 15
Complejidad PDR PDII 3Máx{x'y} x-y 27 243 ¡77147 14-!rf
9 20 ¡10 165
Tabla 9. Operaciones realizadas por el algoritmo recursivo y el iterativo.
Complejidad Espacial en el PDI: Obviamente es O(x-y) para guardar ios resultados, pero en la práctica es O(mín(x,y)), porque necesitamos guardar sólo 2 niveles a la vez para calcular los resultados.
65
Programación dinámica
2.4.3
2.4 Problemas resueltos
Secuencia mínima para calcular el producto entre matrices.
Se desea calcular el producto matricial M=MiM?---M,l. Dado que el producto de matrices es asociativo, el cálculo de M puede realizarse de varios modos. La elección del modo de cálculo puede tener una influencia considerable en el tiempo total. Si tenemos en cuenta que para el producto de dos matrices A,IXt, y Bí/xr se necesitan p-q-r multiplicaciones escalares. Nuestro problema es calcular el modo en el que se tienen que multiplicar las matrices para obtener el mínimo número de productos escalares.
EJEMPLO 2.4.3.1: Se pretende calcular el producto ABCD de las matrices A(l3x5), B(5x89), C(89x3) y D(3x34). Una forma de calcular es producto es: AB (AB)C ((AB)C)D
5785 multiplicaciones 3471 multiplicaciones 1326 multiplicaciones
es decir, tenemos un total de 10582 multiplicaciones. Hay esencialmente cinco formas de obtener el producto. El número de multiplicaciones en cada caso es: «AB)C)D
10582 54201 2856 4055 26418
Para hallar directamente el mejor modo de calcular el producto, basta insertar los paréntesis de todas las formas posibles y calcular, para cada una, el número de multiplicaciones requeridas. Sea T(n) el número de formas significativamente diferentes de insertar paréntesis en un producto de « matrices. Supongamos que inicialmente se decide dividir entre la i-ésima matriz y la (i+1)-ésima: M=(M,M2-Mi)(Mn.lMn.2-Mll) Tenemos entonces T(i) formas de introducir paréntesis en la parte izquierda y T(n-i) formas de hacerlo en la parte derecha. Dado que / puede tomar cualquier valor entre / y »-/, obtenemos la siguiente recurrencia para T{n).
Complejidad temporal Queda como ejercicio demostrar que
¡66
2.4 Problemas resueltos
2.4.3.1
Programación dinámica
Algoritmo recursivo filasxcolumnas filasxcomúnxcolumnas
Contorno( ¡nicio Sea d-( filasxcomúnxcolumnas) Cálcído( r¡, r2, d) = Combinar(...) =
r¡ + r2+filas-común-columnas Máx(...) subproblema 1 suhproblema 2
Descomposición( P ) =
ecisión
Destacaremos que el esquema general de PDR su función descomposición genera dos subproblemas por cada decisión.
función PDR (P:Á):p si Contorno(P) entonces devuelve ¡nicio(P) sino devuelve Combinar{ Cdlculo(PDR(X,), PDR(X 2),x) I \/(Xi,X2,x) eDescomposición(P) fin si fin función
2.4.3.2
Algoritmo iterativo
Para el ejemplo A(!3x5), B(5x89), Cl89x3) y D(3x34) quedaría: j 1
1
m,,-0
2
m, 2=5785
3
4
m¡j=mín( iriii+m2j+l3-5-3. m/2+mjj+J3-89-33 )=I530
in¡4=mín( mi,+mi4+ 13-5-34, mn+m34+ 13-89-34, m,,+m^+ 13-3-34, )=2856 ni24-mín( m22+mj4+5-89-34, in2_l+m44+5-3-34 )=1845 m ¡4=9078 m44=0
i m?2=0
2 3 4
m2J=l335
m}3=0
La definición de problema se transformará en índices para acceder al almacén de forma que:
PDR filasxcolumnas
PDI que indica el número inicial y final multiplicación de matrices.
de la
67
2.4 Problemas resueltos
Programación dinámica
Por ejemplo Funciones de recorrido Sea P=(i,j) y A/=número inicial de matrices
entonces
Las casillas que se recorrerían serían:
devuelve fin
entonces recorrido en zig-zag.
fin devuelve (i,j) Complejidad temporal PDI: Sea n el número de matrices que compone el producto matricial. Habrá que revisar la parte triangular superior de una matriz //x/¡.
Para ver la ganancia se puede confeccionar una muestra (Tabla 10) con las dos complejidades y ver el número de operaciones que efectúan los algoritmos. Complejidad PDR PDI n2
n
5 10 50 100
14 4862 5- 10-" 2-10-''
25 100 2500 10000
Tabla 10. Número de operaciones realizadas por el algoritmo recursivo y el iterativo.
Bibliografía: [HS.78]
Capítulo 5 (Exercises).
[Mi,86)
Capítulo 9 (Examples of Dynamic Programming Applications).
[BB.90J
Capítulo 5.
[BB,97J
Capítulo 8.
68
2.5 Ejercicios
Plateamiento:
Este apartado presenta enunciados de exámenes que se han realizado en esta asignatura. Por lo que el alumno puede poner en práctica los conocimientos adquiridos en ellas. Hay que tener presente que no existe una forma única de resolver un ejercicio, si no que puede haber varias.
Objetivos: Que el alumno mida su nivel de conocimientos de la asignatura en programación dinámica. Que el alumno se familiarice con la notación y la manera de resolver ejercicios realizándolos el mismo.
69
Programación dinámica
2.5.1
2.5 Ejercicios
Inversiones
Estamos es una consultaría financiera y tenemos que tomar decisiones sobre varias inversiones que tenemos que realizar. Inversión
!:
Cantidad (millonesj 1
Interés (%)
riesgo (%)
il
r1
2
f'i
/•i
n
Ín
'"/i
i»
Disponemos de C(número entero positivo) millones de capital para invertir, y nos piden qué inversiones tenemos que realizar para obtener el mayor número de intereses acumulados. Y si hubiera varias soluciones entonces deberemos elegir la de menor riesgo acumulado posible, para ello podemos invertir varias veces en la misma inversión, según aparece en la tabla arriba indicada. Se pide: a) Que se plantee el problema y que se definan las funciones PDR. b) Que se demuestre que la solución propuesta es correcta. c) Que se enuncie y se compruebe el principio de optimalidad. d) Que se plantee el problema en PDI (reduciendo el coste del PDR). e) Que se definan las complejidades temporales de los algoritmos PDR y PDI propuestos.
2.5.2
Transporte de mármol
Tenemos una empresa de pulido y corte de mármol. El trabajo de esta empresa consiste en recoger piedras extraídas de la cantera y transformarlas en losas de mármol. Tenemos dos camiones en una cantera, cada uno puede transportar como máximo M! y M2 toneladas respectivamente. Tenemos que recoger la máxima cantidad de mármol posible, para ahorrar viajes a estos camiones, sabiendo que existen N bloques de mármol que se pueden escoger para transportar en este viaje. Bloque de mármol
Peso en Toneladas
/
TI
2 3
T,
n
T,,
r,
Queremos saber cua! es la cantidad máxima de mármol (toneladas) que pueden transportar entre los camiones en este viaje. Se pide: a) Que se plantee el problema y que se definan las funciones PDR. b) Que se demuestre que la solución propuesta es correcta. c) Que se plantee el problema en PDI (reduciendo el coste del PDR). d) Que se definan las complejidades temporales de los algoritmos PDR y PDI propuestos.
70
2.5 Ejercicios
2.5.3
Programación dinámica
Conexiones en Internet
Queremos resolver un problema de velocidad en la red Internet. Cuando dos nodos quieren intercambiar datos (usuario, servidor) se atraviesan diversos nodos intermedios de comunicación que reciben y emiten los paquetes de datos. Tenemos información precisa de los nodos que se pueden atravesar para llegar del usuario al servidor y pretendemos establecer una velocidad máxima que no entorpezca el funcionamiento global de la red. Sabiendo que no tenemos que sobrepasar las velocidades máximas establecidas de nodo a nodo. Se pide encontrar el camino y la velocidad máxima de transmisión que se puede establecer entre estos dos nodos.
Se pide: a) Que se plantee el problema y que se dafinan las funciones PDR. b) Que se demuestre que la solución propuesta es correcta (Inducción). c) Que se plantee el problema en PDI (reduciendo el coste del PDR). d) Que se definan las complejidades temporales de los algoritmos PDR y PDI propuestos.
2.5.4
Evacuación de una isla.
Queremos resolver un problema de evacuación de personas en una isla. Disponemos de un avión con la siguiente tabla de posibilidades:
El avión está en una base en el continente y tiene que realizar viajes a la isla para poner a salvo a los pasajeros. Teniendo en cuenta que /„< i/< t,< ...< t,, y cualquier número superior a n que no figura en la tabla anterior, el avión no podría despegar por exceso de peso, y por lo tanto, Vi e. V. r />/i =* /,•=«>. Queremos calcular el tiempo mínimo que tardará el avión en evacuar la totalidad de pasajeros.
Se pide: a) Que se plantee el problema y que se definan las funciones PDR. b) Que se demuestre que la solución propuesta es correcta (Inducción). c) Que se plantee el problema en PDI (reduciendo el coste del PDR). d) Que se definan las complejidades temporales de los algoritmos PDR y PDI propuestos.
71
2.5 Ejercicios
Programación dinámica
2.5.5
Dónde llenar el depósito de gasolina.
Queremos realizar un viaje con nuestro coche desde una ciudad origen a otra destino. Tenemos un mapa de carreteras donde están señaladas todas las gasolineras y, por lo tanto, sabemos las distancias entre ellas. Llenamos el depósito de gasolina que nos permite recorrer K kilómetros (a la velocidad habitual de nuestra marcha). Para ganar tiempo queremos realizar el número mínimo de paradas para repostar combustible. Hay que diseñar un algoritmo de programación dinámica que permita saber por qué gasolineras hay que pasar y en cuales parar para repostar, así como el número de paradas necesarias. Eiemolo: K=300 kms de autonomía con el depósito lleno.
Suponiendo que disponemos de un grafo G=(N,A) con las distancias entre las gasolineras. Se pide: a) Que se plantee el problema y que se definan las funciones PDR. b) Que se plantee el problema en PDI (reduciendo el coste teórico del PDR). c) Que se definan las complejidades temporales de los algoritmos PDR y PDI propuestos.
2.5.6
Salir del laberinto
Queremos encontrar el camino más corto para salir de un laberinto. Para ello se nos proporciona una matriz cuadrada de dimensiones NxN con las casillas que podemos o no visitar. La entrada será la casilla (1,1) y la salida será la (N,N). Las direcciones de movimiento admisibles serán cuatro (Norte, Sur, Este, Oeste). Solución: Se puede pasar NO se puede pasar
(I,I),(1.2),(2,2),(3,2)2)..., (5,6),(6,6)
Pasos:14
Se pide: a) Que se plantee el problema y que se definan las funciones PDR. b) Que se demuestre que la solución propuesta es correcta (Inducción). c) Que se plantee el problema en PDI (reduciendo el coste teórico del PDR). d) Que se definan las complejidades temporales de los algoritmos PDR y PDI propuestos.
72
2.6 Soluciones
Planteamiento: Este apartado ofrece al menos una solución del ejercicio enunciado en el apartado anterior para que sírv/a de referencia al alumno. Insistiendo en que un ejercicio puede resolverse correctamente de diferentes formas.
Objetivos: Que el alumno compruebe su nive! de destreza en al resolución de ejercicios relacionados con la programación dinámica.
73
2.6 Soluciones
Programación dinámica
2.5.1 Inversiones. a) Que se plantee el problema y que se definan las funciones PDR. //Cantidad de millones que tenemos que invertir //Cantidad de millones que hemos decidido invertir //Intereses acumuladosxRetenciones acumuladasxdecisiones Contornof C ) = Inicio(C) = Cálculo((i,r.L),d) = En descomposición agotaremos todas las formas de invertir los mi/lores en un paso.
Descomposición( C) = Combincir((i¡, r¡,L¡)... (ik, rk,Lk)) =
b) Que se demuestre que la solución propuesta es correcta. Sea una solución:
El valor de la solución asociada a t:
Función objetivo:
Siendo I(C) cualquier secuencia de inversiones que sumen la cantidad C. Demostración: B.I.:
PDR(0) = (0,0)
H.I.:
V b < a PDR(b} = Combinar F(t]
74
VKl(h)
2.6 Soluciones
P.I.:
PDR(a)
Programación dinámica
= Combinar
= Combinar
- Combinar F(t) V/e/(
c) Que se enuncie y se compruebe el principio de optimalidad. Sea una solución:
El valor de la solución asociada a t:
Función objetivo a optimizar:
Tenemos el conjunto de cualquier secuencia de decisiones que inviertan una cantidad fijada l(C). Demostración: Tenemos una solución óptima: Si eliminamos la última decisión: Por reducción al absurdo suponemos una nueva secuencia t\ que mejora el resultado anterior para la misma cantidad de millones. Esto lo podemos conseguir de dos modos: 1) Tenemos mayor inversión con /',/. si le sumamos la última decisión....
Hemos encontrado una secuencia que mejora la óptima t,.„, es absurdo.
75
2.6 Soluciones
Programación dinámica
2) Tenemos igual inversión pero con menor riesgo con la inversión f',.<: si le sumamos la última decisión....
Hemos encontrado una secuencia que mejora la óptima />.«, es absurdo. Luego queda demostrado el principio de optimalidad.
d) Que se plantee el problema en PDI (reduciendo el coste teórico del PDR). La estructura de datos que necesitamos es un vector unidimensional la definición de nuestro problema es A = W. Entonces necesitamos una dimensión para la máxima cantidad de millones C.
0
1
2
C
devuelve (0) entonces
ps() = ss(a) =
sino devuelve Jmsi devuelve (a) c) Que se definan las complejidades temporales de los algoritmos PDR y PDI propuestos. PDR: Sea /V=ns de millones
76
2.6 Soluciones
Programación dinámica
PDI: Hay que recorrer el vector lineal y para cada casilla hay que consultar sus anteriores casillas correspondientes a descomposición.
77
2.6 Soluciones
Programación dinámica
2.5.2 Transporte de mármol a) Que se plantee el problema y que se definan las funciones PDR. bloques x Toneladas Camión 1 x Toneladas Camión 2 de bloque x {No se transporta, Camión 1, Camión 2} Toneladas totales transportadas
Contorno? (AMiMi)) ¡mcio((A,MhM2)) Cálculo( r, (i,d)) En descomposición decide .si un bloque va a! camión I al 2 ó a ninguno.
Descomposición((A,Mi,M2) Combinar b) Que se demuestre que la solución propuesta es correcta.
PDR((A,M^M2}}
Demostración:
se cumple que:
PDR
78
2.6 Soluciones
Programación dinámica
P.I.: PDR«A,M hM2))
c) Que se plantee el problema en PDI (reduciendo el coste teórico del PDR). La estructura de datos que necesitamos es un cubo tridimensional, ya que, nuestra definición el problema es A s .rVx.~VxrVT Entonces necesitamos una dimensión el número de elementos otra para la máxima carga del Camión 1 y otra para ia carga del Camión 2.
ps() = ss((a,mi,m?)) =
devuelve (0,0,0) entonces sino si nii<M¡ entonces si no
entonces sino devuelve 75
2.6 Soluciones
Programación dinámica
fin si
fin si
fin si devuelve (a,g,L) d) Que se definan las complejidades temporales de los algoritmos PDR y PDI propuestos. PDR: Sea /V=el número de bloques para transportar
PDI:
Hay que recorrer la matriz cúbica de AxM,xM2 dimensiones y para cada casilla hay que consultar 3 casillas correspondientes a descomposición.
80
2.6 Soluciones
Programación dinámica
2.5.3 Conexiones en Internet. Se G-(N,A) el grato que contiene las conexiones entre el nodo Usuario y el Servidor.
a) Que se plantee el problema y que se definan las funciones PDR. nodo actual x nodos recorridos arista escogida velocidad máxima x nodos de la solución Vamos a plantear el algoritmo recursivo hacia atrás. Partiremos del nodo Servidor y llenaremos al nodo Usuario. Llegaremos a la base cuando el nodo actual es el Usurio
Contornoí ( n , L ) ) lnicio((n,L)) Cálculo( (r,L), (a,b)) En descomposición iremos a nodos adyacentes que no hayamos estado anteriormente..
Descomposición( (n,L)) Combinar((r¡,Li).., (r,,¡,L,,,)) b) Que se demuestre que la solución propuesta es correcta (inducción). Lo que vamos a demostrar es que podemos minimizar el camino a hasta cualquier nodo, por lo que, quedará demostrado para el nodo Usuario.
Sea C(n,L) ei conjunto de todos los caminos desde el nodo n hasta el nodo Usuario sin repetir los nodos de L. Demostración:
81
Programación dinámica
2.6 Soluciones
c) Que se plantee el problema en PDI (reduciendo el coste teórico del PDR). En el esquema iterativo la estructura de datos que necesitamos es una matriz bidimensional, ya que, nuestra definición de problema es A = NxN*. Necesitamos una dimensión para e! nodo actual y otra para saber que hemos recorrido todos los posibles caminos hasta llegar al final.
ps() = ss((a,L)) =
devuelve (0,0) entonces si no
entonces si no
devuelve fin si
fin si devuelve (a,L)
d) Que se definan las complejidades temporales de los algoritmos PDR y PDI propuestos. PDR: Sea Afen9 de nodos del grafo.
PDI: Hay que recorrer la matriz cuadrada de NxN dimensiones y para cada casilla hay que consultar N casillas correspondientes a descomposición.
82
2.6 Soluciones
Programación dinámica
2.5.4 Evacuación de una isla. a) Que se plantee el problema y que se definan las funciones PDR. Cantidad de pasajeros que tenemos transportar Cantidad de personas que transportamos en un viaje Intereses acumuladosxRetenciones acumuladasxdecisiones
Contorno( P ) Inicio(P) Cálculo suma el tiempo de transporte de los pasajeros más el de ida vacío.
Cálculo( r, d ) En descomposición transportaremos los viajeros de todas las formas posibles..
Descomposición( P ) = Combinar^ b) Que se demuestre que la solución propuesta es correcta. Sea una solución:
El valor de la solución asociada a r:
Función objetivo:
Siendo T(P) cualquier secuencia de pasajeros que sumen la cantidad P. Demostración:
83
Programación dinámica
2.6 Soluciones
c) Que se plantee el problema en PDI (reduciendo el coste teórico del PDR). En ei algoritmo iterativo necesitamos es un vector unidimensional la definición de nuestro problema es A =.1T Entonces necesitamos una dimensión para la máxima cantidad de personas P.
ps() = ss(a) =
devuelve (0) si a
c) Que se definan las complejidades temporales de los algoritmos PDR y PDI propuestos. PDR:
84
Sea N=r\- de personas para transportar
2.6 Soluciones
Programación dinámica
PDI:
Hay que recorrer el vector lineal y para cada casilla hay que consultar sus anteriores casillas corresoondientes a rifismmnosirión
85
2.6 Soluciones
Programación dinámica
2.5.5 Dónde llenar el depósito de gasolina. Este ejercicio tiene dos formas de resolverse. Por orden definiremos primero la más lógica y en segundo lugar la más eficiente. Sea un grafo G=(N,A)
a) Que se plantee el problema y que se definan las funciones PDR. 'Autonomía(kms) x gasolinera actual x gasol. Recorridas. 'Gasolinera x se para o no 'n9 de paradas x qasol. recorridas x qasol. con parada Llegaremos a la base cuando la gasolinera actual sea el origen o cuando tengamos una autonomía de kms negativa.
Contorn
Inicio( Cálculo( En descomposición iremos a las gasolineras anteriores si podemos sin repostar o repostando.
Descornposición((a,g,L)) Combinar(
b) Que se plantee el problema en PDI (reduciendo el coste teórico del PDR). La estructura de datos que necesitamos es un cubo tridimensional, ya que, nuestra definición
de problema es
Entonces necesitamos una dimensión para la máxima autonomía K,,ltm otra para la gasolinera actual y otra para saber que hemos recorrido todos los posibles caminos hasta llegar al final.
86
2.6 Soluciones
psü ss((a,g,L))
Programación dinámica
devuelve (0,0,0) si a
si no si L
si no devuelve fin
fin si
fin si
si
devuelve (a,g,L) c) Que se definan las complejidades temporales de los algoritmos PDR y PDI propuestos. PDR:
Sea Afen5 de nodos de! grato.
PDI:
Hay que recorrer la matriz cúbica de NxNxK,IIM dimensiones y para cada casilla hay que consultar 2N casillas correspondientes a descomposición.
87
2.6 Soluciones
Programación dinámica
Procederemos a resolver este problema por otro método más eficiente. Sea el mismo grafo anterior G=(N,A)
a) Que se plantee el problema y que se definan las funciones PDR(bis). gasolinera actual x gasol. Recorridas. 'gasolinera inicial x gasolinera final gasolineras recorridas x gasolineras con parada x autonomía(kms) Llegaremos a la base cuando la gasolinera actual sea el origen.
Contórnoí (a,L)) ¡nicio((a,L)) Cólculo((r,p,k),(a,b)) En descomposición iremos a las gasolineras anteriores si podemos ir.
Descomposición((b, L)) Combinar((r/,p/,ki)...(rm,pm,km)) b) Que se plantee el problema en PDI (reduciendo el coste teórico del PDR)(bis). Esta nueva visión del problema la estructura de datos que necesitamos es una matriz
Necesitamos una bidimensional, ya que, nuestra definición de problema es dimensión para ía gasolinera actual y otra para saber que hemos recorrido todos los posibles caminos hasta llegar al final.
ps() ss((a,L))
devuelve (0,0) si a
88
2.6 Soluciones
Programación dinámica
c) Que se definan las complejidades temporales de los algoritmos PDR y PDI propuestos(bis). PDR: Sea Msne de nodos del grato.
PDI: Hay que recorrer la matriz cuadrada de NxN dimensiones y para cada casilla hay que consultar N casillas correspondientes a descomposición.
89
Programación dinámica
2.6 Soluciones
2.5.6 Salir del laberinto En este ejercicio tenemos que fijarnos en recorrer los puntos posibles pero sin repetirlos, si no se formarían bucles infinitos en el recorrido.
a) Que se plantee el problema y que se definan las funciones PDR. Punto actual y lista de los recorridos hasta el momento VX, Ke Y 'Direcciones posibles 'ns de pasos y la direcciones tomadas Comenzaremos de la casilla (N,N) y llegaremos a la base cuando estemos en el punto inicial (1,1) o si repetimos puntos.
Contorno ¡nicio Cálculo En descomposición iremos a casi/las adyacentes sin salimos de la matriz
Descomposición( Combinar
b) Que se demuestre que la solución propuesta es correcta (inducción). Lo que vamos a demostrar es que podemos minimizar el camino a cualquier casilla, por lo que, quedará demostrado para (N.N).
Sea C(x,y,L) el conjunto de todos los caminos desde (1,1) a la casilla (x,\) sin repetir las casillas en L. Demostración:
90
2.6 Soluciones
Programación dinámica
c) Que se plantee el problema en PDI (reduciendo el coste teórico del PDR). La estructura de datos que necesitamos es un cubo tridimensional, ya que, nuestra definición de problema es , Como a una casilla se puede lleoar de 4 diferentes lugares hay que recorrer todas las posibilidades antes de dar la solución. Necesitamos un triple bucle para recorrer todas las casillas tantas veces como el camino más largo posible dentro de! laberinto (N~).
PS() ss
devuelve (0,0,0) entonces si no entonces si no entonces sino devuelve fin si
fin si fin si devuelve (x,\,L) 91
Programación dinámica
2.6 Soluciones
c) Que se definan las complejidades temporales de los algoritmos PDR y PDI propuestos. PDR: Sea Nsne máximo de casillas. Sabiendo que no se pueden repetir casillas los caminos hipotéticos más largos serían aquellos que tuvieran por longitud N2.
PDI: Hay que recorrer la matriz cúbica de NxNxN2 dimensiones y para cada casilla hay que consultar las 4 casillas adyacentes correspondientes a descomposición.
92
3. Ramificación y poda 3.1 Introducción
Planteamiento:
Este tema introductorio presentará el tipo de problemas que son | abordables mediante la técnica de ramificación y poda. También explicará las fases de las que se compone la resolución de un problema de ramificación y poda j y cómo abordarlas.
Objetivos: Que el alumno conozca los fundamentos de la técnica de ramificación y poda, Que el alumno conozca tipos de problemas a los que se le puede aplicar esta técnica. Que el alumno
comprenda como puede
mejorar un algoritmo de
optimización cuando se podan las ramas del árbol de posibles soluciones.
93
Ramificación y poda
3.1 Introducción
Es importante en este tema introductorio conocer el tipo de problemas que son abordables mediante la técnica de ramificación y poda, por ello se expondrán ejemplos y también se explicará las fases de las que se compone la resolución de un problema de ramificación y poda, y también cómo abordarlas. La técnica de vuelta atrás10 es un caso particular de ramificación y poda. Ésta es una técnica de exploración de árboles, cuyos nodos son estados del problema bajo diferentes decisiones. En cada nodo se calcula una cota inferior y/o superior de los valores de las soluciones eventualmente situadas por debajo de nuestro árbol de soluciones. Si estas cotas demuestran que tales soluciones serán peores que las que se obtendrán en otros nodos o peores que la mejor solución ya encontrada, entonces se abandona la exploración de esa parte del árbol. En su versión más simple, el cálculo de una cota inferior se combina con un recorrido en anchura o profundidad que sirve para podar ciertas ramas del árbol. Muy amenudo, la cota inferior sirve para escoger la rama más prometedora con el fin de realizar una exploración con prioridad. La técnica de ramificación y poda realiza cálculos adicionales a los de exploración para decidir en cada momento cual es el siguiente nodo a examinar, utilizando un conjunto de nodos generados y no examinados. Los problemas que se resuelven por ramificación y poda son problemas de explosión combinatoria. Existen dos tipos: a) Que satisfaga algún conjunto de restricciones.
EJEMPLO 3.1.1 • •
¿Existe una combinación en el problema de la mochila para que el beneficio sea superior a X? ¿Existe una combinación en el problema del viajante de comercio donde la solución sea menor que K?.
b) Problemas de optimización. Se intenta encontrar una solución que satisfaga un conjunto de restricciones y minimice una función objetivo. EJEMPLO 3.1.2 • ¿Cuál es la combinación en el problema de la mochila que maximiza el beneficio? • ¿Cuál es la combinación en el problema del viajante de comercio que minimiza el recorrido entre las ciudades?. Los problemas del apartado b) son los que estudiaremos en este tema, ya que son una generalización de los del apartado a). Los problemas se pueden expresar como: Sea el conjunto X las posibles soluciones a un problema, F(.\) la función de coste de una solución y R¡(x) el conjunto de restricciones del problema.
(Restricciones) Si un elemento, xeX que cumple R¡(x) se denomina solución factible, y si además, verifica Mín F(x) se denomina solución óptima. El esquema de ramificación y poda, (sucesivamente lo denominaremos RyP) es una técnica general para resolver problemas de búsqueda combinatoria de soluciones.
10
En inglés la palabra original es 'backtracking
94
3.1 Introducción
Ramificación y poda
RyP es un esquema de partición en X (espacio soluciones). Éste descompone la búsqueda de la solución del problema original en subconjuntos estrictos de X. Esta descomposición se repite hasta que la búsqueda se limita a conjuntos de un solo elemento o hasta que se pruebe que no existe solución. La descomposición del problema se representa mediante un árbol.
EJEMPLO 3.1.3. Representación del problema de ia mochila.
Figura 17.Backtracking aplicado al algoritmo de la mochila Hasta aquí, la técnica utilizada es vuelta atrás (backtracking). Generamos todas las posibilidades y, nos quedamos con la mejor. Vemos en la Figura 17 un ejemplo de la aplicación de esta técnica. Si nos fijamos observamos unas fechas It que indican si el cálculo efectuado en ese nodo se ha hecho de forma descendente o ascendente, respectivamente. La idea fundamental de ramificación y poda es no expandir todo el árbol de búsqueda de soluciones como en la Figura 17, si no utilizar unas cotas para orientar la exploración en el árbol. Ellas nos ayudarán a resolver eficientemente un problema dado. Vamos a pasar a formalizar nuestro esquema introduciendo una serie de funciones básicas en el tratamiento de problemas. La descomposición de un problema en subproblemas más sencillos viene dado por la función hijos: Sea X un determinado problema se define la función como: hijos:
95
ramification Y poda
3.1 Introdcction
Dado un problema X, genérico, la descomposición de éste arbitraria se representa mediante un árbol T=(N,A) donde N es un conjunto de nodos y A un conjunto de aristas, que se definen como sigue: N es el conjunto de nodos que se definen recursivamente como:
y el conjunto de aristas A del árbol T se define como:
Una vez definido el árbol donde se van a hallar las soluciones del problema original, hay que definir una función que nos permita medir el beneficio de un nodo en particular. Como se trata de un problema de optimización definimos una función que actúa sobre una problema X dado, por lo que, vamos a extenderla para el conjunto de nodos del árbol queda de la siguiente forma
EJEMPLO 3.1.4.
Vamos a observar un ejemplo donde se define un árbol T(N,A) junto a las funciones Ff-j
Figura 1 8. Árbol de estados
Como la descomposición se realiza desde la raíz, conocer f(Z) para ZeN, es tanto como resolver el problema (Figura 18). Además si consideramos que |ZI=7 entonces donde Z={X}.
96
3.1 Introducción
Ramificación y poda
El árbol T(N,A) asociado a X se conoce como e! árbol de estados asociado al problema X (Figura 18). Sabemos que si conocemos el valor de/fZ) VZeN es tanto como resolver el problema de RyP. Se introduce una nueva función cota inferior o coste estimado de f(-) que denotamos por: y verifica: 1. g(-) es no decreciente en T
si VZehijos(Y) entonces
Como hemos comentado anteriormente la estrategia de RyP consiste en recorrer el árbol de estados de forma selectiva ayudándose de la función coste estimado hasta encontrar la solución óptima.
EJEMPLO 3.5.
Podríamos definir dos funciones F(-) y g(-) para el problema de la mochila11.
la expresión "i:x¡=l" significa que se consideran todos los elementos que tienen en el vector x un /, es decir, que se han escogido.
la expresión
significa que se consideran todos los elementos que tienen en el vector - un / ó un *, es decir, que se han escogido o los que todavía no se han examinado.
Exploración En la exploración, o recorrido de los nodos del árbol de estados se introducen los conceptos siguientes: Nodo vivo:
Es un nodo del árbol del cual no se han generado todos sus hijos.
Nodo muerto: Es un nodo del cual no se van a generar sus hijos, porque... a) Se han generado todos sus hijos posibles, por lo tanto, estamos en un nodo hoja. b) Se ha demostrado que ningún hijo conduce a una solución factible. c) Se ha demostrado que pudiendo conducir a una solución factible, ésta no es la óptima. En el esquema de RyP los nodos vivos se mantienen en un conjunto de nodos vivos, por ello existen varias estrategias para decidir que nodo o subproblema será el próximo en explorar.
I I Las fórmulas tienen un signo negativo porque el algoritmo RyP lo hemos definido para problemas de minimización y el problema de la mochila es de maximización, por lo que, Mín(x) = - Máx(x).
97
3.1 Introducción
Ramificación y poda
Estrategias ciegas: a) Utilizando una exploración tipo FIFO (Cola), es una exploración en anchura y se recorrerá el árbol de estados por niveles, desde la raíz a las hojas. b) Utilizando una exploración tipo LIFO (Pila), es una exploración en profundidad y se recorre una rama desde el origen a una hoja y, poco a poco se va expandiendo los nodos vecinos a los ya explorados terminando por recorrer el árbol completo. Estrategias inteligentes: Estrategias de coste estimado mínimo o de primero el mejor. La función cota inferior, $(•), se suele utilizar para escoger el próximo nodo para expandir. Estrategias mixtas: Como su propio nombre indica es una combinación de las estrategias anteriores. Se suelen emplear las primeras para encontrar una solución rápida (estrategias ciegas) para luego continuar con una estrategia inteligente y encontrar la solución óptima.
Estrategias || Ciegas
Ventajas •
Inteligentes •
Mixtas
• •
Rapidez de cálculo.
• •
Orientan hacia la solución óptima.
• •
Orientan hacia la solución óptima. • Podan nodos en etapas tempranas del esquema.
Bibliografía: [HS.78]
Capítulo 8 (The method).
[Mi,86J
Capítulo 7 (Tree-Search methods).
[BB,90j
Capítulo 6 (Brach & bound).
<[BB,97]
98
Capítulo 9.
Inconvenientes No orientan a la solución óptima. Tardan mucho tiempo en encontrar la solución óptima. Cálculos complejos. Posibilidad de agotar la memoria con el conjunto de nodos vivos. Mayor complejidad en la estrategia que las dos anteriores.
3.2 Esquema básico de resolución de problemas
Planteamieto: Se mostrará un algoritmo capaz de resolver problemas de ramificación y poda. Se verá su funcionamiento mediante ejemplos y se demostrará su corrección para cualquier problema. Se remarcará el funcionamiento del esquema básico para que en la unidad postenor tratemos de retinarlo y mejoremos su comportamiento.
Objetivos: Que el alumno conozca el funcionamiento del esquema básico de resolución de problemas de ramificación y poda. Que el alumno identifique las funciones básicas y su interrelación. Que el alumno comprenda el correcto funcionamiento del algoritmo.
99
Ramificación y poda
3.2 Esquema básico de resolución de problemas
Para comenzar esta sección vamos a definir el siguiente esquema para la resolución de problemas de RyP. Ésta será la primera versión, explicaremos su funcionamiento y se le aplicarán posteriores refinamientos con en fin de aumentar su eficiencia. Sea /V un tipo de nodo del árbol de estados derivado de un problema dado. Sea CN un tipo conjunto de nodos del árbol de estados de un problema. ' Sea p tipo de resultado que devuelve nuestro algoritmo. Función RyP(x:N) :p
var Cn\\C'nh:CNsolución: p Cn v={x} // iniciación mientras —final(Cnv) //regla de terminación //regla deselección sel=seleccionar(Cnv) Cnh-hij()s(sc¡) //regla de ramificación //regla de poda Cnv=podar(horrur(Cnv,sel) u Cnh) fin mientras solución = obtenerSoiución(Cnv) fin función Se definirá a continuación cada función que compone el esquema, así como, los parámetros y resultados que devuelve: 1.- Función final: Esta función indica si se ha llegado al final de nuestro algoritmo. Entrada: C/v un conjunto de nodos del árbol de estados. Salida: 73 un booleano ¡verdadero, falsoj según se haya llegado o no a! final de nuestro recorrido.
2.- Función seleccionar: Esta función es la encargada de escoger el próximo nodo para examinar, como ya comentamos en la sección anterior en el puntos de exploración, existen diversas formas de selección. Entrada: CN un conjunto de nodos del árbol de estados. Salida: N un nodo del árbol de estados.
\selecciona seleccionar (No se pueden seleccionar hojas del árbol ya que no podrían generar hijos) 3.- Función hijos: Se encarga de devolver todos los problemas del árbol de estados derivados directamente del actual que se le pasa como parámetro. Entrada: /V un nodo del árbol de estados. Salida: C,v un conjunto de nodos del árbol de estados.
i oo
3.2 Esquema básico de resolución de problemas
Ramificación y poda
4.- Función podar: Esta función se encarga de eliminar nodos que no van a conducir a la solución óptima. Entrada: C,v un conjunto de nodos del árbol de estados. Salida: C/v un conjunto de nodos del árbol de estados.
5.- Función otenerSolución: Esta función simplemente devuelve la solución a partir do un nodo hoja. Entrada: C/v un conjunto de nodos del árbol de estados. Salida: p solución asociada a un nodo hoja del problema. obtenerSolución fincd(x)
—> obtenerSolucion(x) = a donde
Después de haber enunciado las funciones básicas del esquema RyP debemos demostrar que el algoritmo termina en un número finito de pasos bajo problemas reales. Teorema 3.1.1. Sea un problema X, si se verifican las siguientes condiciones:
1 .- El tamaño del problema es inferior a infinito. 2.- Al menos existe una hoja en el árbol de
estados.
entonces RyP(A^) termina en un número finito de pasos Demostración: (estricto), aplicando esta regla recursivamente sobre Como los hijos es evidente que X se irá descomponiendo en conjuntos cada vez más pequeños hasta que su tamaño sea 1. Por otra parte un nodo seleccionado se elimina y sus hijos son añadidos a "Cnv". En el peor de los casos el "Cnv" solo contendrá conjuntos de un solo elemento (como hemos comentado en el párrafo anterior) que no podemos seleccionar por ser hojas. Pero como la función podar elimina todas las hojas menos una (ya que no puede eliminar la solución óptima), llegará un momento en que se cumplirá la función "final" y, el algoritmo finalizará. Ahora ya hemos demostrado que nuestro algoritmo encontrará la solución óptima si el problema es finito. Queda por demostrar que la solución óptima se conserva de iteración a iteración. Para ello definimos los siguiente términos. Sea X el problema original y Cm>, el contenido de la variable Cnv al finalizar la iteración /, siendo evidente que en nuestro esquema RyP Cnv(¡={X}.
luí
Ramificación y poda
3.2 Esquema básico de resolución de problemas
Teorema 1.1.2. Si el algoritmo RyP termina en la iteración /, entonces se cumple que
Demostración: Antes de comenzar la demostración definamos las siguientes igualdades:
Se ha demostrado que nuestro esquema termina en un número de pasos finito, que la solución óptima se conserva de iteración a iteración de nuestro algoritmo. Entonces una consecuencia directa del teorema anterior es que al final de cada iteración la solución óptima que se busca al principio desde el problema original está en el Cnv (Conjunto de Nodos Vivos), Corolario 1.1.1.
Cuando finaliza cada iteración tenemos que se cumple la anterior igualdad. Demostración: Sea X es problema original claramente Cnv,, = /Xj conserva la solución óptima de la anterior.
y por el Teorema 1.1.2. cada iteración
Lo único que nos queda para finalizar es demostrar que nuestro algoritmo devuelve la solución correcta requerida.
102
3.2 Esquema básico de resolución de problemas
Ramificación y poda
Corolario 1.1.2.
Si RyP termina, entonces RyP(X) devuelve la solución óptima. Demostración: Supongamos que nuestro esquema RyP termina en la iteración "t" y sea su respuesta esto quiere decir que la variable Recordando la definición def y por el corolario 1.1.1.
Ahora podemos afirmar que nuestro esquema RyP devuelve la solución correcta si resuelve un problema finito y con al menos una solución (factible o no factible).
Bibliografía: • [HS.78]
Capítulo 8.
• [Mi,86]
Capítulo 7.
• [BB.90]
Capítulo 6 (Branch & Bound).
• [BB.97]
Capítulo 9.
103
This page intentionally left blank
3.3 Refinamientos sobre ei esquema básico
Planteamiento: Vamos a considerar mejoras sobre e! esquema propuesto en la unidad anterior que es el esquema básico. Para ello haremos dos observaciones y, de ellas se obtendrán los dos nuevos esquemas, el RyP1(12) y el RyP2(13). Estas mejoras nos reducirán el coste temporal y espacial del algoritmo que resuelve nuestro problema.
Objetivos: •
Que el alumno conozca nuevos refinamientos sobre el esquema básico de ramificación y poda.
•
Que el alumno entienda la utilidad de los nuevos refinamientos.
12 Nombre reducido del primer refinamiento, que consiste en mantener el mejor resultado actual fuera de la lista de nodos vivos. 11 Nombre reducido del segundo refinamiento, que establece una función cota pesimista que permite definir nuevas reglas de poda.
105
Ramificación y poda
3.3.1
3.3 Refinamientos sobre e! esquema básico
Primer refinamiento
En este punto vamos a profundizar en el funcionamiento del algoritmo básico descrito en el apartado anterior, suponemos que solamente disponemos de la función cota inferior g(-) para orientar al algoritmo hacia la solución correcta. Como nuestro objetivo es encontrar la solución óptima. Si hubiera varias soluciones óptimas nuestro algoritmo encontraría una de ellas. El primer refinamiento sobre el apartado 3.2 Esquema básico de resolución de problemas, consiste en extraer del conjunto de nodos vivos, Cnv, todas las hojas. Estamos buscando una solución óptima, ésta la contendrá una hoja, por lo que demostraremos que podemos desechar el resto de hojas por no aportar información adiciona!. Supongamos que en la variable Cnv existen dos nodos distintos que son hojas:
como entonces A-> no tiene sentido que esté en la lista Cm1, ya que no es solución óptima y se podrá podar. Entonces se deberá utilizar una variable que la llamaremos mejor para almacenar la mejor solución en curso. De forma que el nuevo algoritmo mantendrá en memoria e! conjunto de nodos vivos que no contendrá hojas.
En un principio la solución tendrá un valor mejor=ü tal que variable mejor se actualizará con las hojas que ofrezcan una solución inferior.
106
luego dicha
3.3 Refinamientos sobre el esquema básico
Ramificación y poda
función RyPl(X:N): p var sel, mejor,aux : N Cnv : CN fin var Cnv mejor
//tal que
mientras sel - seleccionar(Cnv) Cnv - borrar(Cnv, sel)
// Regla de terminación // Regla de selección
para todo aux E hijos(sel) si \aux\ - 1 entonces //aux es hoja si/(aux) < /(mejor) entonces mejor ~ aux //Actualiza nodo Cnv = podar(Cnv, mejor) //regla de poda
fin si
si no
//aux no es hoja. Examinar si g( aux )
fin si fin para todo fin mientras
devuelve obtenerElemento(mejor) fin función
// x : mejor = ¡x}
Una función importante que se ha utilizado en el algoritmo RyPI es podar(-) y la vamos a definir a continuación.
función podar (Cnv:C^, mejor:N) var A : N; fin var para todo A e Cnv si g(A) >/(mejor) entonces Cnv=borrar(Cnv,A) fin si fin paratodo devuelve Cnv fin función
107
3.3 Refinamientos sobre el esquema básico
Ramificación y poda
Observamos que en la regla de poda que... podcir(Cnv,mejor) = Cn\> - / VB : B eCtiv A g(B) >/(mejor)/ por lo que se verifica que... VAeCin'AA £ pociarfCnr,mejor) —>/(A) ¿g(A) >/(mejor),
por tanto, estamos eliminando nodos que no pueden ser la solución óptima. Recordamos que g(-) es una función cota inferior como estamos minimizando se le denomina también cota optimista y verifica: Sea un problema X y su árbol de estados asociado T(N,A).
1 g(t) es no decreciente en T. Si ehijos(Y) entonces 2.
3.
Figura 19. Representacion grafica de g(z)< f(z) en el nodoz.
Podemos observar en la Figura 19 como la función g(-) se desplaza de izquierda a derecha en la recta real buscando la solución exacta del nodo.
EJEMPLO 3.3.1.1. Tomando como ejemplo el problema de la mochila discreto y considerando como la función a minimizar...
y como función de cota inferior
Figura 20. Árbol de soluciones aplicando poda.
i 08
3.3 Refinamientos sobre el esquema básico
Ramificación y poda
En la traza correspondiente a la Figura 20, cuando llegamos al nodo ¿=(1.0,1) cuya función f(z)=-6, hacemos corresponder mejor=( 1,0,1). Posteriormente la variable mejor nos permite podar todos los nodos restantes del conjunto de nodos vivos Cnv.
3.3.2
Segundo refinamiento
En este segundo refinamiento vamos a introducir una nueva función. La nueva función u(-) será una cota superior y como nuestro objetivo es minimizar la función se denomina también cota pesimista y, tendrá las siguientes características: Sea un problema X y su árbol de estados asociado T(N,A). 1. u(-) es no creciente en T (decreciente o igual) si \fzehijos(y) entonces u(:,)< u(y) 2. 3.
Figura 21. Representación gráfica de x(z)£.ft;.i¿u(:.) en ei nodo 7.
Podemos observar en la Figura 21 como la función u(z) se desplaza de derecha a izquierda en la recta real buscando la solución exacta del nodo /(-), que estará perfectamente delimitada por las dos cotas, ¡>(z)
109
Ramificación v ooda
3.3 Refinamientos sobre el esauema básico
Ahora estamos en condiciones de transformar el algoritmo RyP1, ya visto, en el alqoritmo RyP2, el cual tiene la siguiente forma:
función RyP2(X:N): p var sel, mejor, aux : N solucionReal: .7? Cnv : CN cotajnejor : .'A1 fin var
//Nodos del árbol de estados //Conjunto de nodos del árboh de estados //Solución del problema
Cnv = fXÍ mejor = ü //tal que f( £2)=°° , Ul * / cotajnejor = u(X) solucionReal - Falso mientras Cnv ¿ 0 //Regla de terminación sel = seleccionar(Cnv) //Regla de selección Cnv = borrar(Cnv, sel) para todo aux e hijos(sel) si \aux\ = 1 entonces //aux es hoja si f(aux) u(aux) entonces //Actualizar mejor solución hasta el momento (ficticia) solucionReal - Falso cotajnejor = u(aux) Cn v - podar(Cn v, cotajnejor, solucionReal) fin si Cnv - insertar(Cnv,aux) fin si fin si fin para todo fin mientras devuelve obtenerElemento(mejor) //x : mejor = {x} fin función
no
3.3 Refinamientos sobre el esquema básico
Ramificación y poda
En este algoritmo la función podar quedaría definida por
función podar (Cnv:CN, cota jnejor :'/(*, solucionReal:.25) var A : N; fin var para todo A e Cnv si g(A) > cotajnejoro (g(A)-cota_mejory solucionReal) entonces Cnv=borrar(Cnv,A) fin si fin paratodo devuelve Cnv fin función Consideraciones sobre el algoritmo RyP2: a) Si u(z) siempre vale °° este algoritmo se transforma en el RyP1. b) Se puede hacer un refinamiento para evitar el cálculo de ios valores de las funciones f(x), gfx) y u(x), guardando sus valores en variables, y ampliando la Cnv para guardar también la g(-) del nodo que estamos considerando, para no tener que calcularlo al podar. c) La cota superior u(x) es difícil de establecer en problemas reales con restricciones. Se puede establecer una tabla resumen comparativa entre los algoritmos RyP1 y RyP2: Algoritmos || RyP1 • RyP2
•
Ventajas Fácil impiementación. Ahorro de memoria.
• • • •
Inconvenientes Consumo de memoria para el conjunto de nodos vivos. Difícil encontrar función u(-) Más cálculos que RyP1 . Impiementación más compleja que RyP1.
111
Ramificación v ooda
3.3.3
3.3 Refinamientos sobre el esquema básico
Solución subóptima
La solución subóptima se plantea como alternativa a la solución óptima. Existen problemas en los que se pueden emplear soluciones aproximadas, o bien, no podemos calcular la solución exacta. Esta situación puede ser debida a que la solución exacta consume un tiempo excesivo o se nos agotan los recursos disponibles. Como indica su nombre esta solución es aproximada y nos puede orientar sobre solución correcta. Lo más importante que se puede señalar es que el error de la solución subóptima se puede acotar. Por muchas iteraciones que realice nuestro algoritmo ia solución no se nos desviará más que una porcentaje de la solución real. Si nos fijamos en el algoritmo RyP se eliminan todos aquellos nodos A tales que, g(A) >/(mejor) con lo que obtendríamos la solución óptima.
Como decíamos anteriormente, hay situaciones en el que este requerimiento se puede relajar y, solo nos interesa una solución que de valores lo suficientemente cercanos a la óptima.
EJEMPLO 3.3.3.1. Supongamos que permitimos una desviación del 70% sobre la solución óptima. Si en un momento determinado f(mejor)=150 entonces podremos eliminar todos los nodos "A " para los que g(A) > (150-0.1*150) = 135, ya que, "g(->" es creciente la solución que se podrá derivar de él no dista en más de un 70% de la que proporcionaría la mejor. Para poder integrar el concepto de solución subóptima en nuestros algoritmos RyP se introduce una función permisiva £:/?->/? y, un g(A) >/(mejor) - e(f(mejor)). Con ello aseguramos que
nodo
A
no será
producido
si
Podemos decir que las funciones más utilizadas son las del tipo £(v) - 8-v donde 8>0 que marcan la proporción sobre el parámetro. Se ha podido demostrar experimentalmente que crecimientos lineales en la función permisiva £ conducen a decrecimientos exponenciales en el número de iteraciones del algoritmo. Pero la complejidad del problema sigue siendo exponencial.
Bibliografía: • [HS,78j
Capítulo 8.
• [M¡,86]
Capítulo 7.
112
3.4 Teoría de juegos
Planteamiento: Vamos a realizar una introducción a un algoritmo básico de inteligencia artificial como es el mini-rnax y un método de poda en la búsqueda de la mejor solución como es la estrategia alfa-beta. Se pretende presentar este algoritmo, ya que está muy relacionado con el de ramificación y poda, visto en ei apartado anterior.
Objetivos: Que el alumno tenga una idea intuitiva del algoritmo mini-max. y del método de poda alfa-beta.
113
3.4 Teoría de juegos
Ramificación y poda
La mayor parte de juegos de estrategia se pueden representar bajo la forma de grafos dirigidos. Cada nodo del grafo se corresponde con una configuración posible del juego y cada arco con una transición legal entre dos configuraciones. Este grafo es infinito para aquellos juegos que no tiene un límite prefijado sobre el número de configuraciones posibles. Supongamos para simplificar que el juego se juega alternadamente entre dos jugadores, y que es simétrico (los dos juzgadores se someten a las mismas reglas) y determinista (el azar no interviene); las ideas presentadas se pueden adaptar sin esfuerzo a contextos más generales. Supongamos también que una partida no puede durar indefinidamente y que ninguna configuración del juego tiene un número infinito de posibles sucesores. En particular, algunos nodos del grafo no tendrán sucesor: son las configuraciones terminales. Este punto pretende dar una visión general sobre esta técnica, por lo que se abordará un ejemplo y se comentará. Este ejemplo será sobre dos jugadores de ajedrez.
La técnica del mini-max El primer paso consiste en definir una función de evaluación estática evcl(-) que asocia un valor a cada configuración. Idealmente, nos gustaría que eval(u) fuese tanto mayor cuanto más favorable sea una configuración del juego u. Es costumbre asignar un valor a las configuraciones en igualdad de fuerzas y un valor tanto más negativo cuanto más desfavorable sea la situación. Esta evaluación debe tener en cuenta distintos factores, tales como el número y la calidad de las piezas de una y otra parte, el control del centro, la libertad de movimientos, etc. Es necesario un compromiso entre lo buena que sea la función y el tiempo que tome calcularla.
EJEMPLO 3.3.1. Disponemos de dos jugadores A y B. La Figura 22 representa una parte del grafo correspondiente a un cierto juego. Los valores asociados a las hojas se obtienen aplicando la función eval(-) a las configuraciones correspondientes; los valores de los otros nodos pueden calcularse según la regla del minimax. Se ha supuesto en este ejemplo que el jugador A busca maximizar la función de evaluación y el B minimizarla. La técnica del minimax tiene una profundidad determinada para no expandir indefinidamente, en este caso es de 3 niveles Si A juega para maximizar su ventaja, escogerá la segunda jugada de entre las tres posibles. Esto le asegura un valor 10 como mínimo.
Figura 22. Árbol completo del minimax con 3 niveles.
114
3.4 Teoría de juegos
Ramificación y poda
Método Alfa-beta Esta técnica de base puede ser mejorada de distintas formas. Por ejemplo, puede ser provechoso explorar más profundamente las jugadas prometedoras. Algunas ramas pueden también ser abandonadas antes de terminar su exploración si la información obtenida es suficiente para garantizar que no pueden, en ningún caso, influenciar el valor de sus ascendientes. Esta segunda mejora es generalmente conocida como el nombre de método alfa-beta. Se conoce también con el nombre de poda alfa-beta. Nos limitaremos con dar un ejemplo simple de este método.
EJEMPLO 1.1.2, Volvamos a la Figura 22. Sea (i,j) el j-ésimo nodo de la i-ésima línea del árbol. Queremos calcular el valor de la raíz (U) a partir de los valores calculados por la función eval(-) para las hojas (4,j), ¡<j
Figura 23. Exploración cié la rama izquierda con poda alfa-beta.
Continuando de esta manera se obtiene después de evaluar el nodo (4,4) la situación ilustrada en la Figura 23. Puesto que el nodo (3,3) vale por lo menos 10 y el nodo (2,1) vale como máximo -3, el valor exacto del nodo (3,3); se dice entonces que las ramas correspondientes del árbol han sido podadas. De igual forma, después de evaluar la hoja (4,11), se obtiene la situación ilustrada en la Figura 24. El nodo (2,3) vale como máximo /. Puesto que ya sabemos que (/,/) vale como mínimo 10, es inútil evaluar los otros hijos del nodo (2,3). Para establecer que la raíz (1,1) vale 10, basta visitar sólo 19 de los 31 nodos que tiene el árbol.
115
3.4 Teoría de juegos
Ramificación y poda
Figura 24, Árbol completo minimux de 3 niveles con poda ulta-heta.
PROBLEMA 1.1.1. ¿Qué modificaciones se tiene que hacer en los principios expuestos en esta sección para tener en cuenta los juegos de estrategia en los que interviene el azar? ¿Y si tuviéremos un juego en el que participan más de dos personas?
PROBLEMA 1.1.2. Escribir un programa capaz de ganar al campeón del mundo de backgammon. (¡Esto ya ha sido hecho!).
Bibliografía: [BB,90]
Capítulo 6 (Introducción a los gratos de juego).
[86,97]
Capítulo 9 (El principio del minimax).
116
3.5 Problemas resueltos
Planteamiento: Esta unidad que contiene problemas resueltos pretende ilustrar la aplicación directa de los esquemas de ramificación y poda vistos en este apartado. Veremos la utilidad de las funciones cota inferior, así como, las propiedades que tiene asociadas. En el contenido, .desarrollaremos varios problemas para detallar las partes que forman la resolución de un problema de ramificación y poda.
Objetivos: •
Que el alumno aplique los métodos vistos en este apartado a problemas prácticos.
•
Que el alumno conozca distintas formas de resolver un mismo problema aplicando técnicas de ramificación y poda —distintas funciones cota inferior—.
•
Que el alumno adquiera destreza en el uso de técnicas de ramificación y poda aplicadas a resolución de problemas combinatorios.
117
Ramificación y poda
3.5.1
3.5 Problemas resueltos
El problema de la mochila discreto 0/1.
Recordamos que en el problema de la mochila discreto 0/1 se pretende maximizar el valor de los elementos que existen cumpliendo la restricción de caber en la mochila. Por ello definimos Dasdlkhsdlfkjhasdflakjhaslkjhasdfjhalsdkjfhlaskjdfaksdjfksajdsdhgasdlfjkhasldfsafasdfa
La función objetivo pretende sumar todos los objetos de una solución dada.
La restricción nos dice que una solución factible es aquella cuya suma de los pesos de sus elementos caben en la mochila.
3.5.1.1
Estructura de datos.
Consideraremos un vector de tamaño N (n9 de elementos de la mochila) para guardar las posibles soluciones a nuestro problema14.
donde
en este caso todas las posibles soluciones se podrían definir como:
3.5.1.2
Función objetivo y restricciones
Función objetivo:
Restricciones:
14 'X' (en mayúscula) representa a todas las posibles soluciones, mientras que Y (en minúscula) representa a una solución.
118
3.5 Problemas resueltos
3.5.1.3
Ramificación y poda
Función hijos(-)
Definiremos primero la estructura de un nodo intermedio, para luego pasar a definir la función hijox(-). Un subconjunto YcX lo representaremos mediante una k-tupla
Sea Vye Y, la función hijos vendrá determinada por
hijos(y) = />•«, v,/ donde
y = (a1, a2,..., ak) y0 =(a1, a2,..., ak,0) y1 =(a1, a2,..., ag,I)
La función coste/{•) será:
Tenemos que comprobar que la función hijos(-) cumple las propiedades:
Es evidente, ya que se llama
3.5.1.4
Cota Optimista. Función g(-)
Ahora necesitaremos encontrar una función g(-) que sea cota inferior de /(•). No existe una solución única.
119
Ramificación y poda
3.5 Problemas resueltos
Una solución trivial sería:
Esta g(-) supone que se pueden incluir todos los objetos que llevamos hasta el momento, más el resto que queda por explorar. Evidentemente, cumple las condiciones de función g(-):
Pero esta cota no está muy ajustada. Ya que no tiene en cuenta el espacio que queda libre en la mochila ni el beneficio del resto de elementos. Otra solución mejor es rellenar con la solución del problema de la mochila continua, en el que se pueden coger trozos del objeto. Podemos escoger la solución del problema de la mochila continuo como una cota optimista del problema de la mochila discreta. El provecho (máximo beneficio) obtenido en el algoritmo de la mochila continúa siempre será mayor o igual al obtenido en la mochila discreto y podremos calcularlo según el siguiente algoritmo. Suponiendo que los objetos están ordenados por \>/p¡, densidad de valor, función
var resto, provecho: fin var
resto = M
si resto < O entonces devuelve °° sino
//Hemos sobrepasado el peso máximo
provecho =
mientras si resto > p¡ entonces provecho - provecho + v¡
//Elemento entero
si no provecho - provecho+(resto / p¡) * v¡ //Parte del elemento fin si resto - resto - p¡
i++ fin mientras devuelve -provecho fin si fin función
120
3.5 Problemas resueltos
Ramificación yjjoda
Ahora tenemos que comprobar que esta función g(-) cumple las tres propiedades de la cota optimista (Las siglas PMC y PMD corresponden al cálculo del resto según el Problema de la Mochila Continuo y Discreto respectivamente).
3) si Iyl = / (Es una hoja)
(inmediato.)
EJEMPLO 3.5.1.4.1 Veamos las ventajas que conlleva definir una u otra función g(-). Vamos a realizar dos trazas del mismo problema para apreciar las diferencias entre ambas g(-) anteriormente expuestas. Función g(-) trivial:
Figura 25. Algoritmo de la mochila con g(-l trivial (9 nodos expandidos hustn encontrar la solución).
15
La solución del problema de la mochila continúa siempre es menor o igual al discreto.
121
Ramificación y poda
3.5 Problemas resueltos
EJEMPLO 3.5.1.4.2 Aplicamos ahora la g(-) mejorada. La solución de! problema de la mochila continua. Teniendo en cuenta que los elementos hay que ordenar según su ratio de provecho v/p¡. Función q(-) Problema de la Mochila Continua:
Figura 26. Algoritmo de lu mochila con $(•) trivial (7 nodos expandidos hasta encontrar la solución)
Podemos comprobar en los dos ejemplos anteriores como la función g(-) se dirige hacia la solución correcta en niveles iniciales del árbol de búsqueda de soluciones, si esta función está ajustada. En el caso de la $(•) trivial (Figura 25) el algoritmo necesitaría expandir 9 nodos, dado que explora ramas que no le conducen a la solución. Mientras que la función g(-) definida como la solución de la mochila continua (Figura 26) consigue encontrar la solución con 7 nodos expandidos, examinando sólo dos nodos hoia.
3.5.1.5
Cota Pesimista. Función u(-)
Una cota pesimista trivial que podríamos proponer sería la siguiente:
Dejamos para el lector que compruebe que cumple las tres propiedades de una cota pesimista. entonces u(z) ^u(y). Función no creciente. 1)
2) 3) Adícionalmente se puede realizar varias optimizaciones como el guardar para no tener que calcularlos cada vez que se llama a la función g(-) o la función u(-).
122
3.5 Problemas resueltos
3.5.2
Ramificación y poda
El Viajante de Comercio
Se conocen las distancias entre un cierto número de ciudades. Un viajante de comercio debe partir de una de ellas, visitar cada ciudad exactamente una vez, y regresar al punto de partida habiendo recorrido en total la menor distancia posible. Supondremos que la distancia entre ciudades nunca es negativa. El caso que nos aborda, los algoritmos exactos tienen un coste exponencial. Se puede representar este problema mediante un grato. Supongamos G=(V,A) un grafo dirigido y ponderado por la función C: A—>7¿ para simplificar la solución supondremos que el grafo es completo (todos los arcos que no están tienen peso °° ).
3.5.2.1
Estructura de datos.
Los posibles caminos, los representaremos por un vector de tamaño solución tendrá la forma:
3.5.2.2
IVI=«. La
Función objetivo y restricciones
Así la función objetivo será el camino que llevarnos recorrido más volver del último nodo al inicial.
Cumpliendo la restricción de no repetirse nodos durante las visitas que se vayan examinando.
Todo el conjunto de soluciones posibles para un problema cualquiera quedará definido por:
Un nodo intermedio del árbol de estados quedará definido por un conjunto de nodos recorridos que no llegará a ser « (todos los nodos) y por supuesto no será solución. Las soluciones únicamente las tendremos en los nodos hojas.
123
Ramificación y poda
3.5.2.3
3.5 Problemas resueltos
Función hijos(-)
La función hijos(-) se definirá como el camino recorrido hasta el momento y todas las posibilidades para ir a las ciudades que sean accesibles desde la actual. Función hijos(-):
Hay que comprobar que se cumplen las propiedades de la función hijos(-): (evidente por la construcción del problema)
3.5.2.4
Cota optimista. Función g(-)
Como ya hemos hecho en el ejercicio anterior vamos a definir dos funciones g(-). Una definición trivial y otra más ajustada al problema. Función Cota Inferior g(-) Solución trivial: sumar los nodos que ya conocernos y desde el actual volver al inicial.
El último término solo se puede añadir si se cumple la desigualdad triangular17. Esta función cumple las condiciones : 1)
Se tiene que cumplir por tener mismo nodo raíz, y cumplir la desigualdad triangular.
(por la desigualdad triangular)
16 17
Sea un grafo G=(N,A)
124
3.5 Problemas resueltos
Ramificación v ooda
2)
Por R.A. supongamos que no es cierto
ademas
de lo que se deduce que
que esta en desacuerdo con la desigualdad triangular, por lo que hemos llegado a una contradicción, luego c.q.d.
3) S¡|;y| = l =>#(y) = / ( y ) Inmediato. No obstante, esta cota no está muy ajustada. Existe una forma de obtener una función g(-) que se ajuste más, basándose en el uso de la matriz reducida. La forma de obtener una matriz reducida es la siguiente: -
El grafo viene dado por la matriz de costes. Una fila/columna está reducida, si y solo si, contiene un cero y los restantes valores son no negativos. Una matriz está reducida, si y solo si, todas las filas y columnas están reducidas.
Sea A la matriz asociada al nodo R del espacio de soluciones. Sea S un hijo de R correspondiente a incluir el arco en el camino.
Figura 27. Cálculos realizados en la matriz A dei nodo padre al hijo Como observamos en la Figura 27, si S no es una hoja, para obtener la matriz reducida asociada se debe realizar 1) Cambiar todos los valores en la fila "í" y en la columna "/' por «>, para impedir utilizar más arcos que salgan de Y o lleguen a "/"'• 2) Poner /I//, /y = «. 3) Reducir filas y columnas excepto aquellas cuyos valores son todo Ahora tenemos que Vyehijos(x), el valor de g(y) será: (Siendo r el coste de la matriz reducida del nuevo nodo).
125
3.5 Problemas resueltos
Ramificación y poda
EJEMPLO 3.5.2.4.1. Aplicaremos la definición de la función g(-) más ajustada y realizaremos una traza. Tenemos una matriz de costes. La reduciremos inicialmente y, seguiremos nodo a nodo, seaún el camino recorrido. Matriz de Costes
Matriz de coste reducido, r = 25 Reducir Matriz Inicial
El coste de r=25 se obtiene de coger los mínimos de las filas (10+2+2+3+4) y de la matriz resultante escoger los mínimos de las columnas (1+3). Con lo que queda
la traza.
Vamos ahora a mostrar las como quedarán las matrices para cada nodo necesario para
(1,2) nodo 2
(1,3 nodo 3
(1,4) nodo 4
(1,5) nodo 5
(1,4,2) nodo 6
(1,4,3) nodo 7
(1,4,2,3) nodo 9
(1,4,2,5) nodo 10
(1,4,5) nodo 8
126
3.5 Problemas resueltos
Ramificación y poda
Si aplicamos al grafo las reglas de ramificación y poda quedaría:
Figura 28. Árbol de estados correspondiente al problema del viajante de comercio (matriz de coste reducida)
En la Figura 28 el índice k perteneciente a las etiquetas ik indican los nodos recorridos (o profundidad en el árbol) y e! número que aparece a su lado en el número de nodo que se ha visitado. Es decir, i2-4 significa que es nuestro segundo nodo visitado y concretamente es e! nodo 4.
Bibliografía: [HS.781
Capítulo 8.
[Mi,86]
Capítulo 7.
127
This page intentionally left blank
3.6 Ejercicios
Planteamiento: Este apartado ofrece enunciados de exámenes que se han realizado de esta asignatura. Por lo que el alumno puede practicar los conocimientos adquiridos en ramificación y poda. Sabiendo que no existe una única forma de resolverlo si no que pueden haber varias.
Objetivos: •
Que el alumno mida su nivel de conocimientos de la asignatura en ramificación y poda.
•
Que el alumno se familiarice con la notación y la manera de resolver ejercicios realizándolos el mismo.
129
3.6 Ejercicios
Ramificación y poda
3.6.1
Dónde llenar el depósito de gasolina.
Queremos realizar un viaje con nuestro coche desde una ciudad origen a otra destino. Tenemos un mapa de carreteras donde están señaladas todas las gasolineras y, por lo tanto, sabemos las distancias entre ellas. Llenamos el depósito de gasolina que nos permite recorrer K kilómetros (a la velocidad habitual de nuestra marcha). Para ganar tiempo queremos realizar el número mínimo de paradas para repostar combustible. Ejemplo: K=300 kms de autonomía con el depósito lleno.
Ejemplo: Sea la matriz correspondientes al gráfico anterior G=(N,A).
(i)
(2) (3) (4) (5) (6) (7)
(1)
(2) 200
200 250 350
150
-
200 310
(3) 250 150 200
(4) 350 200
(5)
(6)
(7)
200 -
310 160
-
-
160 100
200
150
100 200 150 ~
Se pide: a) b) c)
130
Que se plantee la solución para un problema genérico mediante RyP (solución, función objetivo y restricciones, nodos intermedios y función hijos). Que se defina una función cota inferior, lo más ajustada posible al problema. Que se realice una traza del problema con K=300 kims: • Árbol de nodos intermedios con la cota inferior correspondiente. • Etiquetar el orden de recorrido del árbol. • Identificar las podas en el árbol. • Lista de nodos vivos en cada iteración.
3.6 Ejercicios
3.6.2
Ramificación y poda
Reservas de laboratorio
Estamos al comienzo de curso y los alumnos quieren reservar un turno de laboratorio. Para solucionar este problema se propone a los alumnos que elijan varios turnos a los que desearían asistir según su orden de preferencia. El número máximo de alumnos es N y el de turnos es T. Existe una restricción adicional y es que en cada turno solamente caben 7, alumnos. Las máximas prioridades están a la izquierda de la tabla. Alumnos
Al A2 A3 A4
T2 T2 TI Ti
Elección Tí TI T2 T3
Turno
Max. Alumnos
TI
2 / 1
T:
T3 TJ T2
T3
Se quiere encontrar una solución para satisfacer al número máximo de alumnos, según su orden de preferencia. Se pide: a)
Que se plantee la solución para un problema genérico mediante RyP (solución, función objetivo y restricciones, nodos intermedios y función hijos). Que se defina una función cota inferior y otra superior lo más ajustadas posible al problema. Que se realice una traza para el problema del enunciado: • Árbol de nodos intermedios con la cota inferior correspondiente. • Etiquetar el orden de recorrido del árbol. • Identificar las podas en el árbol. • Lista de nodos vivos en cada iteración.
b) c)
3.6.3
Puzzle
Queremos resolver un puzzle de tamaño /Vx/V en el menor número de movimientos posibles. Nos dan una matriz que está desordenada y tenemos que realizar los movimientos correspondientes para que esta matriz tenga la solución correcta del puzzle. En la matriz siempre tenemos una casilla en blanco para desplazar un movimiento las celdas adyacentes (movimientos permitidos). El puzzle siempre tiene solución. Ejemplo Del Problema Matrices
3x3
1
2
3
1
4
6- —»•
4
7
5
8
7
Movimiento 1
2 t 5
3
1
2
3
1
2
3
6
4
5
6
4
5
6
8
7
-8
7
8
Movimiento 2
•4
Movimiento 3
¡ Solución !
Se pide: a) b) c)
Que se plantee la solución para un problema genérico mediante RyP (solución, función objetivo y restricciones, nodos intermedios y función hijos). Que se defina una función cota inferior, lo más ajustada posible al problema. Que se realice una traza del problema con:
1 7 • • • •
2
3
4
5
3
6
Árbol de nodos intermedios con la cota inferior correspondiente. Etiquetar el orden de recorrido del árbol. Identificar las podas en el árbol. Lista de nodos vivos en cada iteración.
131
3.6 Ejercicios
Ramificación y poda
3.6.4
Construcción de edificios
Un constructor tiene que terminar 3 edificaciones pero los promotores de ellas, le proponen darle bonificaciones si las termina antes de final de año. También el propio promotor sabe que si las quiere terminar tendrá también gastos adicionales. Sep 12 IU 10
Edl. Ed2. Ed3.
Bonificaciones Oct Nov 10 11 .5 10 X 15
Dic 7 7 3
Edl. Ed2. Ed3.
Sep 8 5 11
Gastos Adicionales Oct Nov 3 4 A' / 5 5
Dic 4 2 2
El constructor no va a terminar antes de estos meses y, si lo hace después, no obtendrá bonificaciones ni gastos adicionales. Por ello quiere maximizar su beneficio y quiere saber el orden en que tiene que terminar sus edificios y el beneficio que obtendría, sabiendo que en cada mes solamente podrá terminar un edificio como máximo. Se pide: a)
b) c)
3.6.5
Que se plantee la solución para un problema genérico mediante RyP (solución, función objetivo y restricciones, nodos intermedios y función hijos). Que se defina una función cota inferior y oirá cota superior, lo más ajustada posible al problema. Que se realice una traza del problema con el ejemplo del enunciado: • Árbol de nodos intermedios con la cota inferior correspondiente. • Etiquetar el orden de recorrido del árbol. • Identificar las podas en el árbol. • Lista de nodos vivos en cada iteración.
Cena de empresa
Vamos a organizar una cena de empresa, para ello hay que distribuir a I invitados en M mesas de C comensales cada una (Sabemos que I-M*C). Se dispone de una tabla simétrica de afinidades que contiene valores de O a 5 según su grado (O indica aversión total y 5 simpatía). Se pretende diseñar un algoritmo de ramificación y poda que calcule la distribución de invitados por mesa que optimiza e! bienestar general. Ese bienestar se calcula sumando las afinidades de los comensales sentados en posiciones adyacentes. Ejemplo: 1=6 invitados, M=2 mesas de C-3 comensales.
Se pide:
a)
b) c)
132
Que se plantee la solución para un problema genérico mediante RyP (solución, función objetivo y restricciones, nodos intermedios y función hijos). Que se defina dos funciones, una cota inferior y otra cota superior, lo más ajustadas posible al problema. Que se realice una traza del problema con: • Árbol de nodos intermedios. • Etiquetar el orden de recorrido del árbol. • Identificar las podas en el árbol. • Lista de nodos vivos en cada iteración.
Ramificación y poda
3.6 Ejercicios
3.6.6
Viaje en autobuses
Tenemos que organizar un viaje para un ns determinado de personas. Para lo cual contrataremos diversos autobuses que realizarán el trayecto del viaje sabiendo que este número está limitado. Hemos de decidir cuantos autobuses alquilar y de que tipo, ya que existen de diferente número de plazas. El objetivo es minimizar el precio global del viaje. Sabemos que el número de personas es P y el de tipo de autobuses es T, Ejemplo: Tipo de autobús 0 1 2 •' -
\ l'lazas máximas !(> 15 50 60
Disponibles j 2 / 2
Coste 10.000 ¡ítem. U.SOOpttix. 40.000 ptas. 54.000 imis.
Se pide: a) b)
c)
Que se plantee la solución para un problema genérico mediante RyP (solución, función objetivo y restricciones, nodos intermedios y función hijos). Que se defina la función cota inferior, lo más ajustada posible al problema. Que se realice una traza del problema con P=65 (Personas): • Árbol de nodos intermedios con la cota inferior correspondiente. • Etiquetar el orden de recorrido del árbol. • Identificar las podas en el árbol. • Lista de nodos vivos en cada iteración.
133
This page intentionally left blank
3.7 Soluciones
Planteamiento: Ofrecer al menos una solución del ejercicio enunciado en el apartado anterior para que sirva de referencia. Insistiendo en que un ejercicio puede resolverse correctamente de diferentes formas.
Objetivos: Que el alumno comprueba su nivel de destreza en al resolución de ejercicios relacionados con la ramificación y poda.
135
Ramificación y poda
3.7 Soluciones
3.6.1 Dónde llenar el depósito de gasolina. a) Que se plantee la solución para un problema genérico mediante RyP (solución, función objetivo y restricciones, nodos intermedios y función hijos). Sea G=(N,A) el grafo del conexiones que describe la red con AfeNodos y /^Aristas. Estructura de datos: ;j=Autonomía en Kms. gasolineras recorridas paradas en gasolineras Función objetivo:
Función hijos:
b) Que se defína una función cota inferior, lo más ajustada posible al problema. Supongamos que tenemos una matriz de distancias mínimas entre los nodos (Algoritmo de Kruscal) que se calcula en tiempo de preproceso con un coste O(n3) entonces podemos definir nuestra cota inferior como:
Sumamos las paradas realizadas hasta el momento / ,y calculamos en el mejor de los casos, cuantas paradas necesitaríamos para llegar el final. La función f-l calcula el entero superior al parámetro, si éste tiene decimales (Ejemplo: f3~l=3, [3.71=4, Fo.ll=1).
136
Ramificación y poda
3.7 Soluciones
c) Que se realice una traza del problema con K=300 kms. Distancias
{') (2) (3) (4) (5) (6) (7)
(1) (2) 200 200 . 250 150 350 . 200 310 -
(3) (4) (5) 250 350 150 200 200 200 _ . 160 . 100 200
Distancias mínimas
(6) (7) 310 160 - ¡00 - 200 150 150 -
(1) (2) (3) (4) (5) (6) (7)
(1) (2) 200 200 250 150 350 350 400 200 410 310 550 400
(3) (4) (5) (6) (7) 250 350 400 410 550 150 350 200 310 400 200 350 160 300 200 - 300 250 100 350 300 . 350 200 160 250 350 . 150 300 ¡00 200 150
Conjunto de nodos vivos con sus correspondientes iteraciones: Cnv0=(U Cn\'!=¡2.3l Cnv-,=¡i,4,5¡ Cnv,=¡4.5,6,7 ¡ Solución F(8)=2, y poda el resto de nodos pendientes.
137
Ramificación y poda
3.7 Soluciones
3.6.2 Reservas de laboratorio a) Que se plantee la solución para un problema genérico mediante RyP (solución, función objetivo y restricciones, nodos intermedios y función hijos). Estructura de datos:
Alumnos
Turnos correspondientes a los alumnos
Función objetivo: Debemos minimizar el coste total de desplazar un alumno según sus preferencias. El peso correspondiente al desplazamiento lo dejamos que lo calcule la función Coste(-). Como restricción tenemos que los alumnos de un turno no deben superar el máximo establecido por ese turno.
Función hijos:
b) Que se defina una función cota inferior y otra superior lo más ajustadas posible al problema. Cota inferior g(-):
Cota superior u(-):
138
3.7 Soluciones
Ramificación y poda
c) Que se realice una traza del problema con K=300 kms. Elección
Alumnos
Al A2 A3 A4 "Coste
TI
T3 TI T2 T3
T3 T3 T2
O
i
2
T2 T2 \
Ti
Turno TI T2 T3
Max. Alumnos 2 1 1
Conjunto de nodos vivos con sus correspondientes iteraciones:
Solución F(ll)=l, y poda e! resto de nodos pendientes.
IK
La elección de pesos se ha realizado arbitrariamente. Podría elegirse otros distintos para deshacer empates. 139
Ramificación y poda
3.7 Soluciones
3.6.3 Puzzle a) Que se plantee la solución para un problema genérico mediante RyP (solución, función objetivo y restricciones, nodos intermedios y función hijos). Estructura de datos: situación del cuadro en blanco Matriz actual Lista de matrices desde el comienzo Función objetivo: Debemos minimizar la longitud de la lista que nos lleve a la solución. La matriz actual debe ser la solución. En la lista L no habrán matrices repetidas
Función hijos:
b) Que se defina una función cota inferior lo más ajustada posible al problema. Cota inferior g(-): Los movimientos necesarios serán, al menos, todas las casillas que no estén en su lugar (el cuadro blanco actúa como comodín) más el ns de movimientos realizados.
140
3.7 Soluciones
Ramificación y poda
c) Que se realice una traza del problema con.
1 2 3 4 5 7 8 6 Conjunto de nodos vivos con sus correspondientes iteraciones:
Solución F(8)=3, y poda el resto de nodos pendientes.
141
Ramificación v poda
3.7 Soluciones
3.6.4 Construcción de edificios a) Que se plantee la solución para un problema genérico mediante RyP (solución, función objetivo y restricciones, nodos intermedios y función hijos). Antes de comenzar podríamos calcular una nueva tabla Beneficio como la diferencia entre Bonificaciones-Gastos. Bencficio(i,j)=Bonificacione.\(i,j)-Gasto.i(iJ) Beneficio
Edi.
Ed2. Ed3. Ninguno
Sep 4 5 -/ 0
Oct 7 -3 3 0
M,v 7 9 10 0
Dic .? 5 / 0
Estructura de datos: MsMeses. jVsNúmero de edificios [No}=No se asigna edificio Función objetivo:
Cambiamos el signo de F(X) para que se convierta en un problema de minimización.
Función hijos:
Seleccionamos todos los edificios no terminados
b) Que se deñna una función cota inferior, lo más ajustada posible al problema. Función g(-) cota inferior: La g(-) calculará las decisiones que hemos tomado hasta el momento y el máximo de los próximos meses.
i 142
3.7 Soluciones
Ramificación y poda
Función u(-) cota superior: De igual forma podríamos calcular u(Y) como:
como hay siempre una fila con valor O de beneficio (es la posibilidad de no construir es edificio), la fórmula anterior se transforma en:
c) Que se realice una traza con el problema del enunciado. Conjunto de nodos vivos con sus correspondientes iteraciones:
Solución F(I2)=22, y poda el resto de nodos pendientes.
143
3.7 Soluciones
Ramificación y poda
3.6.5 Cena de empresa a) Que se plantee la solución para un problema genérico mediante RyP (solución, función objetivo y restricciones, nodos intermedios y función hijos). Estructura de datos: C & n9 de comensales en una mesa M & n3 de mesas Se supone que el n2 de invitados es ¡=M*C, es decir que los invitados caben justos con las
mesas.
Función objetivo: Utilizaremos la función moil como módulo (resto de la división entera)
Podemos plantear es problema como la minimización de la simpatía entre los invitados. Si dos elementos son iguales es porque son el mismo elemento. Función hijos:
/ = Invitados por colocar Y= Invitados sentados
b) Que se defina una función cota inferior y otra superior lo más ajustadas posible al problema. Cota inferior g(-): La función g(-) sumará todas las afinidades de los invitados sentados y agregará el máximo del resto de los invitados que quedan por sentar. Todo ello cambiado de signo.
144
3.7 Soluciones
Ramificación y poda
Cota superior u(-): La función «(•; será equivalente a la anterior pero, sumará todas las afinidades de los invitados sentados y agregará el mínimo del resto de los invitados que quedan por sentar.
c) Que se realice una traza del problema con el ejemplo. Conjunto de nodos vivos con sus correspondientes iteraciones:
Solución F<22)= -30, y poda el resto de nodos pendientes.
145
Ramificación y poda
3.7 Soiuciones
3.6.6 Viaje en autobuses a) Que se plantee la solución para un problema genérico mediante RyP (solución, función objetivo y restricciones, nodos intermedios y función hijos). Estructura de datos:
P= personas que quedan por transportar numero de autobuses de un tipo
Función objetivo:
Función hijos: Los nodos intermedios Y serán aquellos que no transporten al total de personas requerido.
b) Que se defina una función cota inferior, lo más ajustada posible al problema. Supongamos que tenemos los tipos de autobuses ordenados por e! cociente Coste/(Plazas máximas):
Sumamos el coste de los autobuses contratados hasta el momento y luego lo mejor que no puede pasar sería que cupieran en los autobuses más baratos y con la capacidad justa. También podríamos mejorar la cota si comprobamos con los autobuses disponibles cuantas de la p personas podemos transportar el resto lo haríamos con el siguiente cosíePersona mínimo.
146
3.7 Soluciones
Ramificación y poda
c) Que se realice una traza del problema con P=65 personas.
Tipo de autobús
0 1 2 3
Plazas máximas
10 15 51) 60
Disponibles
3 2 / 2
Coste 10.000 fitas. 13. 500 pías. 40.000 ¡ñus. 54.000 pías.
Coste/Persona 1000
Orden
9ÜO $00 WO
4 3 1 2
Conjunto de nodos vivos con sus correspondientes iteraciones:
Solución F(8)=53500 y poda el resto de nodos pendientes.
147
This page intentionally left blank
Referencias Bibliografía básica [HS.78]
[BB.97]
Ellis Horowitz & Sarta] Sahni. "Fundamentáis of Computer Algorithms" Computer Science Press (1978)
Giles Brassard & Paul Bratley. "Fundamentos de Algoritmia" Prentice Hall (1997).
Bibliografía complementaria [Sa,81]
Sartaj Sanhi "Concepts in discrete mathematics" The Camelot Publishig Company
[Mi,86]
M. Minoux. "Mathematical Programming Theory and Algorithms" John Wiley and Sons
[Sn,92]
Moshe Sniedovich. "Dynamic Programming" Board
[BB.90]
Giles Brassard & Paul Bratley "Algorítmica. Concepción y análisis" Masson, S.A.
149
This page intentionally left blank
índice analítico A algoritmia, 4. 5 algoritmo, 1,4.5.6, 1 1 , 13, 14, 16, 17, 18,21,22, 23, 28, 30, 33, 43, 49. 50, 56, 59, 63, 64. 65, 71, 75, 76, 77, 79, 82, 84, 87, 89, 94, 97, 99, 100, 101. 103, 105. 106. 109. 110, 1 1 1 , 113, 123, 125, 126, 135 divide y vencerás, 3 heurístico. 4
inicio, 26, 27. 33, 34, 40, 41, 42, 46, 47, 48. 50, 53,58,69.73.76,78,81,83,85
I iterativo, 14. 20, 22. 37. 39, 41, 43. 48, 49, 50, 55, 56. 58, 59, 77, 79
M minimal, 31,32, 33.39. 47, 54
iterativo, 11 optimización, 1 1 recursivo, 1 1 voraz, 3 vuelta atrás. 3
N noetheriano, 31, 32, 33. 39, 46. 47. 54, 55 notación. 6, 9
C complejidad. 3, 95 espacial, 5, 22 temporal, 3, 4, I I , 13, 14, 16, 18,21,37.39,43. 49, 50, 55, 56, 1 1 1 temporales. 59 conclusión, 22 conjunto, 4. 6, 7, 8, 16. 17, 18, 25. 26, 27, 28. 29, 30, 31, 32, 33, 39, 40, 41. 45. 53. 54, 55, 70, 76, 85, 91,92,93,94,95.99. 100, 105. 108, 110, 1 2 1 , 126
D divide y vencerás. 5, 13. 16, 17
E espacio. 123 decisión. 25, 33 memoria, 4, 39 problema, 25. 30, 33, 35 solución. 25, 92. 128 Esquemas Algorítmicos. 3
F fórmula, 13.29,49.56. 146 funciones programación dinámica iterativa ps, 40, 41, 42, 48, 55, 59, 71. 74. 77, 79, 82, 83, 86 ss, 40, 41, 42. 48, 55, 59, 71, 74, 77, 79, 82, 83, 86 funciones programación dinámica recursiva cálculo, 6, 26. 27, 33, 34, 40, 41, 46, 47, 48, 49. 50. 53, 58, 69, 73, 76, 78, 81, 83. 85 combinar, 26. 27, 33, 34, 40, 41. 46. 47, 48, 50, 54,58,69,73,76.78,81.83,85 contorno, 26. 27, 33, 34, 40, 41, 42, 46, 47, 48. 50, 53,58,69,73.76.78.81,83,85 descomposición, 25. 26, 27, 33, 34, 35, 40. 41, 46, 47, 48, 50, 54. 58. 69, 73, 76. 78. 81, 83, 85
O optimi/.ación. I 1, 89, 91, 93
P paradigma, 5 funcional. 5 imperativo. 5 lógico. 5 PDI, 40, 41, 42, 48. 49, 50, 55, 56, 58, 59. 63. 64, 65, 71. 72. 74. 75. 77, 79. 80. 81. 82. 83, 84. 86. 87 PDR, 26. 27. 33, 34. 40. 41. 42. 46, 47, 49. 50. 54. 55, 56, 58, 59, 63. 64, 65, 69, 70. 71. 73. 74, 75, 76, 77, 78, 79. 81, 82. 83. 84, 85, 86, 87 programación dinámica, 5. I I , 13. 18, 22. 23, 25, 26, 27, 32, 35, 36, 37, 39, 43, 61. 65, 67 Programación Metódica, 1, 3, 5 Programación Orientada a Objetos, 5
R ramificación y poda, 5, 89, 91. 92. 97. 103, 119, 130, 131, 135, 137 recursivo, 13. 14, 17, 18, 21, 22, 23, 25, 26. 27, 32. 33. 37. 39, 41. 43. 46, 49, 50, 53, 54, 55, 56. 58. 59, 76 relación de orden estricto, 30, 33 RyP, 91,92. 94, 99. 100, 101. 102, 1 1 1 , 133, 134. 135, 136, 139, 141. 143. 145. 147. 149
S subproblema, 13, 18, 20, 25. 26. 37, 39, 40, 92, 94
V vuelta atrás, 5, 91. 92
151