Busqueda sistematica

INSTITUTO TECNOLOGICO SUPERIOR DEL OCCIDENTE DEL ESTADO DE HIDALGO

BÚSQUEDA SISTEMÁTICA
TEMA 2.3

INTELIGENCIA ARTIFICAL
MATERIA

HECTOR DANIEL HERNANDEZ GARCIA
PROFESOR

ING. EN SISTEMAS COMPUTACIONALES 8 “A”
GRUPO

     

BAUTISTA CORONA FELIPE DE JESUS GONZAGA MATURANO SANDRA IDALY MAQUEDA BARCENAS LORENA MARTINEZ ANAYA FRANK FERNANDO MENDOZA CARBAJAL MARCOS TREJOBAUTISTA JOSE ANGEL
INTEGRANTES

Mixquiahuala de Juárez a 26 de febrero de 2010

Página 1

2.3 BUSQUEDA SISTEMATICA
Búsqueda: método computacional para resolver problemas. Sistemática: si existe una solución la encuentra • recorrido ordenado del espacio de estados • Si un estado no puede ser solución --> poda • No sistemática: pueden no encontrar la solución • Búsqueda local • Descenso porgradiente • Simulated annealing • Algoritmos genéticos • Búsqueda tabú • pueden visitar varias veces el mismo estado Los problemas de búsquedas, que generalmente encontramos en Ciencias Computacionales, son de un estado determinístico. Por ejemplo, en los algoritmos de búsqueda de anchura y de búsqueda de profundidad, uno sabe la secuencia de los nodos visitados en un árbol. Sin embargo, los problemasde búsqueda, los cuales siempre tendremos que tratar en Inteligencia artificial, son no determinísticos y el orden de elementos visitados en el espacio de búsqueda depende completamente en el conjunto de datos. Dependiendo de la metodología de expansión de un espacio de estado y consecuentemente el orden de los estados visitados los problemas de búsqueda se nombran diferentes: Búsqueda de Metas aProfundidad. Búsqueda de Metas en Anchura. Búsqueda Óptima.

2.3.1BÚSQUEDA DE METAS A PROFUNDIDAD
Es llamado así porque sigue cada camino hasta su mayor profundidad antes de moverse al siguiente camino. Asumiendo que iniciamos desde el lado izquierdo y trabajamos hacia la derecha, la búsqueda de metas por profundidad involucra trabajar todos los caminos debajo del camino de árbol más a laizquierda hasta que un nodo hoja es alcanzado. Si esta es una meta de estado, la búsqueda es completada y reportada de exitosa. La búsqueda de profundidad es usada por computadoras a menudo para los problemas de búsqueda como ubicar archivos en un disco, o por buscadores para “spidering” en Internet.

Mixquiahuala de Juárez a 26 de febrero de 2010

Página 2

EJEMPLO:

En la búsqueda enprofundidad se avanza de vértice en vértice, marcando cada vértice visitado. La búsqueda siempre avanza hacia un vértice no marcado, internándose “profundamente” en el grafo sin repetir ningún vértice. Cuando se alcanza un vértice cuyos vecinos han sido marcados, se retrocede al anterior vértice visitado y se avanza desde éste.

2.3.2 BÚSQUEDA DE METAS EN ANCHURA
Como su nombre indica, este enfoquesupone atravesar un árbol por anchura más que por profundidad. El algoritmo de anchura empieza examinando todos los nodos de un nivel (a veces llamado hebra uno) abajo del nodo raíz. Si una meta de estado es alcanzada aquí, el éxito es reportado. De otra forma, la búsqueda continúa ampliando caminos de todos los nodos del nivel en curso, para posteriormente bajar al próximo nivel. De este modo, labúsqueda continúa revisar nodos en un nivel especial, e informará sobre el éxito cuando un nodo meta es encontrado, y reportar una falla si todos los nodos han sido revisados y ningún nodo meta ha sido encontrado.

Mixquiahuala de Juárez a 26 de febrero de 2010

Página 3

COMPARATIVA DE CASOS DE BÚSQUEDA DE PROFUNDIDAD Y POR ANCHURA

2.3.3 BÚSQUEDA ÓPTIMA
La búsqueda heurística trata deresolver los problemas mediante una nueva técnica. Podemos expandir nodos por selección juiciosa, seleccionado el nodo más prometedor, donde estos nodos estarán identificados por el valor de su fuerza comparada con sus competidores homólogos con la ayuda de funciones intuitivas especializadas, llamadas funciones heurísticas. La búsqueda heurística generalmente trabaja para dos tipos distintos de...