programacion dinamicaaaa

INSTITUTO UNIVERSITARIO POLITÉCNICO“SANTIAGO MARIÑO”

EXTENSIÓN, PORLAMAR

PROGRAMACION DINAMICA

AUTORES:BR. JOSÉ CORDERO

PORLAMAR JULIO DE 2013

La programación dinámica es un enfoque general para la solución de problemas en los que es necesario tomar decisiones en etapas sucesivas. Las decisiones tomadas en una etapa condicionan la evolución futura del sistema, afectando a las situaciones en las que el sistema se encontrará en el futuro (denominadas estados), y a las decisiones que se plantearán en el futuro. Conviene resaltar que a diferencia de la programación lineal, el modelado de problemas de programación dinámica no sigue una forma estándar. Así, para cada problema será necesario especificar cada uno de los componentes que caracterizan un problema de programación dinámica.

Programación Dinámica

El Método de la Burbuja o Intercambio se basa en el principio de comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados.

METODO DE ORDENAMIENTO DE

LA BURBUJA

Vemos un ejemplo sencillo. Supongamos que queremos ordenar estos valores con el algoritmo de la burbuja: 45, 52, 21, 37, 49, así pues, n=5´.

(45, 52, 21, 37, 49)

METODO DE ORDENAMIENTO DE LA BURBUJA

1ª pasada: comparamos cada uno de los cuatro primeros (n-1) con los que le siguen. Si un elemento no está en orden con respecto al siguiente, los intercambiamos de sitio y seguimos. El elemento de mayor valor (52) irá "ascendiendo" hasta la última posición.

45, 52, 21, 37, 49 → Comparar 45 y 52. (1º y 2º) Están en orden. Seguimos.45, 52, 21, 37, 49 → Comparar 52 y 21. (2º y 3º) No están en orden. Intercambio.45, 21, 52, 37, 49 → seguimos

45, 21, 52, 37, 49 → Comparar 52 y 37 (3º y 4º). No están en orden. Intercambio.45, 21, 37, 52, 49 → seguimos

45, 21, 37, 52, 49 → Comparar 52 y 49. (4º y 5º). No están en orden. Intercambio.45, 21, 37, 49, 52 → Ya hemos terminado esta pasada.45, 21, 37, 49, 52 → El 5º elemento ya está en su sitio.


2ª pasada: comparamos cada uno de los tres primeros (n-2) con los que le siguen. No llegamos a hacer comparaciones que involucren al 5º elemento, porque la primera pasada hizo que el mayor de todos los elementos ocupara la última posición, con lo cual, sabemos que ese ya está en su sitio. Trabajaremos sólo con los cuatro que quedan.

45, 21, 37, 49, 52 → Comparar 1º y 2º. No están en orden. Intercambio.21, 45, 37, 49, 52 → seguimos

21, 45, 37, 49, 52 → Comparar 2º y 3º. No están en orden. Intercambio.21, 37, 45, 49, 52 → seguimos

21, 37, 45, 49, 52 → Comparar 3º y 4º. Están en orden. Pasada terminada.21, 37, 45, 49, 52 → El 4º elemento ya está en su sitio. (Fíjate en que el array ya está en orden, pero algoritmicamente, eso no lo sabemos).


3ª pasada: Comparamos cada uno de los dos primeros (n-3) con los siguientes.

21, 37, 45, 49, 52 → 1º y 2º. Están en orden. Seguimos.

21, 37, 45, 49, 52 → 2º y 3º. Están en orden. Pasada terminada.

21, 37, 45, 49, 52 → Ya tenemos tres en orden.


4ª y última pasada: Comparamos el primero con el segundo.

21, 37, 45, 49, 52 → 1º y 2º están en orden. Pasada terminada.21, 37, 45, 49, 52 → Ya tenemos los cuatro últimos en orden.21, 37, 45, 49, 52 → Así pues, el primero también lo estáLas solucion es:

21,37,45,49,52


El ordenamiento Shell (Shell sort en inglés) es un algoritmo de ordenamiento . El método se

denomina Shell en honor de su inventor Donald Shell. Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso.

METODO DE SHELL SORT

Veamos el siguiente arreglo:

75, 15, 22, 45, 39, 98, 12, 79, 66, 89, 31

Se debe empezar con k=n/2 , siendo n el número de elementos de arreglo, y utilizando siempre la división entera.... después iremos variando

k haciéndolo más pequeño mediante sucesivas divisiones por 2, hasta llegar a k=1.

METODO DE SHELL SORT

Empezamos con k=5. Así pues, vamos a dividir nuestro arreglo original en 5 sub-arreglo, en los cuales, sus elementos estarán separados por 5 lugares del arreglo original (el salto o gap es 5). Vamos a hacerlo con colores. Tomamos el primer elemento (el 75) contamos 5 lugares y tomamos también otro elemento (el 98) volvemos a contar 5 y tomamos otro (el 31) y acabamos porque se nos acaba el arreglo. El primer sub-arreglo con k=5 es el formado por 75, 98 y 31. Vamos a pintarlos en rojo

75, 15, 22, 45, 39, 98, 12, 79, 66, 89, 31

METODO DE ORDENAMIENTO DE SHELL SORT

Ahora, ordenaremos los elementos del sub-arreglo rojo pero sólo entre ellos, utilizando el algoritmo de Inserción directa.

31 , 15, 22, 45, 39, 75 , 12, 79, 66, 89, 98

Fíjate qué curioso. El 31, un elemento relativamente pequeño se ha ido hacia el principio y el 98 hacia el final... ¡pero dando saltos ( gap ) de 5 en 5 lugares! Cada uno ha avanzado en saltos de 5 hacia una posición cercana a su ubicación definitiva.


.Formemos ahora otro sub-arreglo con salto k=5... partiendo del segundo elemento (el 14) y contando 5 (tomamos también el 12) y ya está, porque se acaba el arreglo.

31 , 15 , 22, 45, 39, 75 , 12 , 79, 66, 89, 98


Vamos a ordenarlos entre ellos con Inserción directa, el 12 primero y el 15 después.

31 , 12 , 22, 45, 39, 75 , 15 , 79, 66, 89, 98


Ahora a por otro... el 22 y el 79

31 , 12 , 22, 45, 39, 75 , 15 , 79, 66, 89, 98

Están en orden entre ellos, así que se quedan como están.

Ahora le toca al sub-arreglo formado por el 45 y el 6631 , 12 , 22, 45, 39, 75 , 15 , 79, 66, 89, 98

Que también están en orden entre ellos y finalmente el 39 y el 89, que

también están en orden.31 , 12 , 22, 45, 39, 75 , 15 , 79, 66, 89, 98


Hemos formado 5 sub-arreglos en los cuales los elementos están separados por 5 lugares (porque k=5). Hemos ordenado cada sub-arreglo por separado utilizando inserción directa, y hemos logrado que cada elemento se dirija hacia su ubicación definitiva en pasos de 5 lugares. Por supuesto, no hemos terminado todavía, pero resulta evidente que algunos elementos, como el 31, el 98 o el 12 han dado un gran salto y que no deben andar muy lejos de su sitio final.

Para continuar con el algoritmo, debemos ir reduciendo progresivamente k dividiéndolo sucesivamente por 2 y k-ordenando los sub-arreglos que nos salgan (recuerda que nos salen k sub-arreglo). Cuando lleguemos a k=1 habremos terminado. Pero de momento, nuestra k valía 5, así que ahora k←k/2=5/2=2 Nuestra nueva k vale 2. Repetimos todo el tinglado, pero ahora nos saldrán 2 sub-arreglo cuyos elementos están separados por 2 lugares.


El primero (en marrón) y el segundo (en verde):

31, 12 , 22 , 45 , 39 , 75 , 15 , 79 , 66 , 89 , 98

Ordenamos por un lado los marrones entre ellos y los verdes entre ellos... es decir, 2-ordenamos el arreglo (curiosamente, los verdes ya están ordenados.... probablemente ha contribuido a ello la 5-ordenación que ya hemos hecho.

En ese caso, la ordenación ha requerido muy poco esfuerzo)

15 , 12 , 22 , 45 , 31, 75 , 39 , 79 , 66 , 89, 98


.Ahora que k=1 y que vamos a aplicar el algoritmo de inserción directa tal cual, haremos muchas menos comparaciones e intercambios que si lo hubiéramos aplicado con en arreglo tal como lo teníamos al empezar.

El algoritmo de inserción directa se comporta tanto mejor cuanto más cerca está cada elemento de su sitio definitivo. Finalmente, el arreglo queda de ésta manera:

12, 15, 22, 31, 39, 45, 66, 75, 79, 89, 98

Cada elemento descolocado ha tenido que moverse pocos lugares. Muchos de ellos ni siquiera se han movido.


se basa en el divide y vencerás paradigma. Su tiempo de ejecución del peor caso tiene un orden de crecimiento menor que la ordenación por inserción. Dado que se trata de subproblemas, declaramos cada subproblema como ordenar una submatriz A [p .. r]. Inicialmente, p = 1 y r = n, pero estos valores cambian a medida que recurse a través subproblemas.

METODO MERGER SORT

TENEMOS EL SIGUIENTE ARREGLO:

[6, 3, 5, 7, 1, 4, 3, 7]

PRIMERO DIVIDIMOS EL ARRGELO EN DOS PARTES IGUALES APROXIMADAMENTE Y NOS QUEDARIA:

[6, 3, 5, 7] [1, 4, 3, 7]

METODO DE ORDENAMIENTO DE MERGER SORT

Ahora se divide cada uno de los sub-arreglos en partes iguales:

Y que así:[6, 3, 5, 7] [1, 4, 3, 7]

[6, 3] [5, 7] [1, 4] [3, 7]

Ahora se ordena[3, 6] [5, 7] [1, 4] [3,7]

[3] [6] [5] [7] [1] [4] [3] [7]


TENEMOS EL ARREGLO ORDENADO Y SU SOLUCION QUEDA ASI :

[1, 3, 3, 4, 5, 6, 7, 7 ]


En algoritmia, el problema de la mochila, comúnmente abreviado por KP (del inglés Knapsack problem) es un problema deoptimización combinatoria. Modela una situación análoga al llenar una mochila, incapaz de soportar más de un peso determinado, con todo o parte de un conjunto de objetos, cada uno con un peso y valor específicos. Los objetos colocados en la mochila deben maximizar el valor total sin exceder el peso máximo.

METODO DE LA MOCHILA O DE LA BOLSA DE PAPEL

Problema de la Mochila Modelo Un excursionista planea salir de campamento. Hay cinco artículos que desea llevar consigo, pero entre todos sobrepasan las 60 libras que considera puede cargar. Para ayudarse en la selección ha asignado un valor a cada artículo en orden ascendente de importancia.

METODO DE ORDENAMIENTO DE LA MOCHILA

Articulo 1 2 3 4 5

Peso 42 23 21 15 7

Valor 100 60 10 15 15

Planteamiento Puesto que el modelo es binario, la variable puede tomar solo dos posibles valores:Xi = 0 no se lleva el articulo i, 1 sí se lleva el articulo i. Max Z= 100X1 + 60X2 + 70X3 + 15X4 + 15X5 s.a. 42X1 + 23X2 + 21X3 + 15X4 + 7X6 <= 60 Xi {0,1}∈

METODO DE LA MOCHILA

Solución Z = 145X1 = 0X2 = 1X3 = 1X4 = 1X5 = 0 Interpretación El que alguna variable del valor de 1, significa que nos llevamos en la mochila el artículo. En este caso nos llevamos los artículos 2, 3 y 4. El valor de Z nos indica el beneficio de llevar los tres artículos. Por último, de acuerdo con la restricción, no sobrepasamos el peso permitido.

METODO DE LA MOCHILA

programacion dinamicaaaa

Documents