martes, noviembre 16, 2010

Problema de la mochila - Backtracking

Resolver el problema de la mochila seleccionando los elementos más caros en primer lugar, o los más livianos, no necesariamente garantiza llegar a una solución ideal, pues es posible que otras combinaciones de elementos produzcan mejores resultados.

Para obtener la solución ideal se deben revisar todas las alternativas; y en este caso, se puede utilizar una estrategia de retroceso, o backtracking. En esta implementación, iniciando en el primer elemento del almacén, se evalúan dos posibilidades, agregar o no agregar el elemento a la mochila, y llamando recursivamente el método hasta que la mochila se llena; una vez llena, se compara con el máximo calculado anteriormente y se guarda la lista de elementos que genere el mayor valor en la mochila. Esta solución requiere una mochila temporal (tmpMochila) que se crea en forma similar a la mochila definitiva, y dos métodos que calculen el valor y el peso acumulado de dicha mochila temporal. La implementación queda entonces de la siguiente manera:

// Solución por backtracking
    public void resolverProblemaBT(int posicion) {
        double  pesoMochila=getPeso(tmpMochila);    // peso de la solucion temporal
        double valorMochila=getValor(tmpMochila);   // valor de la solucion temporal

        if( posicion>=almacen.size() ) {            // si ya se tuvieron en cuenta todos los elementos
            if(valorMochila>valorMaximo) {          // si el valor es mayor que el máximo anterior
                valorMaximo=valorMochila;           // se actualiza el valor mayor
                mochila.clear();
                mochila.addAll(tmpMochila);
            }
            return;
        }
        Elemento e = almacen.get(posicion);
        // Si el elemento se puede agregar, se envía a la mochila temporal
        if(pesoMochila + e.peso <= pesoMaximo) {
                tmpMochila.add(e);                  // Se agrega a la mochila temporal
                resolverProblemaBT(posicion+1);     // se revisa para el siguiente elemento
                tmpMochila.remove(e);               // Se retira el elemento
        }
        // Si no se pudo agregar, o ya se agregó y se retiró, se revisa para el siguiente
        resolverProblemaBT(posicion+1);
    }

    double getPeso(List<Elemento> tmp) {
        double respuesta=0;
        for(Elemento e: tmp) respuesta+=e.peso;
        return respuesta;
    }

    double getValor(List<Elemento> tmp) {
        double respuesta=0;
        for(Elemento e: tmp) respuesta+=e.valor;
        return respuesta;
    }

El método de invocación quedaría de la siguiente manera (no olvidar crear el vector tmpMochila como un Vector de objetos de tipo Elemento):

    public static void main(String[] args) {
        ProblemaMochila pm = new ProblemaMochila(20);
        pm.resolverProblemaBT(0);       // Inicia en el primer elemento disponible
        pm.mostrarMochila();
    }

Este método devuelve la solución óptima, puesto que evalúa todas las posibilidades, sin embargo, cuando el número de elementos disponibles es relativamente grande, la cantidad de operaciones a realizar hace prácticamente imposible utilizar el algoritmo, ya que su complejidad es del orden de O(N!), donde N es la cantidad de elementos del almacén.

6 comentarios:

Anónimo dijo...

Serias tan amable de mandarme el codigo completo, y si lo tienes por ramificacion y poda te agradeceria mucho.

JorgeP dijo...

Hola buenos días,
En este post está la definición del modelo para resolver el problema y una primera aproximación a la respuesta: http://jorgep.blogspot.com/2010/11/problema-de-la-mochila.html
En este otro posta está la solución utilizando otra estrategia de algoritmos voraces: http://jorgep.blogspot.com/2010/11/problema-de-la-mochila-algoritmos.html

Anónimo dijo...

Gracias bate, nos salvaste de una amanecida xD

Luis Gonzalo Castillo Márquez dijo...

tengo este problema en la Solución por backtracking

ProblemaMochila.getPeso(ProblemaMochila.java:103)

JosueR dijo...

Disculpa, tengo una duda, tu variable del maximo anterior, if(valorMochila>valorMaximo), "valorMaximo" que valor en sí esta representando o donde lo declaras, ya que no lo encuentro en ambos códigos de tu blog....

GRACIAS

JMonda dijo...

Buenos días

El blog esta desactualizado y en mi opinión abandonado pero escribo esto para las nuevas personas.
El código mostrado arriba esta incompleto.

El algoritmo BackTracking lo que hace es ir hacia delante y si no encuentra la solución vuelve hacia atras.

Tenéis un mejor ejemplo en http://jmonda.com/blog_post.php?n=algoritmo-backtracking-problema-mochila

Saludos.

Publicar un comentario

LinkWithin

Related Posts Plugin for WordPress, Blogger...

Calificar