BÚSQUEDA BIDIRECCIONAL

Fecha: 16 Octubre 2014

OBJETIVO DE CLASE E INTRODUCCIÓN 

La clase impartida la fecha mencionada anteriormente estaba basada en exposiciones por parte de mis compañeros, la búsqueda bidireccional era una pequeña parte que estaba compartiendo un compañero. Esta entrada al blog se basara en Ampliar un poco más el concepto teórico y práctico  de la búsqueda bidireccional.

MARCO TEÓRICO

• DEFINICIÓN

Buscar bidireccionalmente, es  como su nombre lo indica, búsquedas en dos direcciones al mismo tiempo: uno hacia adelante desde el estado inicial y el otro hacia atrás de la parte final. Esto se hace generalmente mediante la expansión de árbol con factor de ramificación b y la distancia desde el principio hasta el objetivo es d. La búsqueda se detiene cuando búsquedas desde ambas direcciones se reúnen en el centro. Búsqueda bidireccional es un algoritmo de búsqueda de fuerza bruta que requiera un estado objetivo explícito en lugar de simplemente una prueba para una condición meta (Robin. 2009)

La idea de una búsqueda bidireccional es reducir el tiempo de búsqueda mediante la búsqueda hacia adelante desde el comienzo y hacia atrás de la estancia simultáneamente. Cuando las dos fronteras de búsqueda se cruzan, el algoritmo puede reconstruir un único camino que se extiende desde el estado de inicio a través de la intersección de frontera a la meta. (Poole. 2010 ) . Una técnica que ha demostrado ser útil en el camino más corto y otra discreta cálculos de optimización ha sido la búsqueda bidireccional. El método tiene  sido bien probado en el de dos nodos problema del camino más corto proporciona sustancial  ahorros computacionales. Un impulso natural es extender sus beneficios a heurística búsqueda (Thomas. sf )

• ENFOQUES PARA BÚSQUEDA BIDIRECCIONAL

Algoritmos bidireccionales pueden ser ampliamente divididas en tres categorías: Front-to-Front, Front-to-Back (o Front-to-End), y Perímetro de la búsqueda (Kaindl Kainz 1997). Estos se diferencian por la función utilizada para calcular la heurística.

Front-to-Back

Algoritmos de adelante hacia atrás calculan el valor h de un nodo n utilizando la estimación heurística entre n y la raíz de lo contrario árbol de búsqueda. Front-to-Back es el investigado más activamente de las tres categorías. La corriente mejor algoritmo (al menos en el dominio Quince rompecabezas) es la Bimax-BS * F algoritmo, creado por Auer y Kaindl (Auer, Kaindl 2004).

Front-to-Front

Algoritmos de frente a frente calculan el valor h de un nodo n utilizando la estimación heurística entre n y algún subconjunto de OPEN_d ‘. El ejemplo canónico es el de la (algoritmo bidireccional heurístico Front-a-Front)  BHFFA  (de Champeaux 1977/1983), donde la función h se define como el mínimo de todas las estimaciones heurísticas entre el nodo actual y los nodos en la parte frontal opuesta. O bien, formalmente:

Donde H (n, o) devuelve un (es decir, no sobrestimar) estimación heurística admisible de la distancia entre los nodos n y o. Frente-a-Frente sufre de ser excesivamente exigentes computacionalmente. Cada vez que un nodo n se pone en la lista abierta, se debe calcular su valor f = g + h. Esto implica calcular una estimación heurística de N a cada nodo de lo opuesto al  conjunto abierto, como se describió anteriormente. Los conjuntos abiertos aumentan de tamaño de forma exponencial para todos los dominios con b> 1

• EJEMPLO DE UNA BÚSQUEDA BIDIRECCIONAL CON EL ALGORITMO DE DIJSKTRA

Algoritmo de Dijkstra, concebida por el informático Edsger Dijkstra en 1956 y publicado en 1959, es un algoritmo de búsqueda gráfica que resuelve la sola fuente problema del camino más corto para un gráfico con costes de ruta borde no negativos, produciendo una menor árbol de ruta. Este algoritmo se utiliza a menudo en el enrutamiento y como una subrutina en otros algoritmos de grafos.

A continuación Existe un video que explica la aplicación de una búsqueda bidereccional aplicada en el algoritmo de Dijkstra

  CONCLUSIÓN

Una búsqueda bidireccional está basado en el criterio exhaustivo de búsqueda, es decir busca su meta en dos direcciones basándose en el concepto de fuerza bruta para llegar a su objetivo.  Este algoritmo de búsqueda es muy investigado para encontrar la ruta más corta, algunos aspectos negativos está en los costes que genera en enrutamiento en sus grafos, pero eso es relativo a la velocidad que aplica para llegar a su meta.

BIBLIOGRAFÍAS 

Robin,  D.2010.  Búsqueda Bidireccional .Consultado 10 de Oct .(En línea).Formato HTML. Disponible en : http://intelligence.worldofcomputing.net/ai-search/bidirectional-search.html#.VKgbgiuG8po

Poole,  D.2010.  Búsqueda Bidireccional .Consultado 10 de Oct .(En línea).Formato HTML. Disponible en : http://artint.info/html/ArtInt_65.html

Thomas,  J. sf .  Búsqueda Bidireccional .Consultado 10 de Oct .(En línea).Formato PDF. Disponible en : http://aitopics.org/sites/default/files/classic/Machine%20Intelligence%206/MI6-Ch9-Pohl.pdf

Kaindl, H. .  networks 2004: 11th International Telecommunications Network Strategy and Planning Symposium, VDE Verlag, 2004, p. 464.

HEURÍSTICA

Calceta 9 de Octubre del 2014

INTRODUCCIÓN

Las clases comenzaron por una lectura y análisis de búsquedas, las primeras en ser mencionadas y más a conocidas fueron la búsqueda por anchura y profundidad. En resumen se trató un tema llamado como Heurística que definiremos a continuación.

La metodología aplicada el día de clase fue  análisis de compresión lectora que asume la idea de compartir contenido obtenido del libro de trabajo  los compañeros presentes. Se analizó también un slider y se resolvió un puzle de 3*3.

MARCO TEÓRICO

En informática, la inteligencia artificial, y la optimización matemática diseño  una técnica diseñada para resolver un problema más rápidamente cuando los métodos clásicos son demasiado lentos llamada Heurística, o para encontrar una solución aproximada cuando los métodos clásicos no encuentran ninguna solución exacta. (Dechter. 1985).

Una de las aplicaciones más conocidas es el Best-First Search ; este y sus variantes más avanzadas se han utilizado en aplicaciones tales como juegos y rastreadores web. En un rastreador web, cada página web es tratada  como un nodo, y todos los hipervínculos en la página son tratados como nodos sucesores no visitados. Un rastreador que utiliza mejor primera búsqueda generalmente utiliza una función de evaluación que asigna prioridad a los vínculos en función de cómo de cerca el contenido de la página padre se asemejan a la consulta de búsqueda (Menczer, Pant, Ruiz, y Srinivasan, 2001). En los juegos, mejor primera búsqueda se puede usar como un algoritmo de ruta de investigación para los personajes del juego. Por ejemplo, podría ser utilizado por un agente enemigo para encontrar la ubicación del jugador en el mundo del juego. Algunos juegos dividen el terreno en «azulejos» que pueden o bien ser bloqueados o no bloqueados. En tales casos, el algoritmo de búsqueda trata cada azulejo como un nodo, con los vecinos azulejos bloqueados son nodos sucesores, y el nodo objetivo siendo la baldosa de destino (Koenig, 2004).

BUSQUEDA POR ANCHURA

En la teoría de grafos, búsqueda por amplitud  (BFS) es una estrategia para la búsqueda en un grafo  cuando la búsqueda se limita esencialmente a dos operaciones: (a) la visita e inspección de un nodo de un gráfico; (b) tener acceso a visitar los nodos que los vecinos del nodo actualmente visitado. El BFS comienza en un nodo raíz e inspecciona todos los nodos vecinos. Entonces, para cada uno de esos nodos vecinos, a su vez, se inspecciona sus nodos vecinos, que eran no visitado, y así sucesivamente.

BFS se inventó a finales del 1950 por EF Moore y en un principio utilizado para encontrar el camino más corto para salir de un laberinto (Skiena. 2008).

En el análisis de algoritmos, la búsqueda por amplitud  se supone que se lo realiza en un grafo finito, representado explícitamente como una lista de adyacencia o representación similar. Sin embargo, en la aplicación de métodos gráfico de recorrido de la inteligencia artificial en la entrada puede ser una representación implícita de un grafo  infinito. En este contexto, un método de búsqueda se describe como completa si está garantizado para encontrar un estado final, si existiera. Búsqueda en amplitud es completa, pero la búsqueda en profundidad no es: cuando se aplica a los gráficos infinitos  representados implícitamente, puede perderse en algunas partes de la gráfica que no tienen ningún estado de la meta y nunca regresan (Coppin. 2004)

BÚSQUEDA POR PROFUNDIDAD

La búsqueda en profundidad (DFS) es un algoritmo para el desplazamiento o la búsqueda de árboles o estructuras de datos del gráfico. Uno comienza en la raíz (seleccionar algún nodo arbitrario como la raíz en el caso de un gráfico) y explora la medida de lo posible a lo largo de cada rama antes de dar marcha atrás.

Una versión de búsqueda en profundidad se investigó en el siglo 19 por el matemático francés Pierre Charles Tremaux (Public conference. 2010) como una estrategia para resolver laberintos (Even. 2011), (Sedgewick. 2002)

 

CONCLUSIÓN

Las búsquedas que se utilizan en la IA se  tienen que ser necesariamente óptima debido al objetivo que se quieren conseguir, dado que la inteligencia artificial  trata de  mejorar técnicas de Heurística definidas,  para hacer de esta rama un aporte importante de la ciencia.

Existen varios tipos de búsqueda pero en este blog solo analizamos las dos primeras y más conocidas de las cuales se desprenden un sinnúmero de ramas.  La búsqueda por anchura implica analizar un grafo de forma horizontal y por profundidad de forma vertical  no se pude definir cuál es el óptimo porque eso estaría relacionado a la complejidad del problema a resolver.

BIBLIOGRAFÍA

Dechter, R. & Pearl, J. 1985 . Generalized Best-First Search Strategies and the Optimality of A*. Journal of the Association for Computing Machinery, 32, 505-536.

Menczer, F., Pant, G., Ruiz, M.E. & Srinivasan, P.  2001. Evaluating Topic-Driven Web Crawlers. Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval (pp. 241-249). New York: Association for Computing Machinery.

Koenig, S. 2004 . A Comparison of Fast Search Methods for Real-Time Situated Agents. Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems – Volume 2 (pp. 862-871). Washington, DC: IEEE Computer Society.

Skiena, S .  2008. The Algorithm Design Manual. Springer. p. 480

Coppin, B. 2004. Artificial intelligence illuminated. Jones & Bartlett Learning. pp. 79–80.

Charles Pierre Trémaux (1859–1882) École Polytechnique of Paris (X:1876), French engineer of the telegraph

Public conference, December 2, 2010 – by professor Jean Pelletier-Thibert in Académie de Macon (Burgundy – France) – (Abstract published in the Annals academic, March 2011 – ISSN: 0980-6032)

Even, S . 2011 , Graph Algorithms (2nd ed.), Cambridge University Press, pp. 46–48, ISBN 978-0-521-73653-4.

Sedgewick, R. 2002, Algorithms in C++: Graph Algorithms (3rd ed.), Pearson Education, ISBN 978-0-201-36118-6.