Búsquedas inteligentes

• ¿Què tipo de problemas son importantes para la IA?– La IA trata aquellos problemas que se resuelven

generalmente por ensayo y error, utilizando mètodos de bùsquedas.

– No le interesan los problemas que cuentan ya con mètodos bien definidos para su soluciòn, como los problemas numèricos de soluciòn de ecuaciones.

• Bùsquedas en representación espacio de estados, sus elementos son:– Estado inicial

– Estado meta

– Operadores

– Prueba de estado meta

– Ruta de solución

– Espacio de estados

Búsquedas inteligentes

• Operadores– El operador es un procedimiento usado para modificar el estado

actual del problema. Para aplicar un operador el estado actual debe satisfacer ciertas precondiciones, cada operador tiene sus propias precondiciones.

• Espacio de estados– Hay un espacio de estados formado por el conjunto de los

estados posibles, que existen entre el estado inicial y el estado meta y son resultado de la aplicación de los operadores.

– Los estados también pueden ser soluciones alternativas para el problema. Cada estado es la colección de conocimientosdisponible en forma de estructuras simbólicas de la situación determinada del problema.

• Estado Meta– La meta o estado meta es el objetivo a alcanzar, la solución o

respuesta final del problema.

Búsquedas inteligentes

• Estado Inicial– Estado del que parte la búsqueda, es la configuración inicial del

problema.

• Prueba de estado meta– Cuestionamiento para verificar si el estado que se revisa es el

estado meta buscado.

• Ruta de solución– Al final de la búsqueda, si se encontró la solución se debe dar la

ruta que lleva del estado inicial al estado meta, incluyendo sólo los estados que están entre estos ambos y que es necesario visitar. No siempre son los mismos que se generan o recorren durante la aplicación de los algoritmos.

Búsquedas inteligentes

• Búsquedas ciegas– El orden en que la búsqueda se realiza no depende

de la naturaleza de la solución buscada. La localización de la(s) meta(s) no altera el orden de expasión de los nodos.

– Si la solución existe es seguro que se encuentra

– Puede terminar en una explosión combinatoria

– Exhaustiva o Parcial

– Hay dos procedimientos:• Búsqueda en amplitud

• Búsqueda en profundidad

– Consume mucho tiempo

– Se aplica a problemas simples

– No requiere tener un conocimiento muy preciso del problema

Búsquedas inteligentes

Recorrer árbol/grafo de búsqueda en anchura

• expandir estado raíz

• expandir todos sus sucesores

• expandir todos los sucesores de los sucesores

.....

Realiza un ordenamiento de los estados a estudiar

en base a su nivel

• todos los nodos de nivel d se estudirán antes que

cualquier nodo a nivel d + 1

Búsqueda en amplitud

Se aplican todos los

operadores posibles desde el

estado revisado,así se generan

todos sus descendientes en el

siguiente nivel.

Búsqueda en amplitud

Orden de generación y revisión de nodos

Búsqueda en amplitud

Nodo inicial

Nodo meta