3

Antes que nada, durante todo este tiempo atrás he estado usando este modelo para resolver mis problemas con backtracking.

Es un modelo de backtraking realizado por mi universidad https://github.com/migueltoro/apuntesjava/blob/master/SoftwareDelLibro/src/us/lsi/bt/AlgoritmoBT.java.

        private void bt() { 
            if(estado.isFinal()){           
                actualizaSoluciones();
                if(AlgoritmoBT.soloLaPrimeraSolucion  && solucion!=null) exito = true;
                if(!AlgoritmoBT.soloLaPrimeraSolucion  && soluciones.size()>=AlgoritmoBT.numeroDeSoluciones) exito = true;
            } else {
                    for(A a: filtraRandomize(estado,estado.getAlternativas())){  
                            if(isMin() && estado.getObjetivoEstimado(a) >= mejorValor) continue;
                            if(isMax() && estado.getObjetivoEstimado(a) <= mejorValor) continue;
                            estado.avanza(a); 
                            bt();  
                            estado.retrocede(a); 
                            if (exito) break;
                    }
            }
       }

Ejemplo: Como resolver el problema de las reinas con el modelo mencionado anteriormente https://github.com/migueltoro/apuntesjava/blob/master/SoftwareDelLibro/src/us/lsi/bt/reinas/EstadoReinasBT.java


Una vez leído lo anterior, comienzo con mi duda. Estoy intentando deshacerme del modelo mencionado anteriormente para realizar mis problemas mediante backtraking, he estado intentando realizar el siguiente problema:

Tengo una lista con todos los grupos(de cantantes(Test.lista)) que puedo seleccionar, tengo 9.0€ de presupuesto para contratar los grupos con el mayor numero de votos (Maximizar votos).

Tengo bastante código realizado de lo que quiero conseguir:

Grupos:

    public class Objeto{

        private Integer codigo;
        private String nombre;
        private Integer votos;
        private Double precio;
        private Boolean cerca;

        public Objeto(Integer codigo, String nombre, Integer votos, Double precio, Boolean cerca) {
            this.codigo = codigo;
            this.nombre = nombre;
            this.votos = votos;
            this.precio = precio;
            this.cerca = cerca;
        }

        public Integer getCodigo() {
            return codigo;
        }

        public String getNombre() {
            return nombre;
        }

        public Integer getVotos() {
            return votos;
        }

        public Double getPrecio() {
            return precio;
        }

        public Boolean getCerca() {
            return cerca;
        }

        @Override
        public String toString() {
            return "Objeto [codigo=" + codigo + ", nombre=" + nombre + ", votos=" + votos + ", precio=" + precio
                    + ", cerca=" + cerca + "]";
        }

    }

Test:

    import java.util.ArrayList;
    import java.util.List;

    public class Test {

        public static List<Objeto> lista = new ArrayList<Objeto>();
        public static Double presupuesto = 9.0;

        public static void main(String[] args){
            lista.add(new Objeto(1,"Caracola1",100,9.0,true));
            lista.add(new Objeto(2,"Caracola2",2,4.0,true));
            lista.add(new Objeto(3,"Caracola3",3,5.0,false));

            BackTraking a = new BackTraking();
            System.out.println(a.recursividad(0));
        }
    }

BackTraking:

    import java.util.ArrayList;
    import java.util.List;

    public class BackTracking {

        public List<Objeto> recursividad(Integer indice){
            List<Objeto> res = new ArrayList<Objeto>();

            if(indice == Test.lista.size()-1){
                res.add(Test.lista.get(indice));
            }else{
                for(Objeto a : getAlternativas(res)){

                    res.add(a);
                    recursividad(indice+1);
                }
            }

            return res;
        }

        public List<Objeto> getAlternativas(List<Objeto> lista) {//Todos los objetos que no sobrepasen el presupuesto y no esten en la lista
            List<Objeto> res = new ArrayList<Objeto>();
            Double coste = lista.stream().mapToDouble(x->x.getPrecio()).sum();
            for(Objeto a : Test.lista){
                if(!lista.contains(a) && (coste+a.getPrecio()) <= Test.presupuesto){
                    res.add(a);
                }
            }
            return res;
        }

    }

Solución obtenida :(

    [
    Objeto [codigo=2, nombre=Caracola2, votos=2, precio=4.0, cerca=true]
    , 
    Objeto [codigo=3, nombre=Caracola3, votos=3, precio=5.0, cerca=false]
    , 
    Objeto [codigo=1, nombre=Caracola1, votos=100, precio=9.0, cerca=true]
    ]

Solución que tendría que salir :)

El resultado obtenido tendría que ser new Objeto(1,"Caracola1",100,9.0,true) puesto que cumple que tiene 9.0€ de precio y el que mayor numero de votos tiene (100).

14
  • Hola.. tu publicación contiene demasiada información y es confusa. por favor expresa el problema que tienes claramente. Por favor consulta la ayuda para mejorarla.
    – gbianchi
    el 30 may. 2017 a las 13:41
  • @gbianchi ¿Que parte del post te parece confusa?
    – user38325
    el 30 may. 2017 a las 13:42
  • ni se que estas preguntando y que tienen que ver todos los algoritmos mencionados
    – gbianchi
    el 30 may. 2017 a las 14:01
  • @gbianchi Es muy facil, he intentado resolver mediante backtracking un problema lo que pasa que no se como maximizarlo mediante una propiedad.
    – user38325
    el 30 may. 2017 a las 14:02
  • 1
    Señor usuario, le informamos que porfin vemos a alguien que si lee la guia de "como preguntar" te felicito :D el 30 may. 2017 a las 14:34

1 respuesta 1

3

Analicemos tu funcion de recursividad:

public List<Objeto> recursividad(Integer indice){
    List<Objeto> res = new ArrayList<Objeto>(); <- Nueva lista en cada entrada
    if(indice == Test.lista.size()-1){ 

Si el indice es menor al tamaño de test.lista para todos los casos menos el ultimo

 res.add(Test.lista.get(indice)); 

Agrego el objeto a res, que se va a perder cuando salga por que es local

}else{

Si no es el ultimo de la lista... no se porque el ultimo lo agregas siempre.. eso es raro

for(Objeto a : getAlternativas(res)){

En teoria estas comparando los valores, sin embargo tu set de pruebas no tiene nadie que se pase...

res.add(a);

Agregas todos los objetos que son mas baratos que tu presupuesto.. y los votos donde los miras?

recursividad(indice+1);
                }
            }

            return res;
        }

Lo que veo en todo esto es lo siguiente.. No entiendo como se puede calcular lo que queres por backtracking, no hay backtracking aca, es una simple busqueda de menor valor. Supongamos que se puede por backtracking, tu algorimo deberia probar caminos (para ir y volver, no los veo aca) y comparar las dos cosas que necesitas..

Me parece que este no es el problema para aprender backtracking, y a tu algoritmo le faltan muchas cosas.

10
  • 1
    ¿te falta tabular los comentarios?
    – eferion
    el 30 may. 2017 a las 14:30
  • Cierto, he estado buscando problemas como el de la mochila para basarme y aprender, pero en los encontrado no realizaban llamada recursiva, por lo cual he intentado hacerlo yo. Voy a seguir investigando a ver si encuentro un problema y me sirve de ayuda. MIL GRACIAS!
    – user38325
    el 30 may. 2017 a las 14:31
  • @Knowledge si la respuesta te sirvio dala por aceptada para cerrar la pregunta.. estudia backtracking buscando un problema de camino minimo, que son los basicos...
    – gbianchi
    el 30 may. 2017 a las 14:32
  • @eferion estaban a proposito para que se notaran los problemas.. alguna idea mejor?
    – gbianchi
    el 30 may. 2017 a las 14:33
  • Yo creo que si quitas los símbolos de los comentarios // se va a leer igual de bien y no dará la sensación de que se te ha ido la tabulación. Otra solución que yo aplico a veces es poner numeros en cada linea a comentar y luego explicarlo en una lista numerada
    – eferion
    el 30 may. 2017 a las 14:34

Tu Respuesta

Al pulsar en “Publica tu respuesta”, muestras tu consentimiento a nuestros términos de servicio, política de privacidad y política de cookies