Esquema voraz

Bases del esquema voraz

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.

Esquema voraz

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) $\wedge$ z $\neq \emptyset$ ) 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.

Ejemplo: Mochila [0,1]

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

Criterio de selección

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}

Algoritmo voraz

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!!