The Blog

Algoritmo BackTracking - Alquiler de coche

2017-06-18 17:36:37

Dentro de las técnicas de diseño de algoritmos, el método de Vuelta Atrás (del inglés Backtracking) es uno de los de más ámplia utilización, en el sentido de que puede aplicarse en la resolución de un gran número de problemas, muy especialmente en aquellos de optimización.
Antes de empezar con BackTracking es recomendable que mires el video https://www.youtube.com/watch?v=vdVpRjO7g84 hasta el minuto 8:30 para entender correctamente como funciona BackTracking y el árbol resultante.

Funcionamiento BackTracking:


Enunciado:


Test:

public class Test {

    public static List objetos = new ArrayList();

    public static void main(String[] args){

    	objetos.add(new Coche("Ibiza",TipoCoche.Utilitario,TestAuto.cuarto,10000));
    	objetos.add(new Coche("Fiesta",TipoCoche.Utilitario,TestAuto.segundo,10000));
    	objetos.add(new Coche("Touran",TipoCoche.Familiar,TestAuto.tercero,17000));
    	objetos.add(new Coche("Altea",TipoCoche.Familiar,TestAuto.cuarto,17000));
    	objetos.add(new Coche("Meriva",TipoCoche.Familiar,TestAuto.otro,16000));
		objetos.add(new Coche("Astra",TipoCoche.Compacto,TestAuto.tercero,14000));
		objetos.add(new Coche("Leon",TipoCoche.Compacto,TestAuto.otro,14000));
		objetos.add(new Coche("Insignia",TipoCoche.Berlina,TestAuto.primero,24000));
		objetos.add(new Coche("Mondeo",TipoCoche.Berlina,TestAuto.tercero,24000));
		objetos.add(new Coche("C-Max",TipoCoche.Familiar,TestAuto.segundo,16000));

		List lista1 = new BackTracking().recursividad(0,objetos,
															new ArrayList(),new ArrayList(),0,65000);
		System.out.println("Presupuesto usado: "+lista1.stream().mapToInt(x -> x.getCoste()).sum()+" "+lista1);
    }
}

BackTracking:
public class BackTracking {

	public List recursividad(Integer indice,List objetos, //Propiedades individual
									List lista,List resultado,Integer presupueto,Integer presupuestoInicial){ //Propiedades compartidas
		
		System.out.println(indice+" : "+presupueto+" -> "+lista); //Ver todo el arbo
    	if((indice == objetos.size() || presupueto == presupuestoInicial) && getPrimero(lista)){ //Cuando haya recorrido toda la lista o haya gastado todo el presupuesto

    		//Obtengo la lista con mayor numero de votos
    		if(resultado.size() == 0 || lista.stream().mapToDouble(x->x.getSatisfaccionClientes()).sum() > resultado.stream().mapToDouble(x->x.getSatisfaccionClientes()).sum()){
        		resultado.clear(); //Elimino la lista que hubiese antes
        		resultado.addAll(lista); //Añado la nueva lista
	        }
 
	   }else{
	        	for(Boolean a : getAlternativa(objetos,indice,presupueto,presupuestoInicial)){ //Las alternativas

	        		if(a == true){
	        			presupueto+=objetos.get(indice).getCoste(); //Añado
		        		lista.add(objetos.get(indice));
	        		}
	        	    recursividad(indice+1,objetos,lista,resultado,presupueto,presupuestoInicial);
	        		if(a == true){
	        			presupueto-=objetos.get(indice).getCoste(); //Elimino
		        		lista.remove(objetos.get(indice));
	        		}
	        	}
        }
        return resultado;

    }
    
    public List getAlternativa(List objetos,Integer indice,Integer presupueto,Integer presupuestoInicial){
		List res = new ArrayList();
		if(indice >= 0 && indice < objetos.size()){
			if((presupueto + objetos.get(indice).getCoste()) <= presupuestoInicial){
				res.add(true);
			}
		    res.add(false);
		}
		return res;
    }
    
	//Al menos un coche de cada tipo de coche
    public Boolean getPrimero(List lista){
    	    Boolean res = false;
    	    Integer num1= 0;
    	    Integer num2= 0;
    	    Integer num3= 0;
    	    Integer num4= 0;
    	    for(Coche a : lista){
    	    	   if(a.getTipoCoche().equals(Coche.TipoCoche.Berlina)){
    	    		   num1++; 
    	    	   }
    	    	   if(a.getTipoCoche().equals(Coche.TipoCoche.Compacto)){
    	    		   num2++; 
    	    	   }
    	    	   if(a.getTipoCoche().equals(Coche.TipoCoche.Familiar)){
    	    		   num3++; 
    	    	   }
    	    	   if(a.getTipoCoche().equals(Coche.TipoCoche.Utilitario)){
    	    		   num4++; 
    	    	   }
    	    }
	    	if(num1 >= 1 && num2 >= 1 && num3 >= 1 && num4 >= 1){
	    	    res = true;
	    	}
    	    return res;
    }
	
}

Coche:
public class Coche {

	public static enum TestAuto {
		primero, segundo, tercero, cuarto, otro
	};

	public static enum TipoCoche {
		Utilitario, Compacto, Familiar, Berlina
	};

	private String id;
	private TipoCoche tipo;
	private TestAuto test;
	private Integer coste;

	public Coche(String id,TipoCoche tipo,TestAuto test,int coste) {
		this.id = id;
		this.tipo = tipo;
		this.test = test;
		this.coste = coste;
	}

	@Override
	public String toString() {
		return "<"+id+", " + tipo + ", "+getCoste()+">";
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((id == null) ? 0 : id.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (!(obj instanceof Coche))
			return false;
		Coche other = (Coche) obj;
		return this.id == other.id;
	}

	public String getId() {
		return this.id;
	}

	public TipoCoche getTipoCoche() {
		return tipo;
	}

	public TestAuto getTestAuto() {
		return test;
	}

	public Integer getSatisfaccionClientes(){
		Integer sat;
		switch (tipo) {
		case Compacto:
			sat = 30;
			break;
		case Berlina:
			sat = 80;
			break;
		case Familiar:
			sat = 100;
			break;
		case Utilitario:
			sat = 50;
			break;
		default:
			sat = 0;
		}
		return sat;
	}
	
	public Integer getCoste() {
		return coste - getDescuentoPorTestAuto();
	}
	
	private Integer getDescuentoPorTestAuto() {
		int coefPosicion;
		switch (test) {
		case primero:
			coefPosicion = 3000;
			break;
		case segundo:
			coefPosicion = 2100;
			break;
		case tercero:
			coefPosicion = 1500;
			break;
		case cuarto:
			coefPosicion = 1200;
			break;
		default:
			coefPosicion = 0;
		}
		return coefPosicion;
	}
	
}

Comments (1)

Leave a comment

Su mensaje ha sido enviado correctamente. ¡Muchas gracias!. Recuerda reiniciar la pagina para ver el comentario.

No ha sido posible enviar el mensaje. Revise los datos