Monografías Plus »

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



Monografias.com
Problemas de Decisión y Optimización Un problema de decisió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 solución al problema es una asignación de valores a todas las variables que satisface las restricciones SOL es el conjunto de soluciones
Monografias.com

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
Monografias.com

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:
Monografias.com

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:
Monografias.com

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:
Monografias.com

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
Monografias.com

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)
Monografias.com

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)
Monografias.com

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
Monografias.com

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;
Monografias.com

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
Monografias.com

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
Monografias.com

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
Monografias.com

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
Monografias.com

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
Monografias.com

¿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