PDF de programación - Programación II

Imágen de pdf Programación II

Programación IIgráfica de visualizaciones

Publicado el 14 de Enero del 2017
1.585 visualizaciones desde el 14 de Enero del 2017
57,6 KB
9 paginas
Creado hace 10a (24/05/2011)
Programación II
Bloque temático 1. Lenguajes de programación
Bloque temático 2. Metodología de programación
Bloque temático 3. Esquemas algorítmicos

Tema 4. Introducción a los Algoritmos
Tema 5. Algoritmos voraces, heurísticos y aproximados
Tema 6. Divide y Vencerás
Tema 7. Ordenación
Tema 8. Programación dinámica
Tema 9. Vuelta atrás
Tema 10.Ramificación y poda

Tema 11.Elección del esquema algorítmico

Programación II

Tema 11. Elección del esquema algorítmico

© Mario Aldea Rivas

24/05/11

Tema 11.Elección del esquema algorítmico

11.1. Resumen de los esquemas algorítmicos
11.2. Caso de estudio: fontanero con penalización
11.3. Bibliografía



1



Programación II

Tema 11. Elección del esquema algorítmico

© Mario Aldea Rivas

24/05/11

2

11.1 Resumen de los esquemas algorítmicos

11.1 Resumen de los esquemas algorítmicos

Cuando nos enfrentamos a un problema nuevo

• tendremos que idear un algoritmo que nos permita resolverle
• basado en alguno de los esquemas algorítmicos que

conocemos

• es necesario saber identificar el o los esquemas que ofrecen
mayores posibilidades de éxito para ese problema particular

La mayoría de los problemas pueden resolverse utilizando varios
esquemas algorítmicos

• elegiremos la mejor opción en base a su eficiencia temporal y
espacial y, en menor medida, a su facilidad de implementación

• en ocasiones no quedará más remedio que implementar las

diferentes alternativas para poder compararlas

Programación II

© Mario Aldea Rivas

24/05/11

3

Tema 11. Elección del esquema algorítmico

Algoritmos voraces
Aplicables a problemas que:

11.1 Resumen de los esquemas algorítmicos

• la solución se construye añadiendo en cada etapa un nuevo

elemento a la solución parcial

• verifican el Principio de Optimalidad: “en una secuencia óptima

de decisiones toda subsecuencia ha de ser también óptima”

Es fundamental disponer de una función de selección

• es necesario probar que con esa función de selección

conducen a la solución óptima

Un algoritmo voraz (en el caso de que exista) suele ser la
alternativa más eficiente y sencilla de resolver un problema
Ejemplos:

• dar el cambio, mochila fraccionada, MST, caminos mínimos, ...

Programación II

Tema 11. Elección del esquema algorítmico

© Mario Aldea Rivas

24/05/11

Algoritmos heurísticos y aproximados

11.1 Resumen de los esquemas algorítmicos

Se utilizan en problemas muy complicados para los que

• no sabemos como encontrar su solución óptima, o bien,
• conocemos el algoritmo que permite encontrar la solución

óptima, pero requiere una cantidad excesiva de tiempo
(complejidad exponencial)

Muchos de los algoritmos heurísticos y aproximados son
algoritmos voraces
Permiten obtener soluciones más o menos cercanas a la óptima

4

5

Programación II

Tema 11. Elección del esquema algorítmico

© Mario Aldea Rivas

24/05/11

Divide y Vencerás
Aplicables a problemas que admitan una formulación recursiva
Para que resulte eficiente aplicar DyV debe verificarse que:

11.1 Resumen de los esquemas algorítmicos

• la formulación recursiva nunca resuelva el mismo subproblema

más de una vez
- cuando no es posible generar subproblemas independientes

suele resultar más eficiente usar Programación Dinámica

• la descomposición en subproblemas y la combinación de las

soluciones sean operaciones eficientes

• los subproblemas sean aproximadamente del mismo tamaño

Ejemplos:

• búsqueda binaria, selección, subvector de suma máxima,

mergesort, quicksort, ...

Programación II

© Mario Aldea Rivas

24/05/11

6

Tema 11. Elección del esquema algorítmico

Programación dinámica
Utilizable en problemas que admitan una formulación recursiva
• las ecuaciones recursivas se utilizan para generar una tabla

11.1 Resumen de los esquemas algorítmicos

Aplicables en el mismo tipo de problemas que los voraces:

• la solución se construye añadiendo en cada etapa un nuevo

elemento a la solución parcial

• verifican el Principio de Optimalidad “relajado”: “la solución

óptima de un problema es una combinación de soluciones
óptimas de algunos de sus subcasos”

Ejemplos:

• dar el cambio, mochila entera, ...

Programación II

Tema 11. Elección del esquema algorítmico

© Mario Aldea Rivas

24/05/11

7

Vuelta Atrás y Ramificación y Poda
Realizan una exploración exhaustiva del espacio de soluciones
• por lo que suelen ser menos eficientes que los Voraces o PD

11.1 Resumen de los esquemas algorítmicos

Aplicables a problemas en los que

• la solución se construye añadiendo en cada etapa un nuevo

elemento a la solución parcial

• en cada etapa se elige entre un conjunto finito de valores

RyP es una variante de VA utilizada si existe una función “coste”
que permita

• ordenar los nodos por probabilidad de conducir a la solución
• detectar los nodos que no pueden conducir a la solución

óptima

Ejemplos: mochila, n reinas, laberinto, asignación, ...

Programación II

Tema 11. Elección del esquema algorítmico

© Mario Aldea Rivas

24/05/11

11.1 Resumen de los esquemas algorítmicos

Eficiencia de los distintos esquemas
Clasificación orientativa por eficiencia temporal:

Voraces

más
eficiente

DyV
PD

VA

RyP

menos
eficiente

Clasificación orientativa por eficiencia espacial:

• voraces: lo normal es que no requieran memoria adicional
• DyV: puede ser necesario utilizar memoria adicional en la

recombinación de soluciones

• VA: máxima “profundidad” de las llamadas recursivas,

depende de la longitud de la solución
• PD: tabla con las soluciones parciales
• RyP: cola de nodos vivos, cada nodo con la información

correspondiente a su estado

Programación II

© Mario Aldea Rivas

24/05/11

8

9

Tema 11. Elección del esquema algorítmico

11.2 Caso de estudio: fontanero con penalización

11.2 Caso de estudio: fontanero con penalización
Un fontanero tiene varios trabajos pendientes, cada trabajo tiene:

- duración: días que tarda en realizarse
- plazo de finalización: día en que debe estar acabado
- penalización: lo que el fontanero deja de ganar si no acaba el

trabajo dentro del plazo

Deberemos encontrar el orden de realización de los trabajos que
minimice las penalizaciones, p.e.:

Trabajo

Dur.

Plazo Penali.

t1
t2
t3
t4

2
3
2
4

3
4
5
7

3
2
1
5

0

Se puede demostrar que la realización de los trabajos
ordenados de menor a mayor plazo conduce a mejores
soluciones que si no se sigue ese orden

Orden óptimo: t1,t4
Penalización: 3
t1
1

t4
4

3

2

5

6

7

sólo es necesario analizar
hasta el plazo máximo

Programación II

© Mario Aldea Rivas

24/05/11

10

Tema 11. Elección del esquema algorítmico

Análisis del problema

Características:

11.2 Caso de estudio: fontanero con penalización

• se trata de un problema de optimización
• la solución se construye añadiendo en cada etapa un nuevo

elemento a la solución
- el siguiente trabajo a realizar (conjunto finito de

posibilidades)

• verifica el Principio de Optimalidad “relajado”

- la solución óptima del problema es una combinación de

soluciones óptimas de algunos de sus subcasos

Buscamos la solución óptima:

• descartamos heurísticos y aproximados

Programación II

Tema 11. Elección del esquema algorítmico

© Mario Aldea Rivas

24/05/11

11

11.2 Caso de estudio: fontanero con penalización

Análisis del problema (cont.)

Con las características citadas, los esquemas más apropiados
para resolver el problema podrían ser:

• voraces, programación dinámica, vuelta atrás y ramificación y

poda

No parece apropiado utilizar DyV en este caso

• no es posible partir el problema en partes y resolverlas de

forma independiente para luego combinarlas

Comenzaremos explorando la posibilidad de resolver el problema
utilizando el esquema más sencillo y probablemente más
eficiente: voraces

Programación II

© Mario Aldea Rivas

24/05/11

12

Tema 11. Elección del esquema algorítmico

11.2 Caso de estudio: fontanero con penalización

Solución “voraz”
Debemos encontrar una función de selección que nos permita
elegir el siguiente trabajo a realizar en cada etapa
Podemos pensar varias alternativas de selección de los trabajos:
• primero los de menor duración o primero los de menor plazo o

primero los de mayor penalización

• primero los de mayor relación penalización/duración

Para todos las selecciones citadas existe un contraejemplo:
(d1=5,pl1=5,pe1=6,r1=6/5)
(d2=4,pl2=8,pe2=4,r2=4/4)
(d3=4,pl3=8,pe3=3,r3=3/4)

(d1=1,pl1=1,pe1=3)
(d2=2,pl2=2,pe2=4)

menor duración o menor plazo: t1

óptima: t2

mayor relación o penalización: t1

óptima: t2,t3

Estas funciones de selección nos servirán para implementar
heurísticos, pero no para encontrar la solución óptima

© Mario Aldea Rivas

24/05/11

13

Programación II

Tema 11. Elección del esquema algorítmico

11.2 Caso de estudio: fontanero con penalización

Solución basada en Programación Dinámica
Supongamos que el fontanero tiene T trabajos pendientes
(ti=(duri,pli,pei), 1≤i≤T) ordenados de menor a mayor plazo
• el plazo máximo será plT y la penalización total ptotal=Σpei
Crearemos una tabla p[0..T,0..plT]
• p[t,d] representa la penalización hasta el día d si sólo se
pudieran realizar trabajos en el rango 1..t

Expresión recursiva para cada posición p[t,d] de la tabla:
• si no se ha cumplido el plazo (d≤plt) elegiremos el mínimo de:
- no realizar el trabajo t, entonces: p[t,d]=p[t-1,d]
- realizar el trabajo t, entonces: p[t,d]=p[t-1,d-durt]-pet
• si se ha cumplido el plazo (d>plt):
- se mantiene el valor del día anterior: p[t,d]=p[t,d-1]

Programación II

© Mario Aldea Rivas

24/05/11

14

Tema 11. Elección del esquema algorítmico

11.2 Caso de estudio: fontanero con penalización
Solución basada en Programación Dinámica (cont.)
De lo anterior, junto con las condiciones de contorno, se obtiene
la expresión recursiva que nos permite calcular la tabla:

ptotal
p t d
1–
,[
d,
p t
1–
[
min p t
(
[

]
]
1–

si

d

=

si
si
] p t
[
,

1–

d,

0 o t
d
>
durt
–,
d

plt
d>
durt

]

=

0



pet

)

en otro caso

p t d,[

]

=




  • Links de descarga
http://lwp-l.com/pdf1002

Comentarios de: Programación II (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad