Problemas de Decisión y Optimización (PPT)

Una solución al problema es una asignación de valores a todas las variables que satisface las restricciones

SOL es el conjunto de soluciones

Ej. 1: n-reinas
Poner n reinas en un tablero n x n de manera que no se ataquen

(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 5
(Gp:) 6
(Gp:) 7
(Gp:) 8
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 5
(Gp:) 6
(Gp:) 7
(Gp:) 8

Ej. 1: n-reinas
Formulación 1:
Variables: X={xij}
xij ?{0,1} no hay/hay reina en (i,j)
Restricciones:

Formulación 2:

Variables: X={xi}
xij ?{1,..,n} la reina de la fila i está en la columna j
Restricciones:

Ej. 2: k-coloreado
Dado un grafo G=(V,E) no dirigido, y k colores, asignar a cada vértice un color de manera que vértices adyacentes no tengan el mismo color. Sea V=(1,2,…,n).

Formulación:
Variables: X={x1, x2,…, xn}
xi ?{1,2,…,k} color del vértice i
Restricciones:

Ej. 3: Circuito Hamiltoniano
Dado un grafo G=(V,E) encontrar un ciclo que pase por todos los vértices exactamente una vez. Sea V=(1,2,…,n).

Formulación:
Variables: X={x1, x2,…, xn}
xi ?{1,2,…,n} vértice visitado en la etapa i
Restricciones:

Problemas de Decisión y Optimización
Un problema de optimización se puede expresar como:
Un conjunto de variables X=(x1,x2,…,xn)
Cada variable xi tiene un dominio Di =(v1,v2,…,vm) con los valores que se le pueden asignar
Un conjunto de restricciones
Una función objetivo, F(X), a maximizar o minimizar

Una solución al problema es una asignación de valores a todas las variables que satisface las restricciones

Una solución óptima es una solución maximal (o minimal) respecto a la función objetivo

Ej. 4: Arboles de expansión mínima (MSTs)
Dado un grafo G=(V,E) no dirigido, conexo y etiquetado, encontrar un árbol de expansión cuya suma de etiquetas sea mínima. Sea E=(1,2,…,n).

Formulación:
Variables: X={x1, x2,…, xn}
xi ?{0,1} Escojo o no la arista i
Restricciones: El grafo inducido por las aristas escogidas es conexo y sin ciclos
Función Objetivo: F(X)= ? xn etiq(i)

Ej. 5: Problema del viajante de comercio (TSP)
Dado un grafo G=(V,E) dirigido, conexo y etiquetado, encontrar un circuito hamiltoniano con suma de etiquetas mínima. V=(1,2,…,n)

Formulación:
Variables: X={x1, x2,…, xn}
xi ?{1,2,…,n} vértice visitado en la etapa i
Restricciones:

Función Objetivo: F(X)= ? etiq(xi, x(i+1)%2)

Algoritmos voraces
Introducción y 1er. ejemplo
El problema de la mochila
Caminos mínimos en grafos
Árboles de recubrimiento de coste mínimo
Códigos de Huffman
El problema de la minimización del tiempo de espera
Un problema de planificación de tareas a plazo fijo
Heurísticas voraces
Coloreado de grafos
El problema del viajante de comercio

El esquema voraz:Introducción
El esquema voraz se aplica normalmente a problemas de decisión y optimización
Procede por pasos:
En cada paso se toma una decisión de la que estamos seguros.
Las decisiones tomadas nunca se reconsideran
el algoritmo termina cuando no quedan decisiones por tomar.
el algoritmo es correcto si podemos garantizar que la solución encontrada es siempre óptima;

Se trata de devolver una cantidad de dinero con el menor número posible de monedas.
Se parte de:
un sistema monetario (v1,v2,…,vn), y suficientes monedas de cada tipo
un importe a devolver C.
Formulación:
Variables: X=(x1,x2,…,xn),
xi ?{0,1,..,C} número de monedas de tipo i
Restricciones: S xi vi = C
Función objetivo: S xi
Criterio voraz:
Tomar el máximo de monedas (sin sobrepasar C) en orden decreciente de valor
Problema del cambio en monedas

función cambia(importe:nat;
valor:vector[moneda] de nat)
devuelve vector[moneda] de nat
variable mon:moneda;
cambio:vector[moneda] de nat
principio
para todo mon en moneda hacer
cambio[mon]:=0
fpara;
para mon:=M25 hasta M1 hacer
mq valor[mon]=importe hacer
cambio[mon]:=cambio[mon]+1;
importe:=importe-valor[mon]
fmq
fpara;
devuelve cambio
fin
tipo moneda=(M25,M10,M5,M1)
Cambio de monedas

Ejercicios :

Demostrar la corrección del algoritmo.

Demostrar, buscando contraejemplos, que el algoritmo no es óptimo si se añade un nuevo tipo de moneda de 12 pesetas o si se elimina alguno de los tipos existentes.
Demostrar que, en esas condiciones, el algoritmo puede incluso no encontrar solución alguna aunque ésta exista.

¿Es el método de ordenación por selección directa un algoritmo voraz?

Cambio de monedas

El problema de la mochila
Sean:
n objetos fraccionables.
(p1,…,pn), pesos.
(b1,…,bn), beneficios.
mochila con capacidad C.
Problema: poner en la mochila aquellos objetos que maximicen el beneficio, sin sobrepasar la capacidad de la mochila
Formulación:
Variables: X=(x1,x2,…,xn),
0 ? xi ? 1 “porción que tomo del objeto i”
Restricciones: S xi pi ? C
Función objetivo: F(X) = S xi bi

Observaciones:
Podemos suponer p1+???+pn>C.
Podemos poner un “=“ en la restricción

Ejemplo:
n=3 C=17
(b1,b2,b3)=(40,36,22)
(p1,p2,p3)=(15,12,8)

Tres soluciones factibles:
El problema de la mochila
(Gp:) (x1,x2,x3)

(i) (1,1/6,0) 46
(ii) (0,3/4,1) 49
(iii) (0,1,5/8) 49’75
(Gp:) 1=i=3
(Gp:) ? bixi

¿Cuál es un criterio voraz correcto?
Volvamos al ejemplo:
1ª estrategia: elegir el objeto con mayor beneficio total (el primero).Sin embargo, la mochila se llena muy rápidamente con poco beneficio total.
2ª estrategia: elegir el objeto que llene menos la mochila, para acumular beneficios de un número mayor de objetos. Sin embargo, es posible que se elija un objeto con poco beneficio simplemente porque pesa poco.
3ª estrategia, que es la óptima, es tomar siempre el objeto que proporcione mayor beneficio por unidad de peso.

Los algoritmos resultantes de aplicar cualquiera de las dos primeras estrategias también son voraces, pero no calculan la solución óptima.
El problema de la mochila