Download Práctica 2
Document related concepts
no text concepts found
Transcript
Práctica 2 Búsqueda I En esta práctica vamos a ver algunos algoritmos de búsqueda en grafos. Para ello vamos a utilizar una aplicación que nos permite programar diferentes problemas que pueden solucionarse mediante búsqueda en grafos. Primero veremos unas trazas y luego veremos cómo se puede programar un problema. 1 La aplicación La aplicación que vamos a utilizar se encuentra disponible en: http://www.aic.uniovi.es/ssii/P2/AlgBusqueda.zip Una vez descargada, descomprimimos el zip y vemos que aparecen dos directorios: • LibreríaMotorBusqueda.- Contiene el fichero busqueda.jar donde se encuentran implementados los algoritmos de búsqueda en grafos que habéis visto en teoría. • VisorTraza.- Contiene una serie de ficheros que nos permiten ejecutar una aplicación que visualiza las trazas generadas por los algoritmos de búsqueda. Para que todo esto funcione, debemos tener el directorio bin de jdk en el path y debemos crear una variable de entorno (JAVA_HOME) almacenando el directorio principal del jdk. Algo como lo que sigue (teniendo en cuenta las particularidades del PC en el que os encontréis): PATH=PATH;C:\Archivos de programa\Java\jdk1.5.0_08\bin JAVA_HOME=C:\Archivos de programa\Java\jdk1.5.0_08 2 El problema de las ciudades Ya habéis visto en teoría que estos algoritmos se pueden utilizar para buscar rutas que nos lleven de una ciudad a otra. En la figura 1 se muestra un mapa en el que se representan 12 ciudades con las diferentes carreteras que las unen. Podemos utilizar este mapa como ejemplo para aprender a utilizar esta aplicación. En este caso se pretende ir de la ciudad 0 a la ciudad 11 circulando por las carreteras existentes. No todas las ciudades están conectadas entre sí. Aquellas que sí lo están, aparecen unidas por una línea, indicándose también el número de kilómetros que supone ese trayecto. Figura 1.- Mapa de ejemplo 3 El visor de trazas Para empezar vamos a descargar un fichero de traza generado por el algoritmo de Coste Uniforme para resolver el problema del epígrafe anterior: http://www.aic.uniovi.es/ssii/P2/ciudadesCosteUniforme.xml Haciendo doble click sobre el enlace “Visor de Traza” contenido en el directorio VisorTraza, aparece la siguiente ventana: Figura 2.- Visor de traza Para visualizar una traza debemos ir a Fichero->Abrir y seleccionar la traza que deseamos. En este caso seleccionaremos la traza que acabamos de descargar. Vemos que nos indica el problema que estamos resolviendo y con qué algoritmo. El área grande se utiliza para ir visualizando los estados por los que va pasando el algoritmo (cuando pulsamos el botón “Adelante”). En general, cada nodo se identificará con un número natural (empezando en 1), aunque para el algoritmo Coste Uniforme, además del número natural, se mostrará en el nodo el coste que supone llegar hasta el mismo. Los arcos que unen los diferentes nodos vienen etiquetados con un texto descriptivo de la acción y el coste que esta supone. Los nodos pueden tener diferentes colores, indicando cada color una situación diferente para el nodo: • Gris.- El nodo ya ha sido explorado • Azul.- El nodo se encuentra en abierta • Rojo.- Es el nodo seleccionado • Amarillo.- Para este nodo se ha actualizado el valor de g(n) Figura 3.- Traza del problema de las ciudades resuelto con el algoritmo de coste uniforme Trabajo: Visualiza la traza utilizando los botones Inicio y Adelante para ver cómo el algoritmo de Coste Uniforme alcanza la solución. 4 Programando un problema Vamos a ver cómo está programado el problema de las ciudades. Para ello, vamos a descargar el siguiente fichero: http://www.aic.uniovi.es/ssii/P2/CiudadesCompleto.java Nada mas abrir el fichero nos encontramos con la inclusión de unas ciertas librerías imprescindibles para el programa, ya que son las librerías en las que se encuentra implementado el motor de búsqueda: import es.uniovi.busqueda.*; import es.uniovi.busqueda.algoritmos.*; Para implementar este problema necesitamos definir una clase que herede de la clase Problema. En este caso, la clase recibirá el nombre CiudadesCompleto y cada instancia de esta clase será un nodo a expandir en el grafo que se forma al ejecutar un algoritmo en busca de la solución. Por tanto, esta clase necesita que se definan los siguientes campos: private private private private static double[][] caminos; static double[] heuristico; int orig; static int dest; El primero de ellos es una matriz conteniendo el coste de los caminos entre las diferentes ciudades (se pondrá infinito cuando el camino no exista). El segundo es un vector que almacena el número de kilómetros estimados desde cada ciudad hasta el destino. El tercero es el número de la ciudad de origen y, el cuarto, el de la ciudad de destino. Los campos comunes a todos los nodos deben declararse como estáticos. Se necesita implementar dos constructores, uno para instanciar el problema y otro para ir generando los nodos sucesores hasta alcanzar la solución. public CiudadesCompleto (int o, int d, double[][] matriz, double[] heuris){ orig=o; dest=d; prof=0; caminos = matriz; heuristico = heuris; nombre = new String("Ciudades"); } private CiudadesCompleto (int o, int pr){ orig=o; prof=pr; } El primero de los constructores debe ser público para poder crear un problema desde fuera de la clase. A este constructor debemos pasarle los datos del problema e inicializa los campos anteriormente definidos. Además, debemos inicializar un par de campos heredados: prof (de profundidad) con valor 0 y nombre (de nombre del problema) con el nombre que deseemos darle. El segundo constructor necesita únicamente el número de la ciudad a la que estará asociado y su profundidad, es decir, cuantos nodos se han expandido desde el nodo inicial. El resto de campos no necesitan ser inicializados ya que han sido inicializados por el otro constructor (acuérdate de que eran estáticos). Necesitamos implementar también un método que nos de información del nodo en que nos encontramos: public String Informacion(){ return new String("Ciudad: "+(orig)+" Destino: "+(dest)); } Necesitamos también implementar un método que nos indique si un nodo es o no objetivo. En este caso, resulta un método muy sencillo: public boolean EsObjetivo(){ if (dest == orig) return true; else return false; } Para poder expandir un nodo, necesitamos conocer cuales son sus nodos sucesores. Para ello se hace necesario implementar la función Sucesores, que debe retornar una LinkedList1 de elementos InfNodo. El constructor de InfNodo necesita como parámetros un nodo sucesor, lo que cuesta llegar a él y una descripción de la acción. La función queda de la siguiente forma: public LinkedList<InfNodo> Sucesores(){ LinkedList<InfNodo> sucesores = new LinkedList<InfNodo>(); for ( int i=0; i < caminos.length; i++ ){ if (caminos[orig][i] != Double.POSITIVE_INFINITY){ CiudadesCompleto p = new CiudadesCompleto(i,prof+1); InfNodo hijo = new InfNodo(p,new Double(caminos[orig][i]), new String("Ir hacia ciudad: "+(i))); sucesores.addLast(hijo); } } return sucesores; } Algunos algoritmos necesitan lo que conocemos como heurístico (estos algoritmos los veremos en la siguiente práctica) por lo que necesitamos implementar una función que nos retorne el valor heurístico de un nodo. El valor heurístico de un nodo es la estimación que haces sobre lo que falta para alcanzar la solución desde un nodo. Si no implementamos esta función, el motor de búsqueda entenderá que el valor heurístico de todos los nodos es 0. En este problema la función es muy sencilla: public double Heuristico(){ return heuristico[orig]; } Para optimizar las ordenaciones, necesitamos implementar el método hashCode, que retorna un mismo entero para todos los nodos que son iguales: public int hashCode(){ //Todas las ciudades con mismo origen tienen el mismo hashcode return orig; } 1 import java.util.LinkedList; Finalmente debemos implementar un método que nos diga cuándo dos nodos son iguales: public boolean equals( Object c ){ // Si es instancia de ciudades el objeto c if ( c instanceof CiudadesCompleto ){ CiudadesCompleto b = (CiudadesCompleto)(c); if (orig!=b.orig) return false; // caminos es estático así que todos los objetos de // la clase ciudades tienen los mismos arcos return true; } else return false; } Queda ahora por implementar el programa principal que, como podemos ver en el fichero descargado, se ocupa de crear el problema, definiendo la matriz y el vector, y creando una instancia de CiudadesCompleto con todos estos datos, donde se le indica que la ciudad de origen es la 0 y la de destino la 11. Finalmente resuelve el problema con diferentes algoritmos, mostrando la solución obtenida y el tiempo empleado por cada uno de ellos. Además, si le indicamos el nombre de un fichero, almacenará en el mismo la traza que podrá ser visualizada en el Visor de Traza visto en el epígrafe anterior (únicamente el algoritmo Profundidad Iterativa no genera la traza). 5 Compilar y ejecutar La manera más sencilla de compilar y ejecutar un problema implementado, es situar el fichero con el código fuente en el directorio donde se encuentra la librería del motor de búsqueda (busqueda.jar), es decir, en el directorio LibreríaMotorBusqueda. Para compilar ejecutar el siguiente comando: javac –classpath busqueda.jar CiudadesCompleto.java ¡Ojo con las mayúsculas y minúsculas! Para ejecutar los algoritmos sobre este problema lanzar el siguiente comando: java –classpath busqueda.jar;. CiudadesCompleto Trabajo: Compila y ejecuta. ¿Generan todos los algoritmos la misma solución? ¿Tardan lo mismo? Visualiza las diferentes trazas para comprender el funcionamiento de los algoritmos. Cambia las ciudades de origen y destino y vuelve a ejecutar. 6 Rumanía Prueba a modificar el fichero CiudadesCompleto.java para adaptarlo al problema de Rumanía visto en teoría. Se pretende ir de Arad a Bucarest siguiendo alguna de las posibles rutas indicadas en el siguiente mapa: Figura 4.- Mapa de Rumanía Nota: Como función heurística, puedes poner 0 para todas las ciudades.