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