IA













FACULTAD DE INGENIERÍA
ESCUELA PROFESIONAL DE INGENIERÍA DE SISTEMAS







CURSO : Inteligencia Artificial


DOCENTE : Ing. Julio Tenorio, Mg


INTEGRANTES :


Kong Arana, Andres
Rivera Espinola, Holger
Trujillo Cárdenas, José
Vega Santos, Marvin


CICLO : VIII



TRUJILLO – PERÚ
2014
Introducción

En inteligenciaartificial el tema de búsquedas es central, dado que, por ejemplo, realizar acciones mecanizadas o resolver problemas, se reduce a buscar en un espacio de estados. En esta disciplina se estudiará búsquedas inteligentes (búsqueda avara, A*, IDA*, A* restricta por memoria simplificada, ascenso de cima, etc.)

Las estrategias de búsqueda no informada resuelven problemas mediante generaciónsistemática de estados, pero son muy ineficientes.

Vamos a ver como las estrategias de búsqueda informada o heurística, usando conocimiento específico del problema, pueden resolver problemas más eficientemente.


No se discute que las búsquedas aumenten "explosivamente" cuando el espacio de problema se vuelve demasiado vasto por bifurcación de nodos a buscar o por incorporación de más variables.

Paraanalizar estos métodos de búsqueda fue necesario hacer investigaciones y aplicaciones sistematizadas para entender y explicar la función de cada uno de estos métodos de búsqueda, siendo de gran aporte para el desarrollo de este proyecto de investigación, esto permitió identificar las relaciones e interacción de los distintos métodos de búsqueda.







Búsqueda Informada (Heurística)


La búsquedaheurística utiliza información adicional sobre el problema específico como el coste ó la distancia al estado final; pudiendo encontrar soluciones de una manera más eficiente.

Las estrategias de búsqueda heurística se caracterizan por la tendencia a limitar el tiempo y el espacio en donde buscar la respuesta a problemas complejos.

A su vez se pueden dividir en tres tipos de búsqueda:

-Búsqueda preferente por lo mejor.
Búsqueda limitada por la capacidad de la memoria.
Búsquedas de mejoramiento iterativo
Búsqueda preferente por lo mejor

Esta búsqueda consiste en expandir primero aquél nodo con mejor evaluación. Dicha evaluación es el resultado de aplicar la función de evaluación al nodo, la cual devuelve un número que sirve para representar lo deseable que sería laexpansión de un nodo.

Dentro de este tipo de búsqueda se encuentran:

Búsqueda ávara (voraz) ó búsqueda primero el mejor
Búsqueda A*





Búsqueda ávara (voraz) ó búsqueda primero el mejor

Es una de las más sencillas estrategias en la BPPLM, que consiste en reducir al mínimo el costo estimado para lograr una meta.

En otras palabras, el nodo cuyo estado se considere más cercano a la meta en términosde costo de ruta se expande primero.

Aunque casi siempre es posible calcular el costo aproximado hasta la meta, es difícil hacerlo con precisión.

La función utilizada para dicho estimado del costo se llama función heurística, simbolizada por h.

Dónde:

h(n) = costo estimado de la ruta más barata que une el estado del nodo n con un estado meta.
h puede ser cualquier función. El únicorequisito es que
h(n) = 0 cuando n es una meta.
La mejor heurística para la determinación de rutas en el mundo real es la distancia en línea recta a la meta:
hDLR (n) = distancia en línea recta entre n y la meta



Mapa de Rumania con costes de operador en Km
Aplicamos el método de búsqueda voraz:
La función de evaluación es h(n) (función heurística): estimación del coste del nodo al objetivo.Expande primero el nodo no expandido que supone acercarse más al objetivo (supone un mayor “bocado” en el coste que resta hasta el objetivo)
Implementación:
Eval-Fn = h

Ejemplo de función heurística para el problema de hallar rutas en Rumania:
hDLR(n) = distancia en línea recta de n a Bucarest

h puede ser cualquier función siempre y cuando h(n) = 0 en los nodos que representan estados...