Run Backtracking algorithm

3

First of all, during all this time ago I have been using this model to solve my problems with backtracking.

It's a backtraking model made by my university link .

        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;
                    }
            }
       }

Example: How to solve the queens problem with the model mentioned above   link

Once I have read the above, I begin with my doubt. I'm trying to get rid of the model mentioned above to make my problems through backtraking, I've been trying to do the following problem:

I have a list with all the groups (of singers (Test.list)) that I can select, I have 9.0 € of budget to contract the groups with the highest number of votes (Maximize votes).

I have enough code made of what I want to achieve:

Groups:

    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;
        }

    }

Solution obtained: (

    [
    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]
    ]

Solution that would have to leave:)

The result obtained would have to be new Objeto(1,"Caracola1",100,9.0,true) since it fulfills that it has 9.0 € of price and the one that greater number of votes has (100).

    
asked by 30.05.2017 в 15:09
source

1 answer

3

Let's analyze your recursion function:

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

If the index is less than the test size. list for all cases except the last

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

I add the object to res, which will be lost when it comes out because it is local

}else{

If it's not the last one on the list ... I do not know why the last one is always added ... that's weird

for(Objeto a : getAlternativas(res)){

In theory you are comparing the values, however your set of tests has no one to pass ...

res.add(a);

Do you add all the objects that are cheaper than your budget ... and the votes where you look at them?

recursividad(indice+1);
                }
            }

            return res;
        }

What I see in all this is the following .. I do not understand how you can calculate what you want backtracking, there is no backtracking here, it is a simple search of lesser value. Suppose you can by backtracking, your algorithm should try paths (to go and return, I do not see them here) and compare the two things you need ..

I think this is not the problem to learn backtracking, and your algorithm is missing many things.

    
answered by 30.05.2017 / 16:27
source