Búsqueda RBFS para hallar la ruta de Oradea a Bucharest

La búsqueda en computación, es un tema muy estudiado, esto se debe a que las búsquedas son las funciones más usadas en los sistemas software de cualquier índole, más que otras operaciones como inserción, selección, actualización y eliminación. En el campo específicamente de Inteligencia Artificial, las búsquedas toman una connotación un poco diferente. El buscar datos implica buscar nuevas soluciones que en muchos casos no se tiene certeza si será encontrada. En el curso de IA tratamos, entre otras búsquedas, la búsqueda RBFS. Como referencia, el libro de Russell y Norving: "Artificial Intelligence A Modern Approach" contiene este tema, además de dicho libro sacamos un ejemplo, el cual lo resolvimos de manera gráfica para observar el comportamiento del RBFS.

Sea el mapa de ruta:

Y la tabla de heurística:

Primer paso:

El hijo con menor recorrido es Sibiu, y el siguiente hijo menor queda en memoria, en este caso Zerind con un valor de 445.

Segundo paso:

El nodo Sibiu se expande, sin imbargo, sus hijos presentan valores mayores que él. El algoritmo toma el nodo en memoria con el menor valor, no sin antes, guardar el menor valor de los hijos expandidos, en este caso Romnicu Vicea con un valor de 424, que queda en memoria, para luego expandir Zerind.

Tercer paso:

El hijo expandido de Zerind: Arad, presenta un valor mayor al de su padre, por tanto pasa al anterior que estaba en memoria, es decir 424 que correspondía a Rimnicu Vilcea, y en este ser verifica el hermano menor en memoria, es decir Fagaras con 426 y se procede a expandir los hijos de Rimnicu Vilcea.

Cuarto paso:

Los hijos de Rimnicu Vilcea son mayores que el padre, por tanto, se procede a llamar al nodo que quedo en memoria, es decir Fagaras, se guarda antes el menor valor de los hijos expandidos, en este caso con 428 el nodo Pitesti. Y se procede a expandir Fagaras.

Quinto paso:

Fagaras expande su hijo que casualmente llega a ser el nodo buscado: Bucarest, y entonces termina el algoritmo.

Inferencia usando un heap con distribución de probabilidad conjunta

En el campo de Inteligencia Artificial, los modelos probabilísticos han sido adoptados como una opción a las redes neuronales. Modelos probabilísticos como las redes bayesianas, han sido adaptadas a un sin número de aplicaciones: diagnóstico médico, modos de búsquedas 'inteligentes' en motores de búsqueda conocidos, reconocimiento de patrones en imágenes, entre otras. La red bayesiana es un grafo dirigido, cuyos nodos representan las variables que se requieren para modelar el entorno, sin embargo, el modo de inferencia es inmensamente variado, existen inferencias completas y aproximadas. La inferencias completas, incluyen en el cálculo de una consulta, todos los nodos, la distribución conjunta completa. Las inferencias aproximadas, buscan los nodos que pertenecen a la línea de ascendientes o descendientes (según sea el caso), del nodo involucrado en la consulta.

El modo de consulta más común, el cual se pretende manejar aquí, es P(e|X), donde se desea saber la probabilidad de que ocurra la variable 'e' (que es el nodo padre o ascendiente del conjunto de nodos X), dado que han aparecido (o desaparecido) un conjunto 'X' de variables ligadas (como síntomas de una enfermedad o palabras que un usuario final ha colocado en un motor de búsqueda).
Aquí un modo de inferencia con distribución conjunta completa usando un método que hice junto con mis compañeros Jorge Valverde R. y Juan Grados V., basándonos en el comportamiento de la red cuando hay una instanciación, utilizando una estructura de datos Heap. El mecanismo de inferencia es parecido al método de Enumeración.

Tabla de probabilidades conjunta

Esquema que representa la distribución de probabilidades

Para implementar la estructura, lo hacemos a través de una cola de prioridad. Donde cada nodo tiene dos hijos, y cumple con la siguiente norma:

Si un nodo está en la posición “i”, entonces sus hijos están en la posición: 2*i y (2*i+1).

Relación entre la matriz y la estructura árbol

Como puede observarse, todo el contenido de la matriz se encuentra en las hojas. Además mientras va subiendo de nivel, a partir de las hojas, los valores obtenidos en los nodos internos son las sumas de sus descendientes.

Por ejemplo, queremos hallar la probabilidad de caries con dolor.

Luego, si queremos hallar la probabilidad de dolor, el esquema sería:

Para cada profundidad del árbol, existe una variable diferente. Y el número de veces que se repite una variable en su ply es: el cual llamaremos: grado de repetición, a la cual llamaremos simplemente grado.

Algoritmo P(a^b)

1. Determinar la variable de mayor grado “m” entre “a” y “b”.

2. La variable de menor grado “n” entre “a” y “b”.

3. x ß hallar la probabilidad de todos los subárboles “m”

4. y ß hallar la probabilidad dentro de los subárboles “-m”, de las variables “n”

5. retornar x+y

Algoritmo P(a|b)

1. Determinar la variable de mayor grado “m” entre “a” y “b”

2. Si “a” es “m”, entonces

3. n ß b

4. Sino

5. n ß a

6. Fin-si

7. suma ß 0

8. prob ß hallar probabilidad de subárbol “n”

8. Para cada subárbol “m” hacer

9. suma ß suma + hallar probabilidad de subárbol “n”

10. Fin-para

11. retornar suma/prob

Análisis de red con el algoritmo de flujo máximo: Ford-Fulkerson

1. Introducción

Dentro del sistema de transporte, en Trujillo, uno de los principales problemas es la congestión de la red vial, principalmente en el centro de la ciudad. Esto se debe a muchos factores, entre los que podemos mencionar:

· Algunas calles son cerradas para los vehículos en ciertos horarios.

· Existen horas puntas, en las que las personas se dirigen con sus vehículos a sus trabajos, en el centro de la ciudad.

· Las calles, en el centro, son estrechas y la cantidad de autos es grande en comparación a su capacidad.

Estos factores son contra-producentes en la economía de los conductores, principalmente de los taxistas, quienes diariamente tienen que circular por el centro de la ciudad, para poder prestar sus servicios, ya que es el lugar más seguro de encontrar pasajeros.

Dentro de este entorno, el taxista se ve envuelto muchas veces dentro de una congestión casi innecesaria, si él supiera que existen algunas rutas que son poco usadas en ciertas horas, en las que él pueda estar involucrado.

Para ello presentamos una solución al problema de la navegación de taxis en la red vial del centro de la ciudad, y se pretende dar una ruta alternativa, que estime la mejor opción en cuanto a ahorro tanto de tiempo, como de combustible, ya que usualmente ambos suelen estar relacionados fuertemente.

Figura 1. Mapa satelital del centro de la ciudad de Trujillo, extraído de Google Earth.

2. Problema de tráfico

Dentro del tema podemos tomar ciertas consideraciones, enfocándonos específicamente a la actividad diaria del centro de Trujillo.

Una de ellas es que la velocidad de un vehículo en el centro de la ciudad es de no más de 30Km/h, por el simple hecho de estar en una zona urbanizada, y si descontamos el hecho de que las calles son permanentemente usadas por muchos vehículos, entonces podríamos deducir que la velocidad podría ser mucho menor. Por ello consideramos que la velocidad es despreciable, por tanto no la contamos dentro de nuestro análisis para encontrar una ruta adecuada, tampoco consideramos la distancia, por el mismo hecho, es decir por que no siempre la distancia más corta es la más adecuada, ya que podría estar demasiado congestionada, ya que muchos conductores toman esa ruta por el mismo razonamiento de ser la más corta.

Así que nos quedaría un criterio que es muy importante en las zonas urbanizadas: el tráfico. ¿Como definimos el tráfico?, de muchas formas, ya que el tráfico es el flujo sobre un canal, en nuestro caso: el tráfico vial; está referido a la cantidad de autos que circulan sobre una red vial.

Podemos entonces concluir en lo siguiente:

· La velocidad de un vehículo en una zona urbanizada es despreciable y moderadamente constante.

· La distancia más corta no es usualmente la más óptima, sino la ruta con menos tráfico.

3. Teoría de máximo flujo

La teoría de máximo flujo, es un sub-problema de los problemas de flujo de red.

3.1 Nodo fuente (nodo “s”)

El nodo origen es denominado fuente y es donde se origina el flujo, dicho flujo es constante, durante toda su trayectoria, esto es parecido a la Leyes de Kirchoff, en física, donde la corriente que fluye a través de un circuito es invariable durante toda su trayectoria, obedeciendo a la ley de conservación de la materia.

3.2 Nodo sumidero (nodo “t”)

Es el nodo destino, del flujo proveniente del nodo fuente. La ruta trazada desde el nodo fuente a este nodo debe contener le máximo flujo de todas las posibles rutas.

3.3 Phi

Cada nodo tienen un valor Phi, dicho valor indica la capacidad máxima de flujo que puede pasar sobre dicho nodo.

Observamos que el valor Phi, es decir la capacidad máxima que puede aceptar el nodo X, es el menor flujo proveniente de otras fuentes.

3.4 Flujo máximo

El flujo máximo, se puede definir dentro de nuestro problema, como la máxima capacidad libre de vehículos, que puede albergar una calle o avenida, que permite mayor libre tránsito, por tanto mayor rapidez para desplazarse. Que para nuestro caso será un conjunto de calles que o ruta desde un nodo fuente a un nodo sumidero.

La definición es:

F: VxV à V

Donde V, es el conjunto de vértices, el flujo máximo es: dado una matriz de nodos o vértices como entrada, produce una ruta conformado por un conjunto de vértices, como salida.

Paso 1.

Paso 2.

Repetir el paso 2 hasta que “t” pertenezca a X

4. Análisis del problema

4.1 Definición del problema

Dado un grafo G=(V,E) dirigido, que representa una red vial, dentro una zona mayoritariamente urbanizada. Y dado dos nodos (u,v) que pertenecen al conjunto de vértices de V. Encontrar la ruta que tenga menos cantidad de autos en sus calles, por tanto, que permitan una mayor movilidad desde el nodo origen “u” hasta el nodo destino “v”.

5. Diseño

5.1 Algoritmo de Flujo Máximo

Algoritmo de Flujo máximo

Entrada: MAdy (matriz de adyacencia), s (nodo origen), t (nodo destino)

Salida: V (arreglo de nodos)

/* Comentarios

N: cantidad de nodos presentes en la red.

Phi: arreglo de dimensión “N” que guarda un valor de caudal para cada nodo.

Candidatos: tabla que guarda información acerca de aristas (par de nodos) candidatos para ser parte de la ruta óptima e información acerca de la arista anterior.

X: arreglo dinámico, que va guardando los nodos que ya son visitados.

--Fin-comentarios

*/

1. inicializar arreglo Phi

2. candidatos ß null

3. nodo ß s

4. agregar(X,nodo)

5. Mientras (nVisitados<=N && nodo!=t)

6. calcularCandidatos(nodo,candidatos)

7. Para iß 0 hasta |candidatos|-1

8. nodoI ß candidatos[i][0]

9. nodoF ß candidatos[i][1]

10. valoresMin[i]ß-MIN( Phi[nodo],MAdy[nodoI][nodoF] )

11. index ß MAX(valoresMin)

12. Phi(candidatos[index][1]) ß valoresMin[index]

13. nodo ß candidatos[index][1]

14. agregar(X,nodo)

15. nVisitados ß |X|

16. V ß obtenerRuta(candidatos)

17. V ß invertirArreglo(V)

18. retornar V.

6. Implementación

El programa fue implementado en el lenguaje de programación Java, versión de JDK: 1.6. Usando el IDE: JCreator.

6.1 Función de obtención de ruta con máximo flujo

Entrada: Matriz de adyacencia, nodo fuente, nodo sumidero

Salida: Conjunto de nodos que conforman la ruta óptima.g

public int[] getRutaMaxFlujo(int s, int t)

{

/*

-------------------------------------------------------

DECLARACION DE VARIABLES LOCALES

-------------------------------------------------------

*/

//Nodos que han sido visitados

int[] X=null;

//Aristas o par de nodos candidatos para formar

//la ruta con maximo flujo

/*

Estructura "Candidatos"

----------------------------------

| i | j | ref | considerar

----------------------------------

donde:

i: es el nodo que ha sido visitado, pertenece a X.

j: es el nodo que no ha sido visitado, pertenece a -X.

ref: hace referencia a que par de candidatos lo generaron.

considerar:

=0: borrado logico

=1: considerar para el siguiente proceso

*/

int[][] candidatos=null;

//candidatos=new int[4][0];

int nCandidatos=0;

// Valor PHI[i], que representa el max flujo que tolera en nodo i.

int[] phi=new int[nNodos];

// Nodo que actualmente sera la entrada para buscar nuevos nodos

// hacia el destino "t"

int nodo=s; //Se iniciliza con el nodo origen de la busqueda: "s"

// Cantidad de nodos visitados es 1, ya que estamos visitando

// por defecto el nodo inicial: "s"

int nVisitados=1;

// Indice que almacena el ultimo registro considerado

int index=-1;

int nodoI=-1;

int nodoF=-1;

int i=0;

int[] ruta=null;

System.out.println("Nodo Inicial: "+s);

System.out.println("Nodo Final: "+t);

/*

-------------------------------------------------------

PROCEDIMIENTO REALIZADOS POR EL ALGORITMO DE MAXIMO FLUJO

-------------------------------------------------------

*/

//Donde "1' 000, 000" representa un valor "infinito"

inicializarArreglo(phi,1000000);

//El primer nodo: que es el nodo origen, lo tomamos como "visitado",

// agregandolo al conjunto de los X.

X=redimensionarArreglo(X,nodo);

//Vamos recorriendo todas las rutas, aplicando el corte minimo

//con flujo maximo para cada subgrafo tomado hasta:

// 1. poder hallar el destino

// ó

// 2. hasta que ya no hayan nodos por recorrer

//reportarArreglo(X,"X");

while( nVisitados<=nNodos && nodo!=t ){

candidatos=calcularCandidatos(nodo,candidatos,X,index);

if(candidatos==null)

{

nCandidatos=0;

}

else{

nCandidatos=candidatos.length;

}

// reportarMatrizCandidatos(candidatos);

//Almacena los valores minimos temporales

int[] valorMin=new int[nCandidatos];

// System.out.println("n: "+nCandidatos);

for(i=0;i

if( candidatos[i][3]==1 ) {

nodoI=candidatos[i][0];

nodoF=candidatos[i][1];

valorMin[i]=hallarValorMinimo(phi[nodoI],ady[nodoI][nodoF]);

}

}

index=getIndexValorMaximo(valorMin);

phi[candidatos[index][1]]=valorMin[index];

nodo=candidatos[index][1];

X=redimensionarArreglo(X,nodo);

nVisitados=X.length;

}

candidatos=calcularCandidatos(nodo,candidatos,X,index);

if(candidatos!=null){

nCandidatos=candidatos.length;

//Modificamos el par ultimo porque no debe hacer referencia a nada

candidatos[nCandidatos-1][1]=-1;

}

reportarMatrizCandidatos(candidatos);

ruta=hallarRuta(candidatos);

ruta=invertirArreglo(ruta);

ruta=redimensionarArreglo(ruta,t);

reportarArreglo(ruta);

return ruta;

}

//***************************************************************************

6.2 Descripción de interfaces
6.2.1 Frame principal

Programa que acepta un grafo, haciendo clic sobre la pantalla.

Programa que acepta un grafo, haciendo clic sobre la pantalla. Y usa una imagen de fondo de la ciudad para establecer un rastreo preciso.

6.2.2 Descripción de elementos

Imagen	Nombre	Descripción
	Ejemplo	Este botón permite mostrar un ejemplo, de enrutamiento en el centro de la ciudad de Trujillo. Sólo se necesita especificar el origen y destino, y luego ( correr), para calcular la solución.
	Nodo origen	Se inserta el número de nodo, que se establece como origen de la ruta.
	Nodo destino	Nodo que es el objetivo final, donde se quiere llegar.
	Horario	Permite seleccionar en que horario se encuentra el conductor, para poder seleccionar el adecuado, esto permite evaluar la red cuando se encuentra en ese horario y obtener una respuesta acertada.
	Visualizar mapa	Permite seleccionar o bien visualizar el grafo solo, o visualizar el grafo junto al mapa en formato “jpg” o “png”
	Abrir	Abre el grafo de una red vial, guardado anteriormente por el programa.
	Abrir mapa	Cambia de mapa, para la configuración de otra red vial. Acepta figuras en formato: “jpg” y “png”
	Correr programa	Permite ejecutar la búsqueda de máximo flujo a través de todo la red vial dada y los nodos de origen y destino configurados.
	Guardar red vial	La red vial es un grafo que se puede montar encima de un mapa, es grafo contiene información acerca de los nombres de las calles y las conexiones entre diversas calles. Esta información pude ser guardada para su posterior uso.

7. Pruebas

Para facilitar el aprendizaje de la interacción con la aplicación presentada, a continuación se describen, a través de un ejemplo, un conjunto de pasos sobre los cuales podemos evaluar el análisis de red vial que se realiza sobre una zona de la ciudad de Trujillo para encontrar la ruta más óptima, tomando en cuenta la cantidad de autos que pueden circular por una autopista por determinados horarios de la semana.

Paso 1

Abrimos la aplicación, inmediatamente observaremos que se carga en la pantalla el mapa de una zona de la ciudad de Trujillo tal y como se vé en la siguiente figura

Paso 2

Para hacer la prueba que hemos preparado como demostración hacer click sobre el botón Probar Demo 1 que se encuentra sobre la barra de menú desplegable. Automáticamente aparecerá sobre el mapa la representación en forma de grafo de una zona del mapa. Observar la siguiente figura.

Como se puede observar, en el grafo cada nodo representa una esquina de determinada calle o avenida y se interconecta con otro nodo a través de aristas, las cuales representan la red por donde circula el trafico (pistas). Por ende, cada red tiene un campo nombre y un campo tráfico para un determinado horario de la semana; estos campos se representan, por ejemplo: Gamarra 4 – 6, lo cual significa que dicha arista indica que es la cuadra 4 de la calle Gamarra y que en el horario de Lun-Jue [mañana] (de Lunes a jueves por la mañana) se permite un tráfico de a lo más 6 autos por dicha calle.

El grafo que representa la red vial de una zona de Trujillo ha sido representado a través de 6 horarios distintos, los cuales son: Lun-Jue [mañana], Lun-Jue [tarde], Lun-Jue [noche], Vie-Dom[mañana], Vie-Dom[tarde], Vie-Dom[noche]; todas estas opciones se encuentran en la barra de menú deplegable y pueden ser usadas cuando se deseen. Por ejemplo, al cambiar la opción por el horario de Vie-Dom[tarde], todo se mantiene igual, excepto el campo tráfico de cada arista. Este factor es muy importante e imprescindible para que el calculo del flujo máximo tenga sentido y amplia utilidad en nuestra realidad.

Paso 3

Si deseamos cambiar de vista y solo observar el grafo, podemos acceder a la opción Mostrar Grafo que se encuentra en la barra de menú desplegable. Observar la siguiente figura.
Estando en este modo de vista podemos regresar a observar el mapa con tan solo acceder a la opción Mostrar Mapa y Grafo.
Cabe resaltar que este cambio de modo no altera para nada la representación del mapa a través del grafo.

Paso 4

Sea el modo de visualización en el que nos encontremos podemos encontrar la ruta más óptima desde un determinado punto de la ciudad hacia otro en un determinado horario.
Para esto debemos escribir en las casillas de texto el número del nodo origen y el número del nodo destino, correspondientemente (ingresar valores válidos representados por los nodos del grafo actual). Luego debemos escoger el horario sobre el cual queremos obtener el camino más corto con mayor flujo.

Por ejemplo podemos colocar como nodo origen el nodo 7 y como nodo destino el nodo 23, elegimos el horario Vie-Dom [tarde] y hacemos click sobre el botón de ejecución.Lo primeo que obtenemos es una ventana de información, le hacemos click en Aceptar y podemos visualizar los resultados. El camino que indica la ruta más corta desde el nodo 7 hacia el 23 con mayor flujo (mayor cantidad de autos que pueden circular por cada vía) se visualizará con una línea de color rojo. Ver las siguientes figuras.

Podemos elegir la opción opción Mostrar Mapa y Grafo y el resultado se observaría como se muestra en la siguiente figura.

Ahora, para observar las diferencias de resultados que ocasionan la elección de circular de un origen hacia un destino en distintos horarios en una red vial, cambiaremos de horario al Lun-Jue [noche], el resultado se visualiza en la siguiente figura.

Nótese que para el mismo nodo de origen y el mismo nodo destino, en diferentes horarios, en los que la cantidad aceptable de tráfico es diferente, se obtienen resultados diferentes.

En la siguiente figura se puede observar una comparativa de lo expuesto en el presente proyecto. Se tiene un mismo plano de red vial representado a través de un grafo, donde, partiendo desde un mismo nodo origen y dirigiéndonos hacia un mismo nodo destino obtenemos rutas diferentes para horarios diferentes, en los que, el flujo de tráfico es diferente.

Este trabajo fue realizado por Jorge Valverde Rebaza y yo para el curso de Tópicos en Informática Teórica, el cual nos sirvió de base para el planteamiento de un nuevo algoritmo de análisis de red.
Estos tipos de trabajos se vienen desarrollando desde hace décadas en países desarrollados, el principal objetivo es optimizar cualquier proceso de índole comercial. En este caso nos enfocamos en la navegación en auto a través de una red vial en la ciudad de Trujillo. Usamos los mapas de google para poder tener una imagen real de la ciudad y lo enmallamos para poder ejecutar el algoritmo de Ford y Fulkerson en la maximización de flujo, sin embargo nótese que el algoritmo de Ford-Fulkerson ha sido modificado para dar sólo una iteración, ya que sólo lo queremos para realizar un viaje de un nodo origen hacia un nodo destino.

Algunas referencias:

[1] Jon Kleinberg, Algorithm Design, Capítulo 7: Flujo de redes. 2005

http://www.cs.princeton.edu/~wayne/kleinberg-tardos/07maxflow.pdf

[2] Hong Chen, Introduction to Min-Cut/Max-Flow Algorithms.

http://homepages.cwi.nl/~lex/files/histtrpclean.pdf

[3] Kevin Wayne, Max Flor, Min Cut. 2004

http://www.math.wm.edu/~rrkinc/maxflow.pdf