inteligencia artificial grafos algoritmo la mejor ruta

5/14/2018 Inteligencia Artificial Grafos Algoritmo la Mejor Ruta - slidepdf.com

http://slidepdf.com/reader/full/inteligencia-artificial-grafos-algoritmo-la-mejor-ruta

Universidad Autónoma de Baja CaliforniaFacultad de ciencias químicas e ingeniería

Reporte Práctica 1 Grafos, Algoritmo “el camino más corto“

Materia: Inteligencia Artificial

Profesor:Dr. Alvarado Magaña Juan Paulo

Nombre:

Renteria Cuevas Roberto Alonso

Fecha de entrega: 21 de marzo del 2012



Practica 1: Arboles “Camino más Corto de un nodo a otro”

Introducción:

En esta práctica se busca aplicar algún tipo de algoritmo para calcular la ruta más corta

de una ciudad a otra pasando por la menor cantidad de ciudades, para esto seutilizaran arboles para representar el mapa de ciudades, cada ciudad será un nodo del

árbol y cada una tendrá una lista de ciudades a las que se conecta y un nombre de la

ciudad.

Ejemplo de la estructura de una Ciudad:

Ciudad {String Nombre ;Lista<Ciudad > nodos ;

}

Por otro lado un mapa tiene igual mente una lista de Ciudades que se interconectan

entre sí para formar un árbol.

Ejemplo de estructura de un Mapa.

Mapa {

Lista<Ciudad> ciudades ;

}

Teniendo esta estructura podremos generar nuestro mapa creando una serie de

ciudades y agregando los nodos a los que se conecta.

Ejemplo de cómo se hacen crea un mapa, simplemente se agregan ciudades a

la lista de nodos de cada ciudad.



Desarrollo:

El programa se desarrollara en java, debido a que es un lenguaje orientado a objetos lo

cual facilita la abstracción del problema de una mejor manera, además se utilizara lasclases de java para el manejo de listas enlazadas, la clase a utilizar es ArrayList<?>,

esta clase contiene todos los métodos básicos para el manejo de listas de esta forma

nos preocupamos menos por crear la lista desde cero como se haría en el lenguaje C.

1- Comenzamos por crear nuestra clase Ciudad, el atributo paren es una bandera

que indica que en la ciudad en un nodo padre, esto será utilizado después para

no ciclarse en el algoritmo para encontrar la ruta más corta.

public class Ciudad {

private String name = null; //nombre de la ciudad

private boolean parent = false; //bandera que indica que es nodo padre.

private ArrayList<Ciudad> nextNodes = null; // Lista de nodos siguientes

//constructor

public Ciudad(String name) {

this.name = name;

this.nextNodes = new ArrayList<Ciudad>();

}

2- Agregamos todos los métodos necesarios para manejar nuestra lista de nodos,

como en este caso utilizaremos la clase ArrayList<?> de java esta ya incluye

todos los método necesarios para el manejo de la lista.

3- Creamos ahora la clase Map.

public class Map {

ArrayList<Ciudad> ciudades = null; //lista de ciudades del mapa

public Map() {

}

}



MAPA

4- El siguiente paso es crear el mapa que utilizaremos para realiza las pruebas del

algoritmo, esto se realiza en el constructor de la clase Map.

El mapa que crearemos para este caso será el siguiente:

- Las conexiones a realizar serán la siguientes:

o C0.nodos = { C1,C2 }

o C1.nodos = { C0,C3,C4 }




o C5.nodos = { C3,C4,C8 }


o C7.nodos = { C6 }

o C8.nodos = { C5 }

Ahora pasemos estas relaciones a código, esto se agregara en el constructor de la

clase Map, como continuación se muestra.

public Map() {

ciudades = new ArrayList<Ciudad>(); //inicializa las ciudadesfor (int i = 0; i <= 8; i++) {

ciudades.add(new Ciudad("c" + i));}

//agregando los nodos a los que se conecta cada nodo para generar el mapa de arribaciudades.get(0).addNextNode(ciudades.get(1));ciudades.get(0).addNextNode(ciudades.get(2));



ciudades.get(1).addNextNode(ciudades.get(3));ciudades.get(1).addNextNode(ciudades.get(4));ciudades.get(1).addNextNode(ciudades.get(0));

ciudades.get(2).addNextNode(ciudades.get(6));


ciudades.get(3).addNextNode(ciudades.get(5));ciudades.get(3).addNextNode(ciudades.get(1));

ciudades.get(4).addNextNode(ciudades.get(5));ciudades.get(4).addNextNode(ciudades.get(1));

ciudades.get(5).addNextNode(ciudades.get(3));ciudades.get(5).addNextNode(ciudades.get(4));ciudades.get(5).addNextNode(ciudades.get(8));ciudades.get(5).addNextNode(ciudades.get(6));

ciudades.get(6).addNextNode(ciudades.get(5));ciudades.get(6).addNextNode(ciudades.get(2));ciudades.get(6).addNextNode(ciudades.get(7));


ciudades.get(8).addNextNode(ciudades.get(5));}



ALGORITMO: El camino más corto.

El algoritmo que utilizaremos será un algoritmo recursivo que lo que hace es a partir delnodo inicial expandir recursivamente cada uno de los nodos siguientes hasta encontrarel nodo destino, una vez que encuentra el nodo destino es nuestro caso base y a partir

de ahí regresa la como ruta una lista con el nodo destino y a partir de ahí le agrega a lalista cada uno de los nodos por los que paso para llegar hasta el nodo destino,incrementando en cada nodo el tamaño de la lista, además en cada nodo anterior onodo “padre” realiza una comparación para determinar si el nuevo camino es más cortoque el anterior, si es que ya se tenía un anterior y regresa la ruta con el camino máscorto, al termina de recorrer cada uno de los nodos de cada ciudad regresara una listacon la ruta más corta de un nodo a otro, si no se encontró ningún camino que llegue aldestino regresa una ruta vacía.

El algoritmo que emplearemos será un algoritmo de tipo codicioso ya que recorrerátodo el árbol hasta encontrar la mejor ruta y no se detendrá al encontrar la primera

solución sino que seguirá recorriendo el árbol en busca de una mejor ruta hasta haberrecorrido todo el árbol.

Explicación:

Este algoritmo recibe como parámetro la ciudad destino y el nodo padre.

1- Inicializa la lista Ruta.

2- Pregunta si la ciudad actual es el es el destino.

3- Si es el destino sale del la función y regresa una lista con la ciudad actual.

4- Si No recorre cada uno de los nodos a los que se conecta la ciudad.5- Si el siguiente nodo es un nodo padre sale de la función y regresa vacio.

6- Si no es nodo padre activa la bandera “padre” de nodo padre y Expande

recursivamente el nodo “realiza desde el paso 1 al nodo siguiente ”.

7- Compara el tamaño de la lista que regreso la función recursiva, con la ruta

anterior si es que ya existe alguna ruta anterior.

8- Si la longitud de la ruta es menor remplaza la ruta actual por la nueva ruta.

9- Al terminar de expandir todos los nodos de la ciudad regresa la ruta más

corta, si es que logro llegar a a la ciudad destino sino regresa lista vacia.



Pseudocódigo:

Función Lista shortestRoute(destino,nodoPadre){Lista ruta//caso base IF (this = destino){

ruta.add(this)Return ruta

}ELSE {//caso recursivo For(i=0 ; i < this.nodos.size() ; i++ ){

IF(this.nodos(i).esPadre = false){nodoPadre.setParent(true);nuevaRuta= shortestRoute(destino,this )

IF(nuevaRuta.isNotEmpty AND (nuevaRuta.size < ruta.size OR ruta.isEmpty){ruta=nuevaRuta

}}

}IF(ruta.isNotEmpty){

Ruta.add(this)}Return ruta

}}

Código en Java:

public ArrayList<Ciudad> findShortestRoute(String destination, Ciudad parentNode) {ArrayList<Ciudad> route = new ArrayList<Ciudad>(); //inicializa la ruta //CASO BASE : cuando encuentra el nodo destinoif (this.name.equalsIgnoreCase(destination)) {

route.add(this);return route;

} else {for (int i = 0; i < nextNodes.size(); i++)

//CASO RECURSIVO: expander nodo siguiente solo si no es nodo padreif (!nextNodes.get(i).isParent()) {

parentNode.setParent(true); //le asigna la bandera parent al nodo padre. //expande recursivamente el siguiente nodo en la lista.ArrayList<Ciudad> newRoute = nextNodes.get(i).findShortestRoute(destination, this);if (!newRoute.isEmpty() && (newRoute.size() < route.size() || route.isEmpty()))

//actualiza la la ruta si la nueva ruta es menor a la anterior o es el primer caso con éxito.route = newRoute;

}

this.parent = false; //restaura la bandera parent antes de regresar a un nivel anterior.if (!route.isEmpty()) //si es caso de exito agrega la ciudad actual a la ruta y la regresa.

route.add(this);return route;

}}



RESULTADO

inteligencia artificial grafos algoritmo la mejor ruta

Documents