Greddy
Páginas: 12 (2906 palabras)
Publicado: 1 de julio de 2014
Técnicas de Optimización (Greedy)
En esta sección estudiaremos varios problemas de optimización que se pueden resolver empleando algoritmo codiciosos o estrategia Greedy. Es común que en los problemas de optimización el algoritmo tenga que tomar una serie de decisiones cuyo efecto general es reducir al mínimo el costo total, o aumentar al máximo el beneficio total, de algún sistema. Elmétodo codicioso consiste en tomar sucesivamente, las decisiones de modo que cada decisión individual sea la mejor de acuerdo con algún criterio limitado "a corto plazo" cuya evaluación no sea demasiado costosa. Una vez tomada una decisión, no se podrá revertir, ni siquiera si más adelante se hace obvio que no fue una buena decisión. Por esta razón, los métodos codiciosos no necesariamente hallan lasolución óptima en muchos problemas. No obstante, en el caso de los problemas que se estudiaran en este capítulo, es posible demostrar que la estrategia codiciosa apropiada produce soluciones óptimas.
En general la estrategia Greedy trabaja en fases. En cada fase, se realiza una decisión que aparentemente es la mejor, sin considerar o lamentar futuras consecuencias. Generalmente, esta idea espensada como escoger algún óptimo local. Si se resume la estrategia como "toma lo que puedas obtener, ahora" podrá entender el porque del nombre de esta clase de algoritmos. Cuando el algoritmo termina tendremos la esperanza que el óptimo local es igual al óptimo global. Si este es el caso, entonces el algoritmo es correcto, de otra manera el algoritmo a generado una solución suboptimal. Si la "mejor"respuesta no es requerida entonces los algoritmos greedy son a menudo usados para generar respuestas aproximadas, en vez de usar algoritmos más complicados que requieren de otra estrategia para generar "la" respuesta correcta. En general la estrategia Greedy trabaja en etapas "Top-Down" realizando una elección greedy después de la otra. En resumen, la estrategia Greedy consiste de dos partes:
1.Subestructura Optimal
2. Partir con elección de óptimos locales y continuar haciendo elecciones localmente optimales, hasta que la solución es encontrada.
Problemas Asociados a esta técnica
Arbol Expandido Minimal ( Minimum Spanning Trees)
“Dado un grafo no-dirigido y conexo G = , donde cada arco tiene asociado una "longitud" o "peso", se desea un subconjunto T, de arcos E, tal que elgrafo restante sea conexo si solamente los arcos en T son usados, y la suma de los pesos de los arcos es el más pequeño posible. Tal subconjunto debe formar un subgrafo que es un árbol, al cual se le llama Minimum Spanning Tree.”
En el proceso de cambio de monedas, por ejemplo $15.530 puede expresarse en $15.530 = 1 * $10.000 + 1 * $ 5.000 + 1 * $ 500 + 3 * ($10). En total se requieren 5elementos. Al hacer esto estamos seguro de que el número de billetes y monedas es el mínimo.
Los problemas de tráfico son típicos casos en que las elecciones óptimas locales no siempre funcionan. Si duda, pregunte en Santiago sobre el resultado de las vías exclusivas que luego pasaron a ser vías segregadas
(Problema de Planificación de Tareas)
Dado los trabajos t 1, t 2, ... t n, con tiempost’1, t‘2, ... t’n y un solo procesador. Cuál es la mejor forma de planificar esos trabajos a fin de minimizar el tiempo medio de terminación?
(Código de Huffman) en la compresión de archivos.
Un código de longitud fija de un alfabeto A= { a1 , a2 , ..., am } con m-letras es una expresión en donde cada letra ai = ci,1 ci,2 ...ci,n , en donde i= 1, ...m, y donde cada ci,j es un elemento de algúnconjunto de símbolos. El conjunto C = { ci,1 ci,2 ...ci,n , tal que, i= 1, ...m, es llamado código de longitud fija de longitud n, y cada ci,1 ci,2 ...ci,,n es llamado código. Veamos con cierto detalle, como funciona esta estrategia en la resolución del problema de comprimir archivos.
Ejemplo:
Sea A= { a, b, c, d }, entonces { a= 00, b= 01, c=10, d=11} es un código de longitud fija para...
En esta sección estudiaremos varios problemas de optimización que se pueden resolver empleando algoritmo codiciosos o estrategia Greedy. Es común que en los problemas de optimización el algoritmo tenga que tomar una serie de decisiones cuyo efecto general es reducir al mínimo el costo total, o aumentar al máximo el beneficio total, de algún sistema. Elmétodo codicioso consiste en tomar sucesivamente, las decisiones de modo que cada decisión individual sea la mejor de acuerdo con algún criterio limitado "a corto plazo" cuya evaluación no sea demasiado costosa. Una vez tomada una decisión, no se podrá revertir, ni siquiera si más adelante se hace obvio que no fue una buena decisión. Por esta razón, los métodos codiciosos no necesariamente hallan lasolución óptima en muchos problemas. No obstante, en el caso de los problemas que se estudiaran en este capítulo, es posible demostrar que la estrategia codiciosa apropiada produce soluciones óptimas.
En general la estrategia Greedy trabaja en fases. En cada fase, se realiza una decisión que aparentemente es la mejor, sin considerar o lamentar futuras consecuencias. Generalmente, esta idea espensada como escoger algún óptimo local. Si se resume la estrategia como "toma lo que puedas obtener, ahora" podrá entender el porque del nombre de esta clase de algoritmos. Cuando el algoritmo termina tendremos la esperanza que el óptimo local es igual al óptimo global. Si este es el caso, entonces el algoritmo es correcto, de otra manera el algoritmo a generado una solución suboptimal. Si la "mejor"respuesta no es requerida entonces los algoritmos greedy son a menudo usados para generar respuestas aproximadas, en vez de usar algoritmos más complicados que requieren de otra estrategia para generar "la" respuesta correcta. En general la estrategia Greedy trabaja en etapas "Top-Down" realizando una elección greedy después de la otra. En resumen, la estrategia Greedy consiste de dos partes:
1.Subestructura Optimal
2. Partir con elección de óptimos locales y continuar haciendo elecciones localmente optimales, hasta que la solución es encontrada.
Problemas Asociados a esta técnica
Arbol Expandido Minimal ( Minimum Spanning Trees)
“Dado un grafo no-dirigido y conexo G = , donde cada arco tiene asociado una "longitud" o "peso", se desea un subconjunto T, de arcos E, tal que elgrafo restante sea conexo si solamente los arcos en T son usados, y la suma de los pesos de los arcos es el más pequeño posible. Tal subconjunto debe formar un subgrafo que es un árbol, al cual se le llama Minimum Spanning Tree.”
En el proceso de cambio de monedas, por ejemplo $15.530 puede expresarse en $15.530 = 1 * $10.000 + 1 * $ 5.000 + 1 * $ 500 + 3 * ($10). En total se requieren 5elementos. Al hacer esto estamos seguro de que el número de billetes y monedas es el mínimo.
Los problemas de tráfico son típicos casos en que las elecciones óptimas locales no siempre funcionan. Si duda, pregunte en Santiago sobre el resultado de las vías exclusivas que luego pasaron a ser vías segregadas
(Problema de Planificación de Tareas)
Dado los trabajos t 1, t 2, ... t n, con tiempost’1, t‘2, ... t’n y un solo procesador. Cuál es la mejor forma de planificar esos trabajos a fin de minimizar el tiempo medio de terminación?
(Código de Huffman) en la compresión de archivos.
Un código de longitud fija de un alfabeto A= { a1 , a2 , ..., am } con m-letras es una expresión en donde cada letra ai = ci,1 ci,2 ...ci,n , en donde i= 1, ...m, y donde cada ci,j es un elemento de algúnconjunto de símbolos. El conjunto C = { ci,1 ci,2 ...ci,n , tal que, i= 1, ...m, es llamado código de longitud fija de longitud n, y cada ci,1 ci,2 ...ci,,n es llamado código. Veamos con cierto detalle, como funciona esta estrategia en la resolución del problema de comprimir archivos.
Ejemplo:
Sea A= { a, b, c, d }, entonces { a= 00, b= 01, c=10, d=11} es un código de longitud fija para...
Leer documento completo
Regístrate para leer el documento completo.