Download Práctica 2

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.