0

Buenos días, estoy intentando hacer el algoritmo de Ramificación y Poda, pero no llego a lograr la Poda. Me sigue recorriendo todos los nodos y una vez recorridos, lo maximiza.

Aquí esta el arbol resultante introducir la descripción de la imagen aquí

public class mochila {

private List resultado = new ArrayList();

public List recursividad(Integer indice,Integer peso,List lista){

    System.out.println(indice+" -> "+lista); //Ver todo el arbol
    if(indice == Test.lista.size() || peso == Test.capacidad){

        if(resultado.size() == 0 || lista.stream().mapToInt(x->x.getPrecio()).sum() > resultado.stream().mapToInt(x->x.getPrecio()).sum()){
            resultado.clear();
            resultado.addAll(lista);
        }

    }else{
        for(Boolean a : getAlternativa(indice,peso,lista)){ //Las alternativas

            if(a == true){
                peso += Test.lista.get(indice).getPeso();
                lista.add(Test.lista.get(indice));
            }
            recursividad(indice+1,peso,lista);
            if(a == true){
                peso -= Test.lista.get(indice).getPeso();
                lista.remove(Test.lista.get(indice));
            }
        }
    }
      return resultado;
  }

  private List getAlternativa(Integer indice,Integer peso,List lista){
    List res = new ArrayList();
    if((peso+Test.lista.get(indice).getPeso()) <= Test.capacidad){
            res.add(true);
    }
    res.add(false);
    return res;
  }

}

Creo que lo conseguido es el algoritmo BackTracking pero Ramificación y poda es una variante del Backtracking mejorado sustancialmente.

6
  • ¿Cómo se supone que haces una poda en el algoritmo de la mochila?¿Cuál sería el criterio? Hasta donde recuerdo, para hacer la poda tienes un criterio (en fino, heurística) que te dice que soluciones parciales son más prometedoras y cuales menos, y "podas" las que parecen (recalco, parecen) peores según ese criterior. ¿Qué criterio usarías aquí?
    – SJuan76
    el 11 jul. 2017 a las 13:15
  • @SJuan76 Efectivamente, ese es el problema. No sabría cual es ese criterio. ¿Alguna ayuda?
    – user38325
    el 11 jul. 2017 a las 13:27
  • Lo único que tienes, en cualquier estado, es el peso que te falta por llenar, por lo que el criterio sería el mismo problema de la maleta de nuevo... Si hubiera un criterio válido para determinar la "bondad" de un estado (más allá de que, si se pasa de peso, no es un estado válido), significaría que con ese mismo criterio podrías resolver el propio problema original, con lo cual no necesitarías hacer todo el backtracking...
    – SJuan76
    el 11 jul. 2017 a las 13:30
  • @SJuan76 no he llegado a entenderlo, puedes representarmelo aunque sea una parte en codigo?
    – user38325
    el 11 jul. 2017 a las 13:33
  • La respuesta es que la heurística es el mismo algoritmo de la mochila. Si tienes una mochila de 100 kilos que tiene ya 30 kilos, lo que te queda es el algoritmo de la mochila con 70 kilos. Y por eso no es muy útil... o lo que es lo mismo, que éste no es un buen problema para aplicar la poda.
    – SJuan76
    el 11 jul. 2017 a las 13:35

0

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.