Untitled

 avatar
unknown
plain_text
2 years ago
2.7 kB
6
Indexable
	private void asignaPasteleros(int [][] costes, int[] pedido, int[] pasteleros, int costeT) throws CloneNotSupportedException {
		Monticulo m;
		TNodo nodo = new TNodo(getNumPasteleros());
		TNodo hijo = new TNodo(getNumPasteleros());
		int cota,estPes;
		m = new Monticulo(0,factorial(this.numPasteleros));
		costeT = 0;
		nodo.setPasteleros(pasteleros);
		for(int i=1; i<=this.numPasteleros;i++) {
			nodo.getAsignados()[i] = false;
		}
		nodo.setK(0);
		nodo.setCosteT(0);
		nodo.setEstOpt(estimacionOpt(costes,pedido,nodo.getK(),nodo.getCosteT()));
		m.insertar(nodo);
		cota = estimacionPes(costes,pedido,nodo.getK(),nodo.getCosteT());
		while(!m.monticuloVacio() && (estimacionOpt(costes,pedido,m.primero().getK(),m.primero().getCosteT()) <= cota)) {
			nodo = m.obtenerCima();
			//se generan las extensiones válidas del nodo.Para cada pastelero no asignado se crea un nodo.
			hijo.setK(nodo.getK()+1);
			hijo.setPasteleros(nodo.getPasteleros());
			hijo.setAsignados(nodo.getAsignados());
			for(int i=1;i<=this.numPasteleros;i++) {
				if(!hijo.getAsignados()[i]) {
					hijo.getPasteleros()[hijo.getK()] = i;
					hijo.getAsignados()[i] = true;
					hijo.setCosteT(nodo.getCosteT()+costes[i][pedido[hijo.getK()]]);
					if(hijo.getK() == this.numPasteleros) {
						if(cota >= hijo.getCosteT()) {
							pasteleros = hijo.getPasteleros();
							costeT = hijo.getCosteT();
							cota = costeT;
						}
					}
					else {
						//la solució no está completa
						hijo.setEstOpt(estimacionOpt(costes,pedido,hijo.getK(),hijo.getCosteT()));
						TNodo clon = (TNodo)hijo.clone();
						m.insertar(clon);
						estPes = estimacionPes(costes,pedido,hijo.getK(),hijo.getCosteT());
						if(cota > estPes) {
							cota = estPes;
						}
					}
					hijo.getAsignados()[i] = false;
				}
				debug();
			}	
		}
		System.out.println("patata");
	}
	
	private int estimacionOpt(int[][] costes, int[] pedido, int k, int costeT) {
		int estimacion, menorC;
		estimacion = costeT;
		for(int i=k+1;i<this.numPasteleros;i++) {
			menorC = costes[1][pedido[i]];
			for(int j=2;j<this.numPasteleros;j++) {
				if(menorC > costes[j][pedido[i]]) {
					menorC = costes[j][pedido[i]];
				}
			}
			estimacion += menorC;
		}
		return estimacion;
	}
	
	private int estimacionPes(int[][] costes, int[] pedido, int k, int costeT) {
		int estimacion, mayorC;
		estimacion = costeT;
		for(int i=k+1;i<=this.numPasteleros;i++) {
			mayorC = costes[1][pedido[i]];
			for(int j=2;j<=this.numPasteleros;j++) {
				if(mayorC < costes[j][pedido[i]]) {
					mayorC = costes[j][pedido[i]];
				}
			}
			estimacion += mayorC;
		}
		return estimacion;
	}
Editor is loading...