Búsqueda Informada y explorada Introducción

Búsqueda Informada y explorada

Introducción

INTRODUCCIÓN

Los métodos de búsqueda hoy en día son muy implementados de lo cual existen varios métodos como lo son la informada y la explorada, aunque la explorada tiene carácter de ser bidireccional la informada tiene más eficiencia ya que cuenta con información previa gracias a la función heurística para llegar a su objetivo planteado mucho más rápido, al contrario de la explorada que puede que nunca llegar a encontrar su objetivo quedando en un ciclo infinito a continuación profundizaremos mas sobre el tema.

MARCO TEÓRICO

¿QUÉ ES UNA FUNCIÓN HEURÍSTICA?

Se deriva del griego heuriskein que significa “encontrar” o “descubrir” y en la rama de inteligencia artificial se la utiliza para referirse a técnicas que mejora el desempeño en los algoritmos de búsqueda.

 

BÚSQUEDAS INFORMADA

Este tipo de búsqueda implementa conocimiento específico de algún problema por el cual encuentra una solución mucho más eficiente que la búsqueda no informada de las cueles mostraremos dos tipos de búsquedas que implementa la función heurística para mejorar su desempeño.

Búsqueda A*

Búsqueda Primero el Mejor

BÚSQUEDA VORAZ PRIMERO EL MEJOR

Trata de escoger el nodo con el mejor valor que implemente un recorrido menor y seguir esa ruta que conduzca a una solución rápida y así evaluar los nodos con la función heurística (n)=h(n).

BÚSQUEDA A* MINIMIZAR EL COSTO

Se le llama búsqueda A* “búsqueda A-estrella”, evalúa cada nodos combinando g(n), para determinar el coste `para  alcanzar el nodo, y h(n), el coste de ir al nodo objetivo.

f(n)=g(n)+h(n)

Ya que la g(n) ofrece el recorrido entre el nodo inicial al nodo n dándonos su costo, y la h(n) nos da una estimación del coste del camino más economico desde el nodo n al nodo objetivo, tenemos un coste del camino más barato hacia nuestro nodo objetivo.

f(n)= consiste en alcanzar el coste más económico para el estimado de la solución a través de n

Así, tratamos de encontrar el camino más económico para dar solución a la problemática, es razonable intentar primero el nodo con el valor más bajo de g(n). Resulta que esta estrategia es más que razonable: con tal de que la función heurística h(n) satisfaga ciertas condiciones, la búsqueda A* es tanto compleja como óptima.

La optimiza de A* es sencilla de analizar si se usa con la BÚSQUEDA ARBOLES. En este caso, A* es óptima si h(n) es una heurística admisible, es decir, con tal de que la h(n) nunca subestime el coste de alcanzar el objetivo. Las heurísticas admisibles son por naturaleza optimistas, porque piensan que el coste de resolver el problema es menor que el que es en realidad. Ya que g(n) es el coste exacto para alcanzar n, tenemos como consecuencia inmediata que la f(n) nunca sobrestima el coste verdadero de una solución a través de n.

Ejemplo

CONCLUSIONES

Como pudimos observar métodos de búsqueda ayuda a determinar una mejor ruta para seguir el trayecto al nodo objetivo e implementado la función heurística para mejorarla de cuales son la busque informado de lo contrario de la explorada no implemente la función heurística por lo cual puede tardarse mas e incluso puede caer en un ciclo infinito y nunca llegar al objetivo planteado.

BIBLIOGRAFIA

Russell, S y Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. 2 ed. España. Pearson Education. p 1242

García. E. 2009. Vida e inteligencia artificial. Revista ACIMED. V 19 n. (En Línea). Consultado el 14 de Abril 2014. Disponible en: http://scielo.sld.cu/scielo.php?script