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.