BUSQUEDA INFORMADA

INTRODUCCION.

En este capítulo hablaremos sobre la búsqueda informada, demostrando la importancia de su estudio ya que está a diferencia  de la búsqueda no informada puede encontrar soluciones más óptima a problemas específicos. Las búsquedas informadas  ha desarrollado estrategias que han dado buenos resultados. En este documento se tratara la estrategia de búsqueda voraz primero el mejor, destacando sus principales característica y mostrando algún ejemplo de cómo funciona dicha búsqueda.

MARCO TEORICO.

Se denomina búsqueda informada a aquella que busca una solución del problema, basado en un conocimiento del problema, que va más allá de la definición del problema en sí.

El primer conjunto de estrategias que analizaremos se denomina búsqueda primero el mejor, para expandir las ramas del árbol, se aplica una función de evaluación, en la cual se escoge el que tenga la evaluación más baja, debido a que la función calcula la distancia más corta a el objetivo.

Esta función de evaluación se conoce como función heurística, la función depende del tipo de problema, la función puede ser uno de los tantos modelos de la investigación de operaciones, programación lineal, programación entera, pert, cpm, etc.

BÚSQUEDA VORAZ PRIMERO EL MEJOR.

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).

Este método expande el nodo más cercano al objetivo fundamentando que este llegara rápidamente a una solución o un estado objetivo, en ciertos casos esto puede ser lo ideal, considerando la imagen a continuación notamos que están los dos nodos expandidos para comparar su forma de trabajo, pero este método como se mencionó solo expande el que es más cercano al otro nodo, en este ejemplo la respuesta optima es la que va a elegir el método voraz primero el mejor, pero en el caso de que el camino elegido por el método sea el más costoso, entonces no sería algo óptimo, ya que también se busca optimizar costos.

EJEMPLO DE VORAZ PRIMERO EL MEJOR

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

FUNCION HEURISTICA
CHONE	20
TOSAGUA	40
ROCAFUERTE	10
CALCETA	50
JUNIN	30
PORTOVIEJO	0

                     Tabla 1

Imagen 1 Mapa de Chone a Portoviejo

En este caso encuentra una solución de forma directa como se muestra en la Imagen 2.

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

BÚSQUEDA A*: MINIMIZAR EL COSTO ESTIMADO TOTAL

DE LA SOLUCIÓN

A la forma más ampliamente conocida de la búsqueda primero el mejor se le llama búsqueda A* (pronunciada ≪búsqueda A-estrella≫). Evalúa los nodos combinando g(n), 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) nos da el coste del camino desde el nodo inicio al nodo n, y la h(n) el coste estimado del camino más barato desde n al objetivo, tenemos:

F[t] = coste más barato estimado de la solución a través de n.

Así, si tratamos de encontrar la solución más barata, es razonable intentar primero el nodo con el valor más bajo de g(n) + h(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 completa como óptima.

En otros términos esta búsqueda se la realiza tomando en cuenta no solo el costo para llegar de un punto a otro, sino que también evalúa el costo heurístico, tomando el que signifique más económico será la respuesta adecuada, en el caso que se encuentren más de una solución se toma la primera encontrada.

CONCLUSIÓN.

Podemos concluir que el estudio de esta búsqueda es más eficaz que la búsqueda no informada para problemas específicos aunque existen algunas estrategias, ya que esta reduce el árbol y se basa en el coste mínimo para alcanzar su meta en un problema específico.

BIBLIOGRAFÍA.

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

Busqueda Informada  Consultado, 17 de Oct. 2015. Formato HTML. Disponible http://sistemasumma.com/2010/09/11/busqueda-informadaheuristica/