Esquema voraz
Last updated
Last updated
La estrategia voraz se apoya en unas bases que podemos resumir del siguiente modo:
En cada decisión debemos elegir de un conjunto de candidatos en base a algún criterio razonable.
Una función de selección de los candidatos determinará en cada momento cuál es el mejor candidato posible.
Utilizamos dos conjuntos SOLUCIÓN y CANDIDATOS.
A medida que vamos tomando decisiones, el conjunto de CANDIDATOS se reduce y el conjunto SOLUCIÓN puede ir aumentando (aumentará si es factible; sino, no).
Una función FACTIBLE nos permitirá determinar si la decisión en curso (MEJOR CANDIDATO ACTUAL) incorporada a la solución que llevamos hasta ese momento (solución parcial) hace que se sigan cumpliendo las restricciones del problema. Si la respuesta es SI, la decisión actual se añade a la solución; si la respuesta es NO, no se añade a la solución, por tanto, se rechaza.
Una función ES_SOLUCIÓN nos permitirá determinar en cada momento si el conjunto solución resuelve el problema planteado.
Función Voraz ( x : T1 ) retorna ( y : T2 )
var z : T´1, S : T2, decision : T3 fvar
z = prepara (x)
S = solucion_vacía
mientras ( ¬es_solucion (S) z ) hacer
decision = selecciona_siguiente (z)
z = elimina(z, decision)
si factible (S, decision) entonces
S = añade (S, decision)
fsi
fmientras
si es_solucion (S) entonces retorna S sino retorna solucion_vacía fsi
ffuncion
Funcion prepara ( x : T1 ) retorna ( z : T´1 )
Comportamiento: Devuelve una estructura transformada de los datos de entrada x, diseñada para facilitar la aplicación del criterio de selección adoptado.
Funcion es_solucion ( S : T2 ) retorna ( b : booleano )
Comportamiento: Devuelve cierto si la solución obtenida es solución del problema planteado; falso, en caso contrario.
Función selecciona_siguiente ( z : T´1 ) retorna ( y : T3 )
Comportamiento: Selecciona uno de los elementos de z según cierto criterio.
Funcion elimina ( z : T´1; decisión : T3 ) retorna ( z : T´1 )
Comportamiento: Actualiza el conjunto z de candidatos a considerar, devolviendo un nuevo conjunto al que ya no pertenece la decisión elegida.
Funcion factible ( S: T2, decisión : T3 ) retorna ( b : booleano )
Comportamiento: Devuelve cierto si la inclusión de la decisión en la solución parcial conduce a una solución que no viola las restricciones, es decir, si progresa como una solución factible; falso, en caso contrario.
Funcion añade ( S : T2, decisión : T3 ) retorna ( S : T2 )
Comportamiento: Devuelve la combinación de la decisión con la solución parcial anterior.
Se dispone de n objetos con sus correspondientes pesos (P[1..n]) y beneficios (B[1..n]) y tenemos una mochila con una capacidad C. Se trata de determinar qué objetos y en qué proporción se introducen en la mochila con la finalidad de conseguir el máximo valor.
Solución como secuencia de decisiones: X1X2 …Xn
donde Xi es la decisión tomada para el objeto i-ésimo. Su valor indicará la porción del objeto que se introduce, esto es Xi pertenece a [0,1].
De tal forma que la secuencia óptima de decisiones será aquella X1X2 …Xn tal que
Ejemplo: n=3 C=20 P[1..3]={18, 15, 10} B[1..3]={25, 24, 15}
Criterio 1: MÁXIMO BENEFICIO
Criterio 2: MÍNIMO PESO
Criterio 3: MAYOR Bi/Pi (Ratio)
Ratio[1..3]={1.39, 1.6, 1.5}
Función Mochila_con_particion (N, C:entero, P[1..N], B[1..N]: vector de enteros)
retorna ( Bmax : real, X[1..N]: vector de reales )
var capacidad, i : entero; beneficio: real; X[1..n]:vector de reales fvar
capacidad = C
beneficio = 0
para i=1 hasta N hacer
X[i]=0.0
fpara
mientras capacidad ≠ 0 hacer # bucle voraz
i = posición de aquel objeto no seleccionado aún cuya ratio Bi/Pi sea mayor
si P[i] ≤ capacidad entonces
X[i]=1
capacidad = capacidad - P[i]
beneficio = beneficio + B[i]
sino
X[i] = capacidad / P[i]
capacidad = 0
beneficio = beneficio + B[i] * X[i]
fsi
fmientras
retorna (beneficio, X[1..N])
ffunción
Ejemplo utilizado en Programación Dinámica y Vuelta atrás (Backtracking).-
n=3 C=15 P[1..3]={5, 6, 9} B=[1..3]={ 24, 40, 38 }
Criterio 3: MAYOR Bi/Pi
Solución à (X1, X2, X3) = (1, 1, 0) Beneficio: 64 ¡¡ SOLUCIÓN NO ÓPTIMA!!
Criterio 1: MÁXIMO BENEFICIO
Solución à (X1, X2, X3) = (0, 1, 1) Beneficio: 78 ¡¡ SOLUCIÓN ÓPTIMA!!