Rod Cutting 5i445i

Rod Rod cutting cutting

Programación Programación Dinámica Dinámica Alex Ticona Bejarrano Nicolas Herencia Castro Suma Paucara Miguel Angel Universidad Nacional de San Agustín Escuela Profesional Ingeniería de Sistemas RodDEL Cutting 22 DEL FEBRERO 2017

1/11

Rod Cutting

Índice Explicación del problema  Introducción al problema  Enunciado

Algoritmo Recursivo  Análisis  Formulación Recursiva

Hallmark #1: Subestructuras óptimas  Demostración  Implementación  Análisis del tiempo de Ejecución

Hallmark #2: Subproblemas repetidos  Top-Down Memoization

Rod Cutting

2/11

Rod Cutting Explicación del Problema Introducción

Introducción Serling Enterprises compra varillas largas de acero y las corta en varillas mas pequeñas, las cuales posteriormente las vende obteniendo ingresos. Se desea saber la mejor forma de cortar las varillas. Asumimos que sabemos el precio pi que la empresa cobra por una varilla de longitud i pulgadas.

Longitu di

1

2

3

4

5

6

7

Precio pi

1

5

8

9

10

16

17

Rod Cutting

3/11

Rod Cutting Explicación del Problema Enunciado

Enunciado del problema Dada una varilla de longitud n pulgadas y una tabla de precios pi (donde i = 1, 2, ..., n), determinar el máximo ingreso rn que se puede obtener cortando la varilla y vendiendo las piezas. 10

1

Longitu di

1

2

3

4

5

6

7

Precio pi

1

5

8

9

10

16

17

Rod Cutting

1

rn = 12

4/11

Rod Cutting Explicación del Problema Enunciado

Enunciado del problema Dada una varilla de longitud n pulgadas y una tabla de precios pi (donde i = 1, 2, ..., n), determinar el máximo ingreso rn que se puede obtener cortando la varilla y vendiendo las piezas. 1

8

1

Longitu di

1

2

3

4

5

6

7

Precio pi

1

5

8

9

10

16

17

Rod Cutting

5

rn = 15

4/11

Rod Cutting Explicación del Problema Enunciado

Enunciado del problema Dada una varilla de longitud n pulgadas y una tabla de precios pi (donde i = 1, 2, ..., n), determinar el máximo ingreso rn que se puede obtener cortando la varilla y vendiendo las piezas. 17

Longitu di

1

2

3

4

5

6

7

Precio pi

1

5

8

9

10

16

17

Rod Cutting

rn = 17

4/11

Rod Cutting Explicación del Problema Enunciado

Enunciado del problema Dada una varilla de longitud n pulgadas y una tabla de precios pi (donde i = 1, 2, ..., n), determinar el máximo ingreso rn que se puede obtener cortando la varilla y vendiendo las piezas. 5 5 8

Longitu di

1

2

3

4

5

6

7

Precio pi

1

5

8

9

10

16

17

Rod Cutting

rn = 18

4/11

Rod Cutting Algoritmo Recursivo Análisis

¿En cuántas formas distintas podemos cortar una varilla de longitud n? Rpta. : 2n-1 Ej. n = 4

 Hay

a)

b)

c)

d)

e)

f)

g)

h)

posiciones de corte, y se debe escoger cortes  

Rod Cutting

5/11

Rod Cutting Algoritmo Recursivo Análisis

¿En cuántas formas distintas podemos cortar una varilla de longitud n? Rpta. : 2n-1 Ej. n = 4

 Hay

 

0 cortes a)

b)

c)

d)

e)

f)

g)

h)

posiciones de corte, y se debe escoger cortes  

Rod Cutting

5/11

Rod Cutting Algoritmo Recursivo Análisis

¿En cuántas formas distintas podemos cortar una varilla de longitud n? Rpta. : 2n-1

 

Ej. n = 4

 Hay

1 corte a)

b)

c)

d)

e)

f)

g)

h)

posiciones de corte, y se debe escoger cortes  

Rod Cutting

5/11

Rod Cutting Algoritmo Recursivo Análisis

¿En cuántas formas distintas podemos cortar una varilla de longitud n? Rpta. : 2n-1

 

Ej. n = 4

 Hay

a)

b)

c)

d)

e)

f)

g)

h)

posiciones de corte, y se debe escoger cortes

2 cortes

 

Rod Cutting

5/11

Rod Cutting Algoritmo Recursivo Análisis

¿En cuántas formas distintas podemos cortar una varilla de longitud n? Rpta. : 2n-1

 

Ej. n = 4

 Hay

a)

b)

c)

d)

e)

f)

g)

h)

3 cortes

posiciones de corte, y se debe escoger cortes  

Rod Cutting

5/11

Rod Cutting Algoritmo Recursivo Análisis

¿En cuántas formas distintas podemos cortar una varilla de longitud n? Rpta. : 2n-1 Ej. n = 4

 Hay

a)

b)

c)

d)

e)

f)

g)

h)

posiciones de corte, y se debe escoger cortes  

Yuliana G. Apaza Yllachura

Rod Cutting

5/11

Rod Cutting Algoritmo Recursivo Formulación Recursiva

Formulación Recursiva  Notación

Aditiva:

Si una solución óptima corta la varilla en k piezas, donde , entonces su descomposición sería:

 

 

Rod Cutting

6/11

Rod Cutting

Hallmark #1 Demostración

Hallmark #1: Subestructuras Óptimas  Demostración:

Sea el ingreso máximo obtenido, es decir: con a = debe ser óptimo? Supongamos que existe un b > a, entonces → Pero esto es contradictorio. Rod Cutting

7/11

Rod Cutting

Hallmark #1 Implementación

Implementación  

Cut-Rod(p, n) 1 2 3 4 5 6

if n == 0 return 0 q = -inf for i = 1 to n q = max(q, p[i] + Cut-Rod(p, n - i)) return q

Cada vez que el tamaño de entrada se hace más grande, su tiempo de ejecución irá duplicándose aproximadamente. Rod Cutting

8/11

Rod Cutting

Hallmark #1 Análisis del tiempo de ejecución

¿Por qué es ineficiente? Cut-Rod(p, n) → Cut-Rod(p, n-i) , i = 1,2, ... n n n–1 n–2 n-3 ...

...

...

1 0

n-2 0

n–3 n-4 ...

1

... ...

1

0

0

0

0

...  

0

Tiempo Exponencial ! Yuliana G. Apaza Yllachura

  Rod Cutting

9/11

Rod Cutting

Hallmark #2

Hallmark #2: Subproblemas repetidos  Métodos

- Top-down con Memoization

Una solución de tiempo exponencial transformada a tiempo polinomial. Rod Cutting

puede

ser

10/11

Rod Cutting

Hallmark #2 Memoization

Memorization Memoized-Cut-Rod (p, n) 1 let r[0...n] be a new array -inf -inf 2 for i = 0 to n 3 r[i] = -inf 4 return Memoized-Cut-Rod-Aux(p, n, r) Memoized-Cut-Rod-Aux(p, n, r) 1 2 3 4 5 6 7 8 9

-inf

...

-inf

-inf

-inf

if r[n] 0 return r[n] if n == 0 n q = 0 -inf -inf -inf ... q -inf -inf else q = -inf for i = 1 to n q = max(q, p[i] + Memoized-Cut-Rod-Aux(p, n - i, r)) r[n] = q return q Rod Cutting

11/11