¿Por que estudiar búsquedas?

Recordemos que la mayoría de los problemas en inteligencia artificial, involucran como tema central un proceso de búsqueda.

INTELIGENCIA ARTIFICIAL = REPRESENTACIÓN DE CONOCIMIENTO + BUSQUEDA

Definición de problemas de búsqueda: Problemas de optimización. Problema de alcanzar algún objetivo. Formalización de los problemas de búsqueda.

Ejemplos: El “traveling salesman problem” (TSP) El acertijo de los “8 tildes”

Initial State

Goal States

Solución de problemas

Transformations

Métodos de Búsqueda

Métodos de Búsqueda (ejemplo)5 3 8 4 67 2 1

3 85 4 67 2 1

5 3 84 67 2 1

5 3 87 4 6 2 1

5 3 84 67 2 1

3 85 4 67 2 1

5 84 3 67 2 1

5 3 84 2 67 1

5 3 87 4 62 1

3 4 85 67 2 1

3 85 4 67 2 1

5 3 84 6 17 2

5 3 4 6 87 2 1

5 84 3 67 2 1

5 3 84 2 6 7 1

5 3 84 2 67 1

5 3 87 62 4 1

5 3 87 4 62 1

¿Como resolver problemas de búsqueda?

Formalice el problema como una búsqueda en un espacio de estados: Identifique el estado inicial Identifique aquellas operaciones que nos

permiten transformar un estado a otro. Identifique la condición de terminación

El objetivo del proceso es llevar al sistema de su estado inicial a algún estado final aplicando alguna secuencia de operaciones.

Búsqueda en un espacio de estados

Considere la siguiente gráfica: • Objetivo: encontrar una ruta desde S hasta G • Estado Inicial: S• Estado Final: G

Espacio de estados:

Depth-first search

Búsqueda por profundidad (Depth-First)

Conocimiento: no informada Completés: NO si existen ramas de profundidad infinita. Complejidad en memoria1:

O(B·d) si los puntos de decisión serán recordados; O(d) de otro modo.

Complejidad en tiempo1: O(B·d) Optimalidad: no necesita obtener la ruta más corta. Consejo sobre la implementación:

Para evitar un ciclo infinito, no extienda (s0, s1, …, sk) a

(s0, s1, …, sk , sk+1) si sk+1 se encuentra en (s0, s1, …, sk). Modelar el comportamiento utilizando recursividad o en su caso una

pila.

1 B es el factor de “branching” y d es la profundidad máxima.

Búsqueda por profundidad

Número de soluciones: Más recomendable cuando sólo se requiera una solución, aunque puede obtener todas las soluciones.

Optimalidad de la solución:Más adecuado para problemas que no requieran optimalidad en sus soluciones.

Localización de las soluciones en el espacio de estados:

No es importante.

Densidad de la solución: Muy recomendable para problemas con muchas soluciones.

Breadth-first Search

Búsqueda por niveles (Breadth-First) Conocimiento: no informada

Completés: COMPLETA – en grafos finitos. SEMICOMPLETA – en espacios de búsqueda infinitos.

Dados suficientes recursos (tiempo y memoria), si existe una solución será encontrada.

Complejidad en memoria1: O(Bd)

Complejidad en tiempo1: O(Bd)

Optimalidad: Siempre encuentra la ruta más corta (no necesariamente la óptima) entre el estado inicial y el final.

Consejo sobre la implementación: Modelar el funcionamiento utilizando una cola.

1 B es el factor de “branching” y d es la profundidad a la cual se encuentra la solución.

Búsqueda por niveles

Número de soluciones: No es importante, pero resulta más adecuado cuando sólo una solución es requerida, por razones de complejidad.

Optimalidad de la solución:Muy adecuado para problemas que requieran optimalidad en sus soluciones, cuando la optimalidad se mide como el número de estados visitados desde el estado inicial.

Localización de las soluciones en el espacio de estados:

Cualquier lugar en el espacio de búsqueda; mas adecuado para problemas en que las soluciones se encuentren a distancia variable del estado inicial.

No cae en ciclos.

Iterative DeepeningProfundidad=1 Profundidad=2

Profundidad=3

Profundidad=4

Iterative Deepening

Conocimiento: no informada Completés:

SEMICOMPLETA – en espacios de búsqueda infinitos

Complejidad en memoria1: O(B·d)

Complejidad en tiempo1: O(B·d)

Optimalidad: Siempre encuentra la ruta más corta (no necesariamente la óptima)

entre el estado inicial y el final.

Consejo sobre la implementación: Definir utilizando recursividad o en su caso una pila. manejar un parámetro de profundidad.

1 B es el factor de “branching” y d es la profundidad máxima.

Iterative Deepening

Número de soluciones: No es importante, pero resulta más adecuado cuando sólo una solución es requerida, por razones de complejidad.

Optimalidad de la solución:Muy adecuado para problemas que requieran optimalidad en sus soluciones, cuando la optimalidad se mide como el número de estados visitados desde el estado inicial.

Localización de las soluciones en el espacio de estados:

Cualquier lugar en el espacio de búsqueda; mas adecuado para problemas en que las soluciones se encuentren a distancia variable del estado inicial.

No cae en ciclos.

Ejercicios

1. En el problema de los baldes de agua, se tiene un balde de 3 litros y uno de 4 litros. Inicialmente, ambos baldes se encuentran vacíos. Cada balde puede ser llenado con agua a partir de una llave, y podemos además deshacernos del agua no deseada vaciándola por una canaleta. El agua puede ser vaciada de un balde a otro. No existe ningún otro instrumento de medición. Deseamos encontrar una serie de operaciones que nos deje exactamente dos litros de agua en el balde de 4 litros.

a. Formalice el problema como un problema de búsqueda en un espacio de estados:

a. Represente el estado inicial como una estructura de datosb. Exprese la condición de terminación como una función de prueba sobre un

estado.c. Nombre las operaciones sobre los estados y provea una descripción precisa de

lo que cada operador cambia en la descripción del estado.

b. Dibuje una gráfica de todos los distintos nodos de estado hasta el nivel 3

después del nodo inicial.

Búsqueda Informada

Estos métodos de búsqueda de alguna manera parten de la idea del breadth-first, excepto que la búsqueda no procede uniformemente hacia fuera partiendo del nodo de inicio; en lugar de esto, procede de manera preferencial a través de los nodos que de manera heurística y basada en información relativa al problema, indica que podrían representar la mejor ruta hacia el nodo objetivo.

Se asume que contamos con una función heurística de evaluación, f, que nos ayudará a decidir que nodo es el mejor para expandir en la siguiente elección. Por convención adoptaremos que los valores menores de f indican los mejores nodos.

Expandiremos el siguiente nodo n, que tenga el menor valor de f(n).

Terminaremos cuando el nodo a expander sea el nodo objetivo.

Búsqueda Informada

Funciones de evaluaciónUna función de evaluación debe obtener una medida aproximada de la

distancia desde cualquier nodo hasta el nodo objetivo y debe ser fácil de evaluar.

Búsqueda Informada

5 3 8 4 67 2 1

3 85 4 67 2 1

5 3 84 67 2 1

5 3 87 4 6 2 1

5 3 84 67 2 1

5 84 3 67 2 1

5 3 84 2 67 1

5 3 8 4 67 2 1

5 3 84 2 6 7 1

5 3 84 2 67 1

8

8 7 9

8 8 8 8

9 8

Comparison among uninformed search techniques:

Where:

b is the branching factor, d is the depth of the solution; m is the depth of the search tree.

Problem Solving in Artificial Intelligence

BreadthFirst

DepthFirst

IterativeDeepening

Branch &Bound

O(n) bd bm bd ba

Memory bd bxm bxd bxa

Optimal yes no yes no

Complete yes Only on finite graphs

yes Yes, when ad