ALGORITMOS HEURÍSTICOS Y APROXIMADOS · Algoritmos aproximados y heurísticos para problemas...

ALGORITMOS HEURÍSTICOS Y APROXIMADOS

Análisis y diseño de algoritmos II- 2009

Problemas “difíciles”: Definiciones, ejemplos y

propiedades

Análisis y diseño de algoritmos II- 2009

Un viaje a Ciencias de la Computación I…

Problema

“lo describe un”

Lenguaje

Clasificación de problemas

Problemas de decisión Problemas de optimización

Indecidibles Insolubles

Decidibles Solubles Soluciones

algorítmicas

Problemas de decisión:

Ejemplos

Un problema de decisión puede ser formulado de

manera tal que dada una entrada requiere una respuesta

simple: “si” o “no”.

Problemas decidibles

Ejemplo: Determinar la pertenencia de una cadena a

un lenguaje de tipo 2.

Problemas indecidibles

Ejemplo: Problema del Halting

Problemas de optimización:

Ejemplos

Informalmente, los problemas de optimización son un tipo

general de problemas en lso que se desea elegir el mejor de un

conjunto de elementos.

“Coloreo de un grafo”

Dado un grafo G = (V,E) y un conjunto finito de colores S, un

coloreo es un mapping C:V-> S, tal que si existe un arco

(v,w) ε E, luego C(v) < > C(w). Determinar el mínimo coloreo

de G.

“Problema de la mochila”

Dado un conjunto de n objetos de tamaños s1,s2, …sn y una

mochila de capacidad C (s1,s2, …sn y C son enteros positivos)

encontrar un subconjunto de objetos que maximice el uso de la

mochila.

Problemas de optimización:

Ejemplos

Problema del viajante

Dadas las distancias entre un conjunto de n

ciudades, determinar el circuito que debería

recorrer un viajante, que parte de una estas

ciudades, visita a todas las demás exactamente

una vez y vuelve al punto de partida, habiendo

recorrido la menor distancia posible.

Problemas de optimización:

Ejemplos

Ordenamiento de tareas con penalidades

Dadas n tareas a ser ejecutadas una por vez. Cada tarea Ji tiene

un tiempo de ejecución ti, un plazo de espera di medido desde el

comienzo de la ejecución, una penalidad pi por exceder el plazo

de espera. Un orden específico de tareas es una permutación S

de {1,2,...,n} donde Js(1) es la primera tarea ejecutada, Js(2) la

siguiente, etc. La penalidad total para un ordenamiento particular

es

n

P S = Σ [if (t s(1) + ....+ t s(i) ) > d s(i) then ps(i) else 0]

i=1

Se requiere encontrar un ordenamiento tal que minimice la

penalidad total

“Problemas de decisión” versus

“Problemas de Optimización”

Ø La clasificación de problemas de decisión puede

basarse en modelos de procedimientos más simples

que los que requeriría una clasificación de problemas

de optimización. Por ejemplo, pueden basarse en

autómatas “reconocedores” como la máquina de

Turing.

Ø Para todo problema de optimización se puede

construir una versión de un problema de decisión del

mismo “grado de dificultad”.

“Problemas de decisión” versus

“Problemas de Optimización”

“Problema del Coloreo de un grafo”

Versión de Optimización

Dado un grafo G = (V,E) y un conjuto finito de colores

S, un coloreo es un mapping C:V-> S, tal que si existe

un arco (v,w) ε E, luego C(v) < > C(w). Se requiere

colorear el grafo con la mínima cantidad de colores.

Versión de Decisión

Dado un grafo G y un entero positivo k ¿existe un

coloreo de k colores?

“Problemas de decisión” versus

“Problemas de Optimización”

Versión de optimización del “viajante”

Dadas las distancias entre un conjunto de n

ciudades, determinar el circuito que debería

recorrer un viajante, que parte de una estas

ciudades, visita a todas las demás exactamente

una vez y vuelve al punto de partida, habiendo

recorrido la menor distancia posible.

“Problemas de decisión” versus

“Problemas de Optimización”

Versión de decisión del “viajante”

Dadas las distancias entre un conjunto de n

ciudades, determinar si existe un circuito cuya

distancia total sea ≤ K y puede ser recorrido por

un viajante que parte de una estas ciudades,

visita a todas las demás exactamente una vez y

vuelve al punto de partida.

Clasificación de problemas decidibles

P-tiempo

Ø

La clase de problemas de decisión de complejidad

temporal polinomial.

Ø

La clase de lenguajes que pueden ser reconocidos por

Máquinas de Turing determinísticas de complejidad

temporal polinomial

Clasificación de problemas decidibles

NP-tiempo

Ø

La clase de lenguajes que pueden ser reconocidospor Máquinas de Turing no-determinísticas de complejidad temporal polinomial

ØNondeterministic Polinomial

NP

Relación entre NP-tiempo y P-tiempo

Problema abierto:

¿NP-tiempo incluye a P-tiempo?

¿Qué se sabe sobre NP-tiempo?

Se ha identificado una clase de problemas de NP-tiempo.

NP-Completo

Un lenguaje Lo está en NP-Completo si todo lenguaje

L1ε NP-tiempo “se reduce” a Lo en un tiempo polinomial

Relación entre NP-tiempo y P-tiempo Un lenguaje Lo está en NP-Completo si todo lenguaje

L1∈ NP-tiempo “se reduce” a Lo en un tiempo polinomial

ØM1 y M2 son Máquinas de Turing definidas sobre un mismoalfabeto.

ØM2 es una Máquina de Turing no determinística que reconoce a L0.

ØM1 es una Máquina de Turing determinística de complejidadtemporal polinomial, que convierte a la cadena w1 en la cadena w2de forma tal que si w1 ε L1 luego w2 ε L2.

MT M1 MT M2w1 SIw2

NO

Reconoce a L1 Reconoce a Lo

Relación entre NP-tiempo y P-tiempo

Los problemas NP-Completo son los “más difíciles” en

NP-tiempo dado que si existiese un algoritmo de complejidadtemporal polinomial para un problema de la clase NP-Completo, luego existiría un algoritmo de complejidad temporal polinomialpara TODO problema perteneciente a NP-tiempo.

Informalmente, si existiese un algoritmo polinomial para un problema NP-completo, podríamos resolver cualquier problemaen NP-tiempo en un tiempo polinomial

Relación entre NP-tiempo y P-tiempo

NP-Completo

L ε NP-Completo si

1. L ε NP-tiempo

2. Para todo L´ ε NP-tiempo , L´ “se reduce a “ L

NP

NP_COMPLETO

Relación entre NP-tiempo y P-tiempo

Si bien no se han encontrado algoritmos

acotados polinomialmente para problemas

NP-Completos, no se ha podido demostrar que

no existen!!!

NP-tiempo ? P-tiempo

NP-tiempo

NP-COMPLETOP-tiempo

SE CONJETURANO DEMOSTRADO

Relación entre P-tiempo y NP-tiempo

SAT ( Satisfiability) es el primer problema parael que fue demostrada su pertenencia a la claseNP-Completo.

SAT: Evaluar una fórmula del cálculoproposicional es un problema NP-Completo

Demostrado por Steven Cook en 1974

Relación entre P-tiempo y NP-tiempo

SAT: Evaluar una fórmula del cálculo

proposicional es un problema NP-Completo.

Bases de la demostración de Cook:

MTD SAT

<M,w> FM (w) SI

NO

M: codificación de MT NDw: cadena

<M,w> describe NP-tiempo, porqué?

fórmula

Relación entre NP-tiempo y P-tiempo

Para probar que un problema A en NP-tiempo es

NP-completo es suficiente probar que algún otro

problema NP-completo B “se reduce a” A. Es

decir, A es polinomialmente transformable a B.

SAT

FNC-SAT

Ciclo Hamiltoniano

Viajante

Relación entre P-tiempo y NP-tiempo

Ejemplos de NP-Completos

Versión de decisión del “viajante”

Versión de decisión del “Coloreo de un grafo”

?¿Qué sucedería si “alguien” descubriese un

algoritmo polinomialmente acotado para un

problema NP-Completo?

Problemas “difíciles”

Siempre es posible construir una versión de decisión

para un problema de optimización que tenga el mismo

grado de dificultad.

Decisión Optimización

NP-Completo NP-Hard

Ejemplos de NP-Hard

Versión de optimización del “Viajante”

Versión de optimización del “Coloreo de un grafo”

Problemas “difíciles”

Problemas computacionalmente

Ø TRATABLES

Ø INTRATABLES

¿Qué relaciones existen entre los problemas

tratables, intratables y las clases de problemas

P-tiempo, NP-Tiempo, NP-Completo y

NP Hard?

Problemas “difíciles”No podemos afirmar que todo problema en P-tiempo tiene una

solución eficiente.

Ø Para ciertas instancias y en función de restricciones al tiempo de ejecución un problema en P-tiempo puede ser ineficiente.

Ø Puede estar en P-tiempo y el orden del polinomio alto

No podemos afirmar que todo problema en NP-Hard es

ineficiente

Ø Un problema en NP-Hard puede ser “tratable” para ciertasinstancias.

Sin embargo…

Problemas “difíciles”

Sin embargo…

hay muy buenas razones para buscar soluciones

que estén en P-tiempo dado que un problema que

no está en P-tiempo será, en general, muy

costoso y probablemente intratable”.

Problemas “difíciles”Un algoritmo para un problema complejo puede construirse

combinando algoritmos para problemas simples. Los algoritmos

simples pueden operar sobre las mismas entradas o sobre entradas

calculadas como resultados intermedios de otros problemas

simples.

Luego, la complejidad del algoritmo puede ser acotada

por suma, multiplicación y composición de complejidades de

otros algoritmos. Los polinomios son cerrados bajo estas

operaciones, luego cualquier algoritmo construido a partir de

algoritmos acotados polinomialmente será un algoritmo acotado

polinomialmente también.

Algoritmos aproximados y heurísticos

para problemas NP-Hard

Si bien no se ha podido demostrar aún que no existen

algoritmos eficientes para las clases NP-completo y

NP-Hard, desde el punto de vista práctico hay que

resolverlos eficientemente.

Ø Si las entradas son “ pequeñas” podríamos construir algoritmos basados en backtracking que realicen una búsqueda exhaustiva

Ø Sino, podríamos construir soluciones aproximadas,“cercanas” a la mejorsolución, a partir de algoritmos polinomiales.

Algoritmos aproximados y heurísticos

para problemas NP-Hard

¿Cómo resolver problemas NP-HARD?

No pretendemos encontrar la “mejor” solución

sino una “buena” solución.

Algoritmos aproximados

Algoritmos heurísticos

Algoritmos heurísticos versus

algoritmos aproximados Heurística “Hallar, inventar”

Algoritmo HeurísticoProcedimiento que puede producir una solución buena, no muy alejada de la

óptima, o incluso la óptima si somos afortunados!

Algoritmo aproximadoProcedimiento que proporciona una solución aproximada, que si bien no es la

óptima, se puede “medir” cuán cerca está de la óptima.

Ø Los algoritmos heurísticos y los aproximados no garantizan encontrar la

solución óptima

Ø Los algoritmos aproximados establecen una cota de error.

Algoritmos de aproximación para

problemas NP-Hard

Supongamos problemas de optimización, en los que

cada solución factible tiene un costo positivo y se

pretende obtener una solución cercana a la óptima.

Dependiendo del problema, una solución óptima puede

ser definida como el máximo o el mínimo costo de las

soluciones factibles. El problema de optimización

puede ser de maximización o minimización

Algoritmo de aproximaciónUn algoritmo de aproximación está acotado por (n) si para

cualquier entrada de tamaño n, el costo de la solución del

algoritmo de aproximación, para un costo de una solución

factible c y un costo c* de una solución óptima, es:

a) si el problema es de maximización

c / c* ≤ (n) 0 < c ≤ c*

y

b) si el problema es de minimización

c* / c ≤ (n) 0 < c* ≤ c

Es decir, maxmax ( c/c* , c*/c) ( c/c* , c*/c) ≤≤ (n)(n)

Algoritmo de aproximación

maxmax ( c/c* , c*/c) ( c/c* , c*/c) ≤≤ (n)(n)

¿Qué expresa (n)=1?(n)=1?

¿Qué expresa (n) = 2?(n) = 2?

¿¿QuQuéé expresa expresa (n) >> 1?(n) >> 1?

Algoritmo de aproximación

Otra medida es el error relativo definido mediante

c – c* / c

Un algoritmo de aproximación tiene un error relativo

ε(n) si c – c* / c ≤ ε(n).

Un esquema de aproximación para un problema de

optimización tiene como entradas no sólo a una

instancia de un problema sino un valor ε > 0, tal que

para un ε dado el esquema es un algoritmo de

aproximación con un error relativo acotado por ε.

Algoritmo de aproximación

Problema del viajante

Un circuito en un grafo G es una secuencia de arcos

(a1, a2), . . .,(ak−1, ak ), (ak , a1) en G tal que:

Ø ai < > aj para cada i < > j ,

Ø {a1, . . . , ak} es el conjunto de vértices de G.

Costo de un circuito en G:

costo ( ) = Σ (costo((ai , ai+1)) + costo((ak , a1))

1 ≤ i ≤ k-1

Algoritmo de aproximación

Problema del viajante Métrico

Costo de un circuito en G:

costo ( ) = Σ (costo((ai , ai+1)) + costo((ak , a1))

1 ≤ i ≤ k-1

Viajante métrico

Ø Distancia euclideana

Ø costo ( u,w) ≤ costo(u,v) + costo(v,w)

u w

v

Problema del viajante métrico

Algoritmo de aproximación

1. Construir un árbol de recubrimiento de

mínimo costo . Sea T

76

5

43

2

1

76

5

43

2

1 76

76

5

43

2

1

Problema del viajante métrico

Algoritmo de aproximación

2. Doblar cada arco de T para obtener un grafo

euleriano G´.

Problema del viajante métrico

Algoritmo de aproximación

3. Construir un circuito euleriano E sobre G’.

<3,2,1,2,3,4,5,6,5,7,5,4,3>

76

5

43

2

1

3 2 12

3

4565

7

5

4

43 3

1

2

Problema del viajante métrico

Algoritmo de aproximación

4. Construir un circuito C que visite a todos los vértices

usando la desigualdad triangular

<3,2,1,4,5,6,7,3>

76

5

43

2

1

1

3 2

1

4

56

7

Problema del viajante métrico

Algoritmo de aproximación

Propuesta:

Ø Implementar el algoritmo de aproximación

Ø ¿Cuál es la complejidad del algoritmo de

aproximación?

Ø ¿Cuál es el error? ¿Cuánto se acerca a la solución

óptima?

Problema del viajante métrico

Algoritmo de aproximación- Error

COSTO (T) ≤ OPT

COSTO (E) = 2 COSTO (T)

COSTO (C) ≤ COSTO(E)

COSTO (C) ≤ 2 OPT

Se dice que este algoritmo es FACTOR 2, indicando

que a lo sumo duplica el valor de la solución óptima

Algoritmo Heurístico

Problema del coloreo de un grafo

Dado un grafo G = (V,E) y un conjuto finito de

colores S, un coloreo es un mapping

C:V-> S, tal que si existe un arco (v,w) ε E,

luego C(v) < > C(w).

1 2

4

3

5

Algoritmo Heurístico

Problema del coloreo de un grafo

for ( i=2; i <= n; i++)

{c = 1;

while (g.adyacentesColoreados(i, c))

++c;

g.colorear(i, c);

}

1 2

4

35

Algoritmo Heurístico

Problema del coloreo de un grafo

Colorear …

a1 a2 an

b1 b2 bnb3 …

a3 …

Algoritmo Heurístico

Problema del coloreo de un grafo

Secuencia de vértices <a1,a2,..an,b1,b2,..bn>

a1 a2 an

b1 b2 bnb3 …

a3 …

Coloreo óptimo:2 colores

Algoritmo Heurístico

Problema del coloreo de un grafo

Secuencia de vértices <a1,b1,a2,b2,..an,bn>

a1 a2 an

b1 b2 bnb3 …

a3 …

n colores!!!

Algoritmo heurístico

Problema del coloreo del grafo

Depende de la secuencia de vértices usada

la cantidad de colores del coloreo.

for ( i=2; i <= n; i++)

{c = 1;

while (g. adyacentesColoreados(i, c))

++c;

g.colorear(i, c);

}

Algoritmo heurístico

Problema del coloreo del grafo

No se conocen algoritmos de aproximación para el coloreo de un grafo que estén acotados por un factor constante.

Se demostró que si se descubriese un algoritmo de aproximación que en el peor de los casos duplicara la cantidad de colores de la solución óptima, sería posible obtener un coloreo óptimo en tiempo polinomial.

Esto implicaría

P-tiempo = NP-tiempo. !!!!

Así, obtener una “buena” solución, no necesariamente la óptima, para el coloreo puede ser en sí mismo un problema NP-HARD.

Problema del viajante

Se lo conoce como TSP (Traveling Salesman

Problem).

Sea G = (V, E) un grafo orientado y rotulado.

Un ciclo hamiltoniano es un ciclo que contiene a

cada uno de los vértices de G una sóla vez.

Se desea obtener un ciclo hamiltoniano de

mínimo costo.

Problema NP-HARD

Problema del viajante

a

e c

d

b3

7 4

6 5

8

2 6

4 3

Una instancia de TSP

Problema NP-HARD

Problema del viajante

a

e c

d

b3

7 4

6 5

8

2 6

4 3

Una instancia de TSP

Problema del viajante

Algoritmo heurístico

Algoritmo heurístico basado en Prim

Inicializar T;

Inicializar S;

while ( S < > V)

{ elegir un arco (u,v) de mínimo costo/

u ε S, v ε V-S y grado-incidencia (u) < 2;

T = T U {(u,v)};

S = S U {v};

}

Problema NP-HARD

Problema del viajante

3

7 4

6 5

8

2 6

4 3

Circuito para una instancia de TSP

a

a

b

b

c

c

d

d

ee

3

3

6

5

4

COSTO = 21

Problema NP-HARD

Problema del viajante

Algoritmo heurístico basado en Prim

Ø ¿Por qué Prim y no Kruskal?

Ø ¿Por qué es heurístico y no de aproximación?

Problemas NP-Hard

Técnicas de diseño

Algunas técnicas específicas que pueden

aplicarse para resolver problemas NP-HARD

son:

Ø Greedy heurístico

Ø Búsqueda Local

Ø Backtracking

Ø Branch & Bound

Problemas NP-Hard

Técnicas de diseño

TODAS las técnicas de diseño podrían ser usadas o

combinadas para resolver problemas NP-HARD.

Por ejemplo, Sanjeev Arora propone una original

combinación de técnicas para resolver TSP euclideano.

Propone un algoritmo de aproximación que combina

divide y conquista, programación dinámica, greedy y

técnicas específicas para algoritmos geométricos.

Problemas NP-Hard

Búsqueda local

Algoritmos de búsqueda local

Ø Comenzar con una solución al azar.

Ø Aplicar a la solución actual una transformación de

un conjunto de transformaciones para mejorar la

solución. La solución “mejorada” pasa a ser la

solución actual.

Ø Repetir hasta que ninguna transformación en el

conjunto de transformaciones produzca mejoras.

Problemas NP-Hard

Búsqueda local

Algoritmos de búsqueda local

Sugerencia:

1.Aplicar esta técnica para diseñar un algoritmo

para encontrar un árbol de recubrimiento de

mínimo costo.

2.Comparar este algoritmo con los algoritmos de

Prim y Kruskal.

Problemas NP-Hard

Búsqueda local

Los algoritmos de búsqueda local son efectivos como heurísticas

para la resolución de problemas cuya solución exacta requiere un

tiempo exponencial.

Ø Comenzar con un número de soluciones y aplicar transformaciones locales a cada una de ellas, hasta lograr soluciones localmente óptimas, es decir que ninguna transformación del conjunto seleccionado puede mejorarla.

Ø Seleccionar la solución localmente óptima que tiene menor costo. Si somos afortunados podría ser la solución globalmente óptima

Problema del viajante

Búsqueda Local

3

7 4

6 5

8

2 6

4 3a

a

b

e

c

c

d

d

e

b

7

3

6

5

4

COSTO = 25

Solución inicial para una instancia de TSP

Problema del viajante

Búsqueda Local

Generar los circuitos candidatos intercambiando

pares de arcos no adyacentes.a b

dc

Si el costo (a,b) + costo(d,c) > costo(a,c) + costo(b,d)

• eliminar del circuito a los arcos (a,b) y (c,d)

• agregar al circuito los arcos (a,c) y (b,d)

Problema del viajante

Búsqueda Local

a

ec

d b

7

3

6

5

4

COSTO = 25

Posibles transformaciones

Pares de arcos que no son adyacentes y generan soluciones factibles locales

(a,e) (b,d)

(a,e) (d,c)

(e,b) (d,c)

(e,b) (c,a)

(b,d) (c,a)

Cantidad de transformaciones para circuitos de tamaño N es

N (N-3) / 2

Problema del viajante

Búsqueda Local

a

ec

d b

7

3

6

5

4

COSTO = 25

Posibles transformaciones

a

d

e

b

a e

c d

3 6

7

6

7

5

87

Costo = 21

Costo = 22

Problema del viajante

Búsqueda Local

a

ec

d b

7

3

6

5

4

COSTO = 25

Posibles transformaciones

e

c

b

d

e b

a c

3

3

5

4

46

8 3

Costo = 25

Costo = 25

Problema del viajante

Búsqueda Local

a

ec

d b

7

3

6

5

4

COSTO = 25

Posibles transformaciones

b

a

d

c

a

d e

b

c

Costo = 25

Costo = 21

4 7

6

4

43

3

6

5

Problema del viajante

Búsqueda Local

Repetir para la solución localmente óptima

a

d e

b

c

43

5

Posibles transformaciones

(a,b) (e,d)

(a,b) (d,c)

(b,e) (d,c)

(b,e) (c,a)

(e,d) (c,a)

6

3

Problema del viajante

Búsqueda Local

¿Qué cantidad de transformaciones?

Para que sea “tratable” la cantidad de

transformaciones debe ser de orden polinomial.

Transformar solamente soluciones localmente

óptimas y acotar las transformaciones a un

orden polinomial no nos garantiza llegar a la

solución óptima.

Problema del viajante

Búsqueda Local

Nuestra estrategia sólo transforma si “mejora”.

La solución óptima puede llegar a partir de

transformaciones que “empeoran” el costo!!

Pero buscaremos una buena solución en

promedio…

Problema del viajante

Búsqueda Local

Costo = 25 Costo = 27

Costo = 19

a

d c

b

e

73

6

5

4

a

d b

c

e

74

6 4

6

a

e b

c

d

24

6

4

3

4

6

“empeora”

“HACIA LA ÓPTIMA”

…

Problema del viajante

Búsqueda Local

Consideraciones

Los algoritmos heurísticos basados en esta

técnica deben ser de complejidad temporal

polinomial

ØNo se pueden generar todas las transformaciones

posibles!! La complejidad sería exponencial.

ØLos algoritmos que transforman soluciones factibles

deben ser polinomiales, de orden bajo.