viajantevoraz.java

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

// ViajanteVoraz.java

package soluciones.practi06;
import org.omg.CORBA.INTERNAL;
import esquemas.EsquemaVZ;
import problemas.ProblemaViajante;
import soluciones.EstrategiaSolucion;

/**
 * Clase que da soluci髇 al Viajante voraz, implementando la clase abstracta
 * EsquemaVZ. El objetivo de esta clase es recorrer todos todos los nodos de un
 * grafo con un recorrido m韓imo.Implementa la interfaz
 * <code>Temporizable</code> para que las soluciones puedan ser medidas; por
 * tanto han de implementarse los m閠odos de dicha interfaz,
 * <code>procesamientoInicial()</code>, <code>procesamientoFinal()</code> y
 * <code>funcionAMedir()</code>.
 * 
 * @version 2.0, 27/09/2005
 * @see EstrategiaSolucion
 * @see EstrategiaSolucion#procesamientoInicial()
 * @see EstrategiaSolucion#procesamientoFinal()
 * @see EstrategiaSolucion#solucion()
 */

public class ViajanteVoraz extends EsquemaVZ implements EstrategiaSolucion {
	/**
	 * Contiene los atributos privados, visitados, distancia, camino, el
	 * CandidatoOrigen, elCandidatoDestino y recorrido
	 */
	// recordar los visitados
	private boolean[] visitado;

	// mirar la distancia m韓ima
	private int distancia;

	// construir los nodos por los que va pasando
	private String camino;

	// el nodo por el que se empieza
	private int origen;

	// ciudad origen
	private int elCandidatoOrig;

	// el nodo en el que se termina
	private int elCandidatoDes;

	// nodos por los que se ha pasado ya
	private int recorridos;

	// grafo que tenemos que recorrer
	private int[][] grafo;

	/**
	 * El m閠odo constructor carga en su atributo privado grafo, la matriz
	 * pasada en el problema
	 */
	public ViajanteVoraz(ProblemaViajante g) {

		grafo = g.getGrafo();
		origen = 0;

	}

	public ViajanteVoraz(ProblemaViajante g, int origen) {

		grafo = g.getGrafo();
		this.origen = origen;
	}

	/**
	 * Devuelve una cadena con la distancia recorrida y el camino
	 */
	public String toString() {
		return "Algoritmo del viajante mediante algoritmo voraz\n\t\tDistancia: "
				+ distancia + "\nCamino: " + camino;
	}

	/**
	 * Inicializa el vector visitado, y los atributos recorridos,
	 * elCandidatoOrig, distancia y camino
	 */
	protected void inicializa() {

		//	COMPLETAR
		recorridos = 1;
		distancia = 0;
		camino = "(" + origen;
		elCandidatoOrig = origen;
		visitado = new boolean [grafo[0].length];
		visitado[origen] = true;
	}

	/**
	 * Indica si el problema ha terminado, si se han recorrido todas las
	 * ciudades Si se han recorrido todas las ciudades, hay que llevar al
	 * viajero de nuevo a la ciudad origen
	 */
	protected boolean fin() {
		
		//	 COMPLETAR
		boolean fin = (recorridos == grafo.length);
		if (fin) {
			camino += " --> " + origen + ")";
			distancia += grafo[elCandidatoOrig][origen];
		}
		return fin;
	}

	/**
	 * Selecciona el candidato que est