Planificación De Máximo Beneficio-Analisis De Algoritmo

1. Programación Dinámica

1ª Etapa: Caracterizar la estructura de una solución óptima

2ª etapa: Definir recursivamente el valor de una solución óptima

3ª etapa: Calcular el valor de una solución óptima

4ª etapa: Construir una solución óptima

2. Algoritmo Voraz

3. Conclusiones y Aspectos a mejorar: Programación Dinámica vs. Algoritmo Voraz

1. Programación Dinámica

La programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de sub-problemas y subestructuras óptimas.

Una subestructura óptima significa que soluciones óptimas de sub-problemas pueden ser usadas para encontrar las soluciones óptimas del problema en su conjunto. Por ejemplo, el camino más corto entre dos vértices de un grafo se puede encontrar calculando primero el camino más corto al objetivo desde todos los vértices adyacentes al de partida, y después usando estas soluciones para elegir el mejor camino de todos ellos. En general, se pueden resolver problemas con subestructuras óptimas siguiendo estos tres pasos:

1. Dividir el problema en sub-problemas más pequeños.

2. Resolver estos problemas de manera óptima usando este proceso de tres pasos recursivamente.

3. Usar estas soluciones óptimas para construir una solución óptima al problema original.

Los sub-problemas se resuelven a su vez dividiéndolos ellos mismos en sub-problemas más pequeños hasta que se alcance el caso fácil, donde la solución al problema es trivial.

El desarrollo de un algoritmo de Programación Dinámica corresponde a las siguientes etapas:

1ª etapa: Caracterizar la estructura de una solución óptima

2ª etapa: Definir recursivamente el valor de una solución óptima

3ª etapa: Calcular el valor de una solución optima en forma encajada de menos a mas, y

4ª etapa: Construir una solución óptima a partir de la información previamente calculada.

Para este Mini Proyecto debemos tener presente las siguientes especificaciones:

Entrada:

La entrada es un arreglo de la siguiente forma: A= {a1, a2, a3, a4, a5,…, an}

Donde cada ai esta compuesto de la siguiente manera:

ai= ti, di, pi, donde 1<= i <= n.

Donde:

A = Representa el conjunto de los procesos.

ti = Tiempo de procesamiento.

di = Tiempo tope de ejecución.

pi= Beneficio de cada proceso

Salida:

La salida es un arreglo S={ai, ai, ai, ai, ai,…, an}, siendo i el identificador de cada proceso y donde 1<= i <= n.

S es el conjunto de los procesos que da la solución óptima, además presenta un beneficio óptimo representando por:

Beneficio(A)={pi, pi, pi, pi, pi,…, pn} donde 1<= i <= n.

1ª etapa: Caracterizar la estructura de una solución óptima

En esta etapa se especifican cuantos y cuales son los sub-problemas resultantes para encontrar la solución óptima.

Los sub-problemas que van a aparecer son de la forma:

Sub-problema S={ai, ai, ai, ai, ai,…, an}, donde 1<= i <= n. Donde ai puede estar en otro orden diferente al de la entrada.

Para encontrar la solución debe generar una estructura como la que se representa en la figura adjunta.

El número de sub-problemas que hay es igual al número de subconjuntos del problema planteado, es decir n! sub-problemas.

2ª etapa: Definir recursivamente el valor de una solución óptima.

Debemos encontrar el orden de los procesos para dar la solución óptima al problema, para ello debemos ir buscando en los sub-problemas.

Por ejemplo para S1 se debe generar la siguiente estructura:

1 a1

2 a2, a3, a4, a5

3 a3, a4, a5

4 a4, a5

5 a5

Y así sucesivamente se va generando los sub-problemas, y se va guardando

...