BÚSQUEDA INFORMADA

Fecha de Clase: 18 -22 de Mayo 2015

INTRODUCCIÓN

En este documento se va a detallar información acerca de la búsqueda informada o heurística, demostrando la importante de su estudio ya que está a diferencia  de la búsqueda no informada puede encontrar soluciones más eficientes a problemas específicos. Las búsquedas informadas también han desarrollado estrategias que han dado buenos resultados, y han minimizado la media de tiempo, es por esto que las estrategias de este tipo de búsqueda son muy utilizados en problemas complejos. En este documento se va ampliar la estrategia de búsqueda voraz primero el mejor, destacando sus principales característica y mostrando un ejemplo de aplicación.

OBJETIVO

Identificar las búsquedas informada y conocer sus diferentes estrategias.

MARCO TEÓRICO

¿QUÉ ES LA HEURÍSTICA?

Heurística significa encontrar, hallar o descubrir, esta palabra proviene del griego “heuriskein”.
La heurística es muy utilizado en los algoritmos de búsquedas puestos que estas ayudan a guiar el proceso de búsqueda, y permiten obtener soluciones de buena calidad, aunque no sean siempre las mejores, pero consiguen buenos resultados en la media de tiempo que las búsquedas emplea.

VENTAJAS DE UTILIZAR LA HEURÍSTICA

Debido a que la heurística, ayuda a resolver problemas complejos, se presentan las siguientes ventajas:

Generalmente para problemas complejos no necesitamos siempre obtener la solución más óptima, solo se necesita resultados buenos.

Utilizando la heurística, no vamos  a encontrar caso críticos, ya que siempre da soluciones.

Deducir como funciona la heurística, nos da un conocimiento  mayor de los problemas que queremos resolver.

BUSQUEDAS INFORMADAS (HEURÍSTICA)

La búsqueda informada, son aquellas que poseen la definición e información específica del problema como coste del estado actual al objetivo. Este tipo de búsquedas es muy eficiente en la obtención del objetivo, ya que es capaz de medir la calidad de un estado, con esto nos permite obtener mejor resultados y encontrar caminos más cortos para llegar a nuestro estado objetivo, es importante recalcar que la búsqueda informada es más efectiva y eficiente que la búsqueda no informada. La búsqueda informada presenta las principales estrategias de búsquedas:

Estas estrategias son las más conocida en la búsqueda informadas, pero en este documento se va a destacar la búsqueda voraz primero el mejor.

VORAZ PRIMERO EL MEJOR

Esta búsqueda también es conocida como búsqueda avara o búsqueda de Greedy.

Según Russell y Norvig “La búsqueda voraz primero el mejor trata de expandir el nodo más cercano al objetivo, alegando que probablemente conduzca rápidamente a una solución. Así, evalúa los nodos utilizando solamente la función heurística: f(n) = h(n)”.

f(n) -> Función evaluación -> selección del nodo de expansión con la evaluación más baja.

h(n) -> Función heurística -> coste estimado del camino más barato desde el nodo na un nodo objetivo.

Esta estrategia no siempre ofrece la solución más óptima, sin embargo brindas buenos resultados.

CARACTERISTICAS

• Completitud: no, ya que muchas veces puede perderse en bucles.
• Optimización: la solución no siempre es la más óptima.
• Complejidad temporal: con una buena aplicación heurística se pueden conseguir mejores resultados en el tiempo de la búsqueda.
• Complejidad espacial: almacena todos los nodos de la búsqueda.

EJEMPLO DE VORAZ PRIMERO EL MEJOR

Realizar una búsqueda de voraz primero el mejor, donde el estado inicial es Calceta y el estado objetivo es Portoviejo véase en imagen 1, utilizando los datos de la tabla 1.

Tabla 1. Función Heurística

Imagen 1. Mapa de Calceta a Portoviejo

En este caso encuentra una solución de forma directa como se muestra en la Imagen 2, pero no es la solución más óptima, lo más óptima seria de Calceta -> Junín -> Portoviejo vease en la imagen 1.

Imagen 2. Solución aplicando la búsqueda voraz primero el mejor

CONCLUSIÓN

Como conclusión puedo decir que las búsquedas informadas son más eficaces que las búsquedas no informadas, gracias a la heurística este tipo de búsqueda resulta de alta calidad, y muy eficiente al momento de realizar una búsqueda.

Las búsquedas informadas como ya se dijo anteriormente poseen información específica del problema lo que ayuda que este tipo de búsqueda siempre entregué una solución, aunque no siempre suele ser la más óptima. Sin embargo  el objetivo de toda búsqueda, simplemente es dar una solución.

La estrategia voraz primero el mejor, no es la más eficiente  ya que no siempre entrega las soluciones más óptimas, como pudimos verlo reflejado en el ejemplo que se presentó.

BIBLIOGRAFÍA

Russell, S. y Norvig, P. 2004. INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. PEARSON EDUCACION. 2 ed. Madrid.

Rentería, R. 2011. ALGORITMOS DE BÚSQUEDA. Consultado 21 de Mayo. 2015. Formato PDF.

____. 2008?. RESOLUCIÓN DE PROBLEMAS MEDIANTE BÚSQUEDA. Consultado 21 de Mayo del 2015. Formato PDF.

____. 2005?. BUSQUEDA INFORMADA (HEUURISTICA). Consultado 21 de Mayo del 2015. Formato PDF.

Benítez, I. 2010. RESOLUCIÓN DE PROBLEMAS MEDIANTE BÚSQUEDA INFORMADAS.

Centro de Inteligencia Artificial. 2011. SISTEMAS INTELIGENTES: BUSQUEDA HEURISTICA. 

BÚSQUEDA NO INFORMADA

Fecha de Clase: 4 - 8 de Mayo 2015

INTRODUCCIÓN

En esta clase se estudió los algoritmos de búsquedas no informadas o también conocidas como búsquedas a ciegas, el estudio de esta búsqueda es indispensable puesto que se han desarrollados diferentes tipos de estrategias que son aplicados según el problema.

Las estrategias de las  búsquedas no informadas han sido de gran ayuda para darle solución a diferentes tipos de problemas, estas son utilizadas de  acuerdo a  la búsqueda que se realice, siendo de mucha utilidad en este proceso.

OBJETIVO

Identificar las búsquedas no informada y conocer sus diferentes estrategias.

MARCO TEÓRICO

BÚSQUEDA NO INFORMADA

Las búsquedas no informadas son aquellas, son aquellas que no poseen información extra simplemente cuenta con la definición del problema, estas búsquedas solo pueden generar sucesores y distinguir entre un estado objetivo de uno que no lo es. La búsqueda no informada presenta seis estrategias de búsquedas:

                  

En este documento se hablara de la búsqueda primero en anchura y la búsqueda primero en profundidad ya que de estas dos estrategias de búsquedas son la base para el desarrollo de las demás estrategias búsquedas.

CRITERIOS DE EVALUACIÓN DE LAS ESTRATEGIAS: »Completitud: llegar al  objetivo o encontrar la solución.

»Optimización: encontrar la solución más óptima.

»Complejidad espacial: cuanto espacio de memoria necesita

»Complejidad temporal: el tiempo necesario para realizar la búsqueda.

LAS COMPLEJIDADES TEMPORAL Y ESPACIAL SE MIDEN EN TÉRMINOS DE:

b -> factor de ramificación ->  Es el máximo número de sucesores de cualquier nodo dentro del árbol de búsqueda

m ->longitud máxima del árbol de búsqueda -> es la longitud de cualquier camino en el espacio de estados

d -> profundidad de la mejor solución -> es la profundidad del nodo objetivo más superficial de menor coste.

BÚSQUEDA PRIMERO EN ANCHURA

Esta estrategia de búsqueda es completa y óptima. Según Russell y Norvig la búsqueda primero en anchura: “Es una estrategia sencilla en la que se expande primero el nodo raíz, a continuación se expanden todos los sucesores del nodo raíz, después sus sucesores, etc. En general, se expanden todos los nodos a una profundidad en el árbol de búsqueda antes de expandir cualquier nodo del próximo nivel”.

Utiliza la estructura FIFO, puesto que esta estrategia siempre expande primero el nodo más antiguo, es decir el menos profundo.

ESTRATEGIA:

•     La búsqueda en el árbol  se realiza por niveles de profundidad
•    En la búsqueda primero en anchura expande todos los nodos de nivel n, antes de expandir nodos de nivel n+1. Figura 1

Figura1. Esquema de la búsqueda primero en anchura

CARACTERÍSTICAS

• Completitud: Esta estrategia siempre llaga al estado objetivo
• Optimización: esta búsqueda es óptima según el número de niveles que tenga desde la raíz hasta encontrar la solución.
• Complejidad espacial: involucra a la exponencial del factor ramificación y la profundidad en la que se halle la solución.
• Complejidad temporal: este depende de la profundidad en la que se encuentre la solución y al factor ramificación.

EJEMPLO DE  LA BUSQUEDA PRIMERO EN ANCHURA

Realizar una búsqueda primero en anchura donde el estado inicial es A y el estado objetivo es N

Recorrido de A:N = {A,B,C,D,E,F,G,H,I,J,K,L,M,N}

BÚSQUEDA PRIMERO EN PROFUNDIDAD

Esta estrategia de búsqueda siempre se comienza a expandir por el nodo más profundo y dando comienzo por el la do izquierdo en el árbol de búsqueda. Una vez que se hayan expandido todos los nodos, es decir cuando los nodos ya no posean ningún sucesor, se retrocede al nodo más superficial que tenga sucesores que no hayan sido expandidos.

La búsqueda en profundidad no es la más óptima,  ni el más completo, puesto que en muchas ocasiones no puede acabar la búsqueda o elije el peor camino. Utiliza una cola LIFO primero en entrar último en salir en la frontera de la búsqueda, este algoritmo maneja sencillos requisitos en la memoria, ya que almacena el camino del nodo raíz al nodo hoja, incluyendo a los nodos hermanos que no han sido expandidos.

Estrategia:

•  La búsqueda en el árbol  se realiza por el nodo más profundo (comenzando por el lado izquierdo del árbol)
•   Retrocede cuando no encuentra nodos sucesores. Figura 2

Figura 2. Esquema de la busqueda primero en profundidad

CARACTERÍSTICAS

• Completitud: esta estrategia encuentra la solución, pero muchas veces es necesario poner un límite.
• Optimización: la solución no siempre es la más óptima.
• Complejidad temporal: depende del factor ramificación y de la profundidad que tuvo que explorar para encontrar la solución.
• Complejidad espacial: hay que tener en cuenta los nodos repetidos, por el coste lineal respecto al factor de ramificación y el límite de profundidad. (Rentería, R. 2011)

EJEMPLO DE  LA BUSQUEDA PRIMERO EN PROFUNDIDAD

Realizar una búsqueda primero en profundidad donde el estado inicial es A y el estado objetivo es K

Recorrido de A:K = {A,B,D,F,H,J,K }

CONCLUSIÓN

Las búsquedas no informadas son importante porque permiten resolver problemas que no cuenta con suficiente información a través de sucesores e identificando los estados hasta llegar a su estado objetivo. Las búsquedas a ciegas han desarrollado estrategias que son utilizadas de acuerdo a la búsqueda que se vaya a realizar.

Las búsquedas no informadas tiene estrategias,  sin embargo las más importante son la búsqueda primero en anchura y primero en profundidad son la base para la creación de otras estrategias. Siendo importante su estudio para conocer y  diferenciar  su funcionalidad y su aplicación. Estas estrategias tienen características que hacen identificar cuáles son los puntos débiles de cada búsqueda y resaltar cuáles son sus fuertes, para según esto escoger la estrategia más  adecuada de acuerdo al problema que nos plantemos.

BIBLIOGRAFÍA

Russell, S. y Norvig, P. 2004. INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. PEARSON EDUCACION. 2 ed. Madrid.

Rentería, R. 2011. ALGORITMOS DE BÚSQUEDA. Consultado 8 de mayo. 2015. Formato PDF.

Hermoso, R y Vasirani, M. 2011. BÚSQUEDA NO-INFORMADA. Consultado 8 de mayo. 2015. Formato PDF.

____. 2008. RESOLUCIÓN DE PROBLEMAS MEDIANTE BÚSQUEDA. Consultado 8 de mayo. 2015. Formato PDF.