solucionskylinedyv.java

Java examples for dinamic programming, divide and conquer, greedy algorithms and backtracking.

package soluciones.practi08;

import problemas.Edificio;
import problemas.ProblemaSkyline;
import soluciones.EstrategiaSolucion;
import esquemas.EsquemaDYV;

/**
 * Clase que soluciona el problema del Skyline usando la estrategia de "Divide y
 * vencer醩". Extiende a <code>EsquemaDyV</code> e implementa
 * <code>EstrategiaSolucion</code>. Tiene dos clase internas,
 * <code>ProblemaSky</code> y <code>SolucionSky</code> que implementan
 * respectivamente las interfaces internas <code>Problema</code> y
 * <code>Solucion</code> de <code>EsquemaDyV</code>.
 * 
 * @version 1.2, 15/11/2005
 * 
 */
public class SolucionSkylineDyV extends EsquemaDYV implements
        EstrategiaSolucion {
    /**
     * El problema que tiene que resolver.
     */
    private ProblemaSkyline pb;

    /**
     * La soluci髇 al problema <code>pb</code>.
     */
    private Skyline solucionFinal;

    /**
     * Construye una soluci髇 a partir del problema que recibe.
     * 
     * @param pb
     *            El problema a resolver
     */
    public SolucionSkylineDyV(ProblemaSkyline pb) {
        this.pb = pb;
    }

    /**
     * Devuelve la soluci髇 final encontrada.
     * 
     * @return La soluci髇 al problema
     */
    public Skyline getSolucion() {
        return solucionFinal;
    }

    /**
     * Verdadero si el problema consta de un 鷑ico edificio. Falso en caso
     * contrario.
     */
    protected boolean esCasoBase(Problema p) {
    	// TODO
    	ProblemaSky ps = (ProblemaSky)p;
    	if (ps.problema.length==1)
    		return true;
    	return false;
    }

    /**
     * Devuelve la soluci髇 que contiene el skyline formado por el 鷑ico
     * edificio que tiene el problema.
     */
    protected Solucion resuelveCasoBase(Problema p) {
        // TODO
    	ProblemaSky ps = (ProblemaSky)p;
    	SolucionSky sol = new SolucionSky(ps.problema[0]);
    	return sol;
    }

    /**
     * Divide el problema en dos subproblemas, cada uno de ellos contentiendo la
     * mitad de los edificios del problema que recibe.
     */
    protected Problema[] divide(Problema p) {
    	/*
    	 * Convertimos el problema en un ProblemaSky; de 閘 extraemos el n鷐ero de 
    	 * edificios que contiene, que guardamos en una variable numPbs. En numPbsIzq 
    	 * guardamos la mitad de ese valor.
    	 */
    	// TODO
    	ProblemaSky ps = (ProblemaSky)p;
    	int numPbs = ps.problema.length;
    	int numPbsIzq = numPbs/2;
        
        /*
		 * Creamos el array de subproblemas que hay que devolver, que llamaremos
		 * pbs, con el n鷐ero de elementos adecuados. Cada uno de los dos
		 * subproblemas se crea, mediante el constructor correspondiente.
		 */
        // TODO
    	ProblemaSky [] pbs = new ProblemaSky[2];
    	pbs[0] = new ProblemaSky(numPbsIzq);
    	pbs[1] = new ProblemaSky(numPbs - numPbsIzq);
    	        
        /*
         * Y se transfiere a cada uno de los dos subproblemas los edificios
         * de los que consta cada uno de ellos; primero a uno...
         */
        // TODO
    	int i=0;
    	while (i < numPbsIzq){
    		pbs[0].problema[i] = ps.problema[i];
    		i++;
    	}
        
        /*
         * ... y luego al otro.
         */
        // TODO
    	int j=0;
    	while (i<numPbs){
    		pbs[1].problema[j] = ps.problema[i];
    		j++;
    		i++;
    	}
        /*
         * Por 鷏timo, se devuelve el arrray de problemas creado.
         */
        return pbs;
    }

    /**
     * Combina los dos skylines que recibe en uno solo, haci閚dolo mediante una
     * mezcla ordenada de los dos skylines. Tiene una casu韘itica complicada.
     * Tiene un coste lineal.
     */
    protected Solucion combina(Solucion[] sk) {
        /*
         * Guardamos el primer skyline en s1 para m醩 comodidad
         */
    	int[] sk1 = ((SolucionSky) sk[0]).sk.getVector();

        /*
         * Y el segundo en s2
         */
        int[] sk2 = ((SolucionSky) sk[1]).sk.getVector();
        
        int n1 = sk1.length;   // El n鷐ero de elementos del primer skyline
        int n2 = sk2.length;   // El n鷐ero de elementos del segundo skyline

        /*
         * Este es el array de destino, que tiene como m醲imo este n鷐ero de
         * elementos
         */
        int[] aux = new int[n1 + n2];     

        int i = 1;          // Con este 韓dice recorremos s1
        int j = 1;          // Con este 韓dice recorremos s2
        int k = 1;          // Con este 韓dice recorremos aux

        /*
         * Por convenio el primer elemento de un skyline siempre es 0 
         * (la altura del suelo previo al skyline)
         */
        aux[0] = 0;     

        /*
         * Esta ser