Apuntes N 7 Paradigma 4 Heurísticas Apunte Carlos Gómez

Introducci´
on
Bin Packing
Knapsack Problem
Resumen

Cap´ıtulo 2: Paradigmas:
Heur´ısticas
Carlos G´
omez-Pantoja
Universidad Andr´es Bello

Oto˜
no, 2013

Carlos G´
omez-Pantoja Universidad Andr´
es Bello

Cap´ıtulo 2: Paradigmas: Heur´ısticas

Introducci´
on
Bin Packing
Knapsack Problem
Resumen

Tabla de Contenidos

1

Introducci´on

2

Bin Packing

3

Knapsack Problem

4

Resumen

Carlos G´omez-Pantoja Universidad Andr´
es Bello

Cap´ıtulo 2: Paradigmas: Heur´ısticas

Introducci´
on
Bin Packing
Knapsack Problem
Resumen

Problemas del Mundo Real

1

Algunos problemas pueden solamente ser resueltos por
algoritmos con pobre desempe˜
no (exponencial).

2

Instancias de problemas en el mundo real son a menudo muy
grandes.

3

Resolverlo podr´ıa tomar mucho tiempo, incluso si este´oricamente posible.

4

Sin embargo, para muchos problemas podemos encontrar
soluciones no ´optimas pero suficientemente buenas.

Carlos G´
omez-Pantoja Universidad Andr´
es Bello

Cap´ıtulo 2: Paradigmas: Heur´ısticas

Introducci´
on
Bin Packing
Knapsack Problem
Resumen

Problemas del Mundo Real

1

2

Un algoritmo heur´ıstico es un algoritmo que produce una
soluci´on a un problema, pero no unasoluci´
on necesariamente
´optima.
T´ıpicamente, un algoritmo heur´ıstico est´a dise˜
nado para:
Encontrar una buena soluci´
on.
Encontrar una soluci´
on r´apidamente.

3

Idealmente, se desea un algoritmo he´
ur´ıstico con una mejor
complejidad computacional que un algoritmo que encuentra la
soluci´on ´optima.

Carlos G´
omez-Pantoja Universidad Andr´
es Bello

Cap´ıtulo 2: Paradigmas: Heur´ısticasIntroducci´
on
Bin Packing
Knapsack Problem
Resumen

Bin Packing

1

Imaginar que se tienen canastos o cajas.

2

Se tienen algunos ´ıtemes (de diferente tama˜
no) a empacar en
estos canastos.

3

El problema es empacar los ´ıtemes en la menos cantidad de
canastos posibles.

Carlos G´
omez-Pantoja Universidad Andr´
es Bello

Cap´ıtulo 2: Paradigmas: Heur´ısticas

Introducci´
on
Bin Packing
KnapsackProblem
Resumen

Bin Packing: Cu´antas Dimensiones

1

El problema tiene variaciones, dependiendo de cu´antas
dimensiones se consideren:
3 dimensiones: cajas de comida en una despensa.
2 dimensiones: escritorios en una oficina.
1 dimensi´
on: avisos de TV durante un break.

2

Otra variaci´on es cuando los canastos tiene el mismo o
diferentes tama˜
nos.

3

S´olo se considerar´a Bin Packing1-Dimensi´
on, y se
restringir´a el tama˜
no de los canastos a que sea el mismo.

Carlos G´
omez-Pantoja Universidad Andr´
es Bello

Cap´ıtulo 2: Paradigmas: Heur´ısticas

Introducci´
on
Bin Packing
Knapsack Problem
Resumen

Bin Packing 1-Dimensi´on: Ejemplo
1

Considerar una situaci´
on donde se tienen canastos de
capacidad 100, y los ´ıtemes tienen los siguientes tama˜
nos: [9,
25, 14, 11, 3, 7, 10,49, 17, 34, 33, 6, 4, 24, 28, 5, 18, 26, 13].

Carlos G´
omez-Pantoja Universidad Andr´
es Bello

Cap´ıtulo 2: Paradigmas: Heur´ısticas

Introducci´
on
Bin Packing
Knapsack Problem
Resumen

Bin Packing 1-Dimensi´on: Ejemplo
1

Considerar una situaci´
on donde se tienen canastos de
capacidad 100, y los ´ıtemes tienen los siguientes tama˜
nos: [9,
25, 14, 11, 3, 7, 10, 49, 17, 34, 33, 6, 4, 24, 28,5, 18, 26, 13].

Carlos G´
omez-Pantoja Universidad Andr´
es Bello

Cap´ıtulo 2: Paradigmas: Heur´ısticas

Introducci´
on
Bin Packing
Knapsack Problem
Resumen

Bin Packing 1-Dimension

1

Objetivo. Usar la menor cantidad de canastos posibles.

2

Esto requiere minimizar la cantidad de espacio desperdiciado
en la cima de cada canasto.

3

La soluci´on ´optima podr´ıa ser encontrada evaluandocada
combinaci´on posible de ´ıtemes (mucho tiempo).

4

Por ejemplo, la situaci´
on anterior tiene 19 ´ıtemes, lo que
implica 19! ordenamientos posibles (121645100408832000
posibilidades).

5

En general, los problemas de Bin Packing tienen una
complejidad exponencial.

Carlos G´
omez-Pantoja Universidad Andr´
es Bello

Cap´ıtulo 2: Paradigmas: Heur´ısticas

Introducci´
on
Bin Packing
Knapsack...