Untitled
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...