![Page 1: ¿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](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4641a28abb57c9126ff/html5/thumbnails/1.jpg)
¿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”
![Page 2: ¿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](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4641a28abb57c9126ff/html5/thumbnails/2.jpg)
Initial State
Goal States
Solución de problemas
Transformations
Métodos de Búsqueda
![Page 3: ¿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](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4641a28abb57c9126ff/html5/thumbnails/3.jpg)
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
![Page 4: ¿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](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4641a28abb57c9126ff/html5/thumbnails/4.jpg)
¿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.
![Page 5: ¿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](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4641a28abb57c9126ff/html5/thumbnails/5.jpg)
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
![Page 6: ¿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](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4641a28abb57c9126ff/html5/thumbnails/6.jpg)
Espacio de estados:
![Page 7: ¿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](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4641a28abb57c9126ff/html5/thumbnails/7.jpg)
Depth-first search
![Page 8: ¿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](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4641a28abb57c9126ff/html5/thumbnails/8.jpg)
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.
![Page 9: ¿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](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4641a28abb57c9126ff/html5/thumbnails/9.jpg)
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.
![Page 10: ¿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](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4641a28abb57c9126ff/html5/thumbnails/10.jpg)
Breadth-first Search
![Page 11: ¿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](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4641a28abb57c9126ff/html5/thumbnails/11.jpg)
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.
![Page 12: ¿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](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4641a28abb57c9126ff/html5/thumbnails/12.jpg)
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.
![Page 13: ¿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](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4641a28abb57c9126ff/html5/thumbnails/13.jpg)
Iterative DeepeningProfundidad=1 Profundidad=2
Profundidad=3
Profundidad=4
![Page 14: ¿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](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4641a28abb57c9126ff/html5/thumbnails/14.jpg)
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.
![Page 15: ¿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](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4641a28abb57c9126ff/html5/thumbnails/15.jpg)
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.
![Page 16: ¿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](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4641a28abb57c9126ff/html5/thumbnails/16.jpg)
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.
![Page 17: ¿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](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4641a28abb57c9126ff/html5/thumbnails/17.jpg)
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.
![Page 18: ¿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](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4641a28abb57c9126ff/html5/thumbnails/18.jpg)
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.
![Page 19: ¿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](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4641a28abb57c9126ff/html5/thumbnails/19.jpg)
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
![Page 20: ¿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](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4641a28abb57c9126ff/html5/thumbnails/20.jpg)
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