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.

7 comentarios:

  1. Anónimo4:57 p.m.

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

    ResponderBorrar
  2. 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

    ResponderBorrar
  3. Anónimo6:06 p.m.

    Gracias bate, nos salvaste de una amanecida xD

    ResponderBorrar
  4. tengo este problema en la Solución por backtracking

    ProblemaMochila.getPeso(ProblemaMochila.java:103)

    ResponderBorrar
  5. 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

    ResponderBorrar
  6. 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.

    ResponderBorrar

Multiprocesamiento recursivo en JAVA 7

Una de las estrategias de diseño de algoritmos más comunes es la de "divide y vencerás", en la cual, un problema de tamaño relativ...