PDF de programación - Programación II

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,[

]

=

⎧
⎪
⎪
⎨