Bu Squedas Inteligentes

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 inteligentes
• Bùsquedas en representaciónespacio 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 conocimientos
disponible en forma de estructuras simbólicas de la situación
determinada delproblema.

• 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ónbuscada. 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úsqueda en amplitud
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 profundidad
• Expandir un camino hasta llegar al final
• Si no essolución y no tiene expansión posible,
volver a un nodo no expandido del nivel anterior
• Menor exigencia de memoria
basta con almacenar los nodos de la ruta que se
está expandiendo
• Backtracking reqiere generar solo un sucesor a
la vez.
• Su gran ventaja es su ahorro en memoria

Búsqueda en profundidad
• Con profundidad limitada
Para evitar caer en caminos de profunidad muy grande,
se lesimpone un límite de profundidad máxima.

• Con profundidad iterativa
Va aumentando gradualmente la profundidad hasta
encontrar una meta.
Algunos nodos se expanden varias veces.
Aunque parece que se repite mucho trabajo de mas, en
la practica es relativamente poco.

Búsquedas Heurísticas
• Búsqueda ciega: ineficaz en la práctica (explosión
combinatoria)
• Búsqueda heurística su objetivo: guiar elproceso de
búsqueda
• ”Podar”el espacio de estados
• Usar información sobre la cercanía de un estado dado a uno
de los estados objetivo
• Explorar primero caminos más prometedores
• No garantiza que se vaya a encontrar la solución
• En ocasiones, encuentra solución buena en tiempo aceptable
•

Búsquedas Heurísticas
• Utiliza funciones de evaluación
• Asocían a cada estado, e, un número, h(e), que...