mg. samuel oporto díaz lima, 12 de octubre de 2005 búsqueda no informada inteligencia artificial
TRANSCRIPT
![Page 1: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/1.jpg)
Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005
Búsqueda no Informada
INTELIGENCIA ARTIFICIAL
![Page 2: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/2.jpg)
22 /54/54
Mapa Conceptual del CursoInteligencia Artificial y Sistemas Expertos
Lenguaje Simbólico
LISP
Búsqueda
Búsqueda Ciega
Búsqueda Heurística
Planeación
Lógica y Razonamiento
Lógica Proposicional
Lógica de Predicados
Inferencia y Razonamiento
Inteligencia Artificial
Conceptos Generales
Conocimiento
Agentes
Búsqueda Ciega
![Page 3: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/3.jpg)
33 /54/54
Tabla de Contenido
1. Estrategias de Búsqueda
2. Búsqueda no Informada.i. Búsqueda por Amplitud
ii. Búsqueda por Costo Uniforme
iii. Búsqueda en Profundidad
iv. Búsqueda Limitada por Profundidad
v. Búsqueda por Profundidad Iterativa
vi. Búsqueda Bidireccional
3. Bibliografía
![Page 4: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/4.jpg)
44 /54/54
Objetivos
• Presentar los conceptos acerca de las estrategías de búsqueda no informada.
![Page 5: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/5.jpg)
55 /54/54
ESTRATEGIAS DE BÚSQUEDA
![Page 6: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/6.jpg)
66 /54/54
Estrategias de Búsqueda
Búsqueda No Informada
(Ciega)
1. Búsqueda preferente por amplitud
2. Búsqueda de costo uniforme
3. Búsqueda preferente por profundidad
4. Búsqueda limitada por profundidad
5. Búsqueda por profundización iterativa
6. Búsqueda bidireccional
Búsqueda Informada
(Heurística)
1. Búsqueda avara2. Búsqueda A*3. Búsqueda A*PI4. Búsqueda A*SRM
![Page 7: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/7.jpg)
77 /54/54
Búsqueda en el Espacio de Estados• La resolución de un problema con esta
representación pasa por explorar el espacio de estados
• Partimos del estado inicial evaluando cada paso hasta encontrar un estado final
• En el caso peor exploraremos todos los posibles caminos entre el estado inicial del problema hasta llegar al estado final
• Definiremos una representación del espacio de estados para poder implementar algoritmos que busquen soluciones
![Page 8: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/8.jpg)
88 /54/54
Estructura del espacio de estados
• Estructuras de datos: Árboles y Grafos• Estados = Nodos• Operadores = Arcos entre nodos (dirigidos)• Árboles: Solo un camino lleva a un nodo• Grafos: Varios caminos pueden llevar a un nodo
![Page 9: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/9.jpg)
99 /54/54
Algoritmo Básico• Basado en búsqueda y recorrido en árboles y grafos• La estructura la construimos a medida que hacemos la
búsqueda • Algoritmo para una solución:
– Seleccionar el primer estado como el estado actual– mientras el estado actual no es el estado final hacer
Generar y guardar sucesores del estado actual (expansión)Escoger el siguiente estado entre los pendientes (selección)
– fin-mientras
• La selección del siguiente nodo determinará el tipo de búsqueda (orden de selección o expansión)
• Es necesario definir un orden entre los sucesores de un nodo (orden de generación)
![Page 10: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/10.jpg)
1010 /54/54
Algoritmo Básico• Nodos abiertos: Estados generados pero aún no
visitados• Nodos cerrados: Estados visitados y que ya se han
expandido• Tendremos una estructura para almacenar los nodos
abiertos• Las diferentes políticas de inserción en la estructura
determinarán el tipo de búsqueda• Si exploramos un grafo puede ser necesario tener en
cuenta los estados repetidos (esto significa tener una estructura para los nodos cerrados). Merece la pena si el número de nodos diferentes es pequeño respecto al número de caminos
![Page 11: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/11.jpg)
1111 /54/54
Evaluación de las EstrategiasLas estrategias se evalúan de acuerdo a su:• Completez. ¿La estrategia garantiza encontrar una
solución, si ésta existe?• Complejidad temporal. ¿Cuánto tiempo se necesitará
para encontrar una solución?• Complejidad espacial. ¿Cuánta memoria se necesita
para efectuar la búsqueda?• Optimalidad. ¿Con esta estrategia se encontrará una
solución de la más alta calidad, si hay varias soluciones?
Las complejidades temporal y espacial se miden en términos de:b máximo factor de ramificación del árbol de búsqueda (branching factor)
d profundidad de la solución de menor costem profundidad máxima del espacio de estados (puede ser ∞)
![Page 12: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/12.jpg)
1212 /54/54
BUSQUEDA NO INFORMADA
![Page 13: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/13.jpg)
1313 /54/54
Estrategias de búsqueda no informada
• No existe información sobre la cantidad de estados intermedios o el costo de ruta para pasar del estado actual a la meta.
• Sólo se sabe distinguir si estamos en el estado meta o no
• A esta búsqueda se le conoce también como búsqueda ciega
![Page 14: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/14.jpg)
1414 /54/54
Estrategias de búsqueda no informada
1. Búsqueda preferente por amplitud
2. Búsqueda de costo uniforme
3. Búsqueda preferente por profundidad
4. Búsqueda limitada por profundidad
5. Búsqueda por profundización iterativa
6. Búsqueda bidireccional
![Page 15: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/15.jpg)
1515 /54/54
BUSQUEDA POR AMPLITUD(DFS)
S
FM
OL
QP
F FN
F
![Page 16: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/16.jpg)
1616 /54/54
1. Búsqueda preferente por amplitud
• En este caso, primero se expande el nodo raíz y luego todos los nodos generados por éste, luego sus sucesores y así sucesivamente.
• Todos los nodos que están a profundidad d se expanden antes que los nodos con profundidad d+1.
![Page 17: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/17.jpg)
1717 /54/54
Búsqueda preferente por amplitud
1. Abiertos←(n0); Cerrados←( )
2. Si Abiertos = ( ), fin devolviendo fallo
3. n←primer elemento de Abiertos; eliminar n de Abiertos y llevarlo a Cerrados; Suc←( )
4. Si n es meta, fin con éxito, devolviendo el camino
5. expandir n, colocando sus hijos en Suc, como hijos de n
6. eliminar de Suc cualquier nodo cuyo estado ya esté asociado a algún nodo de Abiertos o Cerrados
7. colocar los nodos de Suc al final de Abiertos
8. Ir a 2
![Page 18: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/18.jpg)
1818 /54/54
0
0
![Page 19: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/19.jpg)
1919 /54/54
0
3 2 11 2 3
0
![Page 20: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/20.jpg)
2020 /54/54
0
c b a 3 21 2 3
a b c
01
![Page 21: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/21.jpg)
2121 /54/54
0
1 2 3
a b c d e f
f e d c b a 3
012
![Page 22: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/22.jpg)
2222 /54/54
0
i h g f e d c b a1 2 3
a b c d e f g h i
0123
![Page 23: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/23.jpg)
2323 /54/54
γ β α i h g f e d c b
0
1 2 3
a b c d e f g h i
α β γ
0123a
![Page 24: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/24.jpg)
2424 /54/54
012b a 3
γ β α i h g f e d cζ ε δ
0
1 2 3
a b c d e f g h i
α β γ δ ε ζ
![Page 25: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/25.jpg)
2525 /54/54
Búsqueda preferente por amplitud
• Si hay solución, es seguro que se encontrará mediante la búsqueda preferente por amplitud.
• Si son varias soluciones, siempre encontrará primero el estado de meta más próximo (menos profundidad, más a la izquierda).
• La búsqueda preferente por amplitud es completa y óptima siempre y cuando el costo de ruta sea una función que no disminuya al aumentar la profundidad del nodo.
Completez, Complejidad Temporal, Complejidad Espacial, Optimalidad.
![Page 26: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/26.jpg)
2626 /54/54
Complejidad Temporal
• Si b es el factor de ramificación de los estados, y la solución está a una profundidad d, entonces la cantidad máxima de nodos expandidos antes de encontrar la solución es:
1+ b + b2 + b3 + ... + bd + (bd+1 – b)
• La complejidad de este algoritmo es O(bd+1).
![Page 27: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/27.jpg)
2727 /54/54
Complejidad Espacial y Temporal
Si b=10, se analizan 10,000 nodos por segundo y cada nodo requiere 1000 bytes de almacenamiento:
Profundidad Nodos Tiempo Memoria
2 1100 .11 segundos 1 Megabyte
4 111,100 11 segundos 106 Megabytes
6 107 19 minutos 10 Gigabytes
8 109 31 horas 1 Terabyte
10 1011 129 días 101 Terabyte
12 1013 35 años 10 Petabytes
14 1015 3523 años 1 Exabyte
![Page 28: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/28.jpg)
2828 /54/54
Resumen (BFS)• Los nodos se visitan y generan por niveles• La estructura para los nodos abiertos es una cola (FIFO)• Un nodo es visitado cuando todos los nodos de los
niveles superiores y sus hermanos precedentes han sido visitados
• Características:– Completidud: El algoritmo siempre encuentra una solución– Complejidad temporal: Exponencial respecto al factor de
ramificación y la profundidad de la solución O(bd+1). – Complejidad espacial: Exponencial respecto al factor de
ramificación y la profundidad de la solución O(bd+1).– Optimalidad: La solución que se encuentra es óptima en número de
niveles desde la raíz
![Page 29: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/29.jpg)
2929 /54/54
Ejercicio 1
Determine el orden en que un agente basado en metas busca el objetivo (orden en que se visitan y orden en que se aperturan):
– VISITA (nodos cerrados)
– APERTURA (nodos abiertos)
A
ED
CB
GF
I JH
K
A
ED
CB
GF
I JH
K
![Page 30: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/30.jpg)
3030 /54/54
Ejercicio 2
Diga para el siguiente árbol el orden en que se aperturan (nodos abiertos) y orden en que se visitan los nodos (nodos cerrados).
A
B C D
G IH J K L
O
E F
M N
A
B C D
G IH J K L
O
E F
M N
Tenga en consideración lo siguiente:1. Existe dos colas de nodos, nodos abiertos y nodos cerrados.2. La cola de nodos abiertos siempre se inicializa con el primer nodo del árbol, la cola
de nodos cerrados se inicializa vacío.3. Para visitar un nodo este primero debe ser abierto.4. La visita a un nodo, permite generar la lista de nodos abiertos (nodos hijos)5. El primer nodo que se visita en un árbol siempre es el primer nodo del árbol.6. La vista de un nodo permite que este pase a la lista de nodos cerrados.7. La técnica de búsqueda no informada se diferencia por el orden en que se vistan
los nodos, no por el orden en que se abren los nodos.
![Page 31: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/31.jpg)
3131 /54/54
BUSQUEDA POR COSTO UNIFORME
Uniform-Cost Search (UCS)
![Page 32: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/32.jpg)
3232 /54/54
Búsqueda de costo uniforme• Con la búsqueda anterior no siempre se
encuentra la solución de costo de ruta mínimo.• La búsqueda de costo uniforme expande
siempre el nodo de menor costo en el margen, medido por el costo de ruta g(n) en vez del nodo de menor profundidad.
• Si se cumplen ciertas condiciones, es seguro que la primera solución encontrada será la más barata.
• La búsqueda en amplitud es una búsqueda de costo uniforme donde g(n) = profundidad(n)
![Page 33: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/33.jpg)
3333 /54/54
Búsqueda de costo uniforme
S es el único nodo en la frontera(nodos pendientes por expandir).Debido a que no es la meta, seprocede a su expansión...
NOTA: NO SE GENERARÁN NUEVAMENTE LOS ESTADOS ANALIZADOS PREVIAMENTE
S
C
G
A
B
1 10
5 5
15 5
S
C
G
A
B
1 10
5 5
15 5
S 0Frontera
S 0Frontera
Problema: Ir de S a G al menor costo posible
![Page 34: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/34.jpg)
3434 /54/54
Búsqueda de costo uniforme
S 0
A CB
1 5 15
S
C
G
A
B
1 10
5 5
15 5
Frontera
Hay 3 nodos en la frontera (A, B y C), y se elige el de menor costo de ruta (A). Como no es una meta, se procede a su expansión...
![Page 35: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/35.jpg)
3535 /54/54
Búsqueda de costo uniforme
S 0
A CB
11
5 15
S
C
G
A
B
1 10
5 5
15 5
Frontera
Hay 3 nodos en la frontera (G, B y C), de los cuales B es el que tiene el menor costo de ruta, por lo que se procede a expandirlo. Note que aunque ya hay una solución en la frontera (G), el algoritmo la ignora porque la rama S-B tiene posibilidades de encontrar una solución mejor que S-A-G.
G
![Page 36: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/36.jpg)
3636 /54/54
Búsqueda de costo uniformeS 0
A CB
11
15
S
C
G
A
B
1 10
5 5
15 5
Frontera
Hay 3 nodos en la frontera (G, G y C), de los cuales el segundo G es el que tiene el menor costo de ruta, por lo que se procede a expandirlo. En ese momento se detecta que es una solución (sólo genera nodos ya analizados) y la búsqueda termina. Note que hay dos nodos (las dos G’s en la frontera) que representan a un mismo estado, y que el algoritmo ni siquiera intenta expandir C, que no tiene posibilidades de llevar a una mejor solución (S-C ya tiene un costo de 15).
G 10G
![Page 37: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/37.jpg)
3737 /54/54
Búsqueda de costo uniforme• Este método puede encontrar la solución más barata
siempre y cuando se satisfaga un requisito sencillo.
• El costo de ruta nunca debe ir disminuyendo conforme avanzamos por la ruta, es decir, g(Sucesor(n)) g(n) para todos los nodos n.
• Para que el costo de la ruta no disminuya el costo de aplicar un operador no debe ser negativo.
• ¿Qué pasa si el costo de un operador de negativo?
![Page 38: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/38.jpg)
3838 /54/54
Resumen (UCS)• Se visitan y expanden los nodos del borde con menor
costo.• La estructura para los nodos abiertos es una cola (FIFO)• Un nodo es visitado si su costo de ruta es el menor de
todos.• Características:
– Completitud: Se encuentra la ruta siempre y cuando el costo no disminuya conforme se avanza g(sucesor(n)) ≥ g(n)
– Complejidad temporal: Exponencial respecto al factor de ramificación y la profundidad de la solución O(bd+1).
– Complejidad espacial: Exponencial respecto al factor de ramificación y la profundidad de la solución O(bd+1).
– Optimalidad: La solución es óptima si el costo de un operador > 0, en caso contrario hay que buscar exhaustivamente
![Page 39: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/39.jpg)
3939 /54/54
Ejercicio 3• Use la estrategia de costo uniforme
para encontrar la ruta de menor costo para ir de:
A D.• Recuerde que para la estrategia de
costo uniforme se usa la función:• f = g + h : donde h = 0.• Donde g es el costo de la ruta
avanzada
Recomendaciones:• Sustente su respuesta presentando el
árbol de búsqueda generado• No apertura nodos ya visitados en la
misma ruta.
A
B
C
D
E
F
G2
3 4
1
61
1
5
24
4
1
A
B
C
D
E
F
G2
3 4
1
61
1
5
24
4
1
![Page 40: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/40.jpg)
4040 /54/54
Ejercicio 3A
g=0
Bg=2
Gg=4
Fg=1
Gg=5
Eg=7
Cg=5
Gg=3
Eg=5
Fg=7
Cg=4
Dg=8
Dg=8
Dg=9
Eg=6
Bg=5
Cg=5
Fg=8
Gg=6
Dg=9
Dg=6
Cg=8
Dg=9
Dg=10
Eg=7
Bg=6
Cg=6
Ag=0
Bg=2
Gg=4
Fg=1
Gg=5
Eg=7
Cg=5
Gg=3
Eg=5
Fg=7
Cg=4
Dg=8
Dg=8
Dg=9
Eg=6
Bg=5
Cg=5
Fg=8
Gg=6
Dg=9
Dg=6
Cg=8
Dg=9
Dg=10
Eg=7
Bg=6
Cg=6
![Page 41: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/41.jpg)
4141 /54/54
Búsqueda preferente por profundidad (DFS)
S
FM
OL
QP
F FN
F
![Page 42: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/42.jpg)
4242 /54/54
Búsqueda preferente por profundidad• En esta búsqueda siempre se expande uno de
los nodos que se encuentre en lo más profundo del árbol.
• Sólo si la búsqueda conduce a un callejón sin salida (un nodo que no es meta y que no tiene expansión), se revierte la búsqueda y se expanden los nodos de niveles menos profundos.
• Lo anterior se logra mediante el algoritmo de Búsqueda-General, con una función de lista de espera que ponga los estados recién generados al principio de la lista.
![Page 43: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/43.jpg)
Búsqueda preferente por profundidad
NOTA:Se supone que el factor de ramificación es b = 2 y que los nodos de nivel m = 3 no tienen sucesores.
![Page 44: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/44.jpg)
4444 /54/54
Búsqueda preferente por profundidad• Sólo es necesario guardar la ruta que va del
nodo raíz al nodo hoja, junto con los nodos restantes no expandidos, por cada nodo de la ruta.
• Si un espacio de estados tiene factor de ramificación b y profundidad máxima m, se requieren almacenar bm nodos.
• La complejidad temporal es de O(bm).
![Page 45: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/45.jpg)
4545 /54/54
Búsqueda preferente por profundidad• Si la cantidad de soluciones en un problema es
grande, se recomienda esta búsqueda (BFS) sobre la búsqueda preferente por amplitud (DFS).
• La desventaja de esta búsqueda es que se puede quedar estancada al avanzar por una ruta equivocada, ya que muchos árboles de búsqueda pueden ser muy profundos o infinitos. Por lo tanto, la BPPP no es ni la mas completa ni la más óptima.
![Page 46: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/46.jpg)
4646 /54/54
Resumen (DFS)• Los nodos se visitan y generan buscando los nodos a
mayor profundidad y retrocediendo cuando no se encuentran nodos sucesores
• La estructura para los nodos abiertos es una pila (LIFO)• Para garantizar que el algoritmo acaba debe imponerse un
límite en la profundidad de exploración• Características
– Completidud: El algoritmo encuentra una solución si se impone un límite de profundidad y existe una solución dentro de ese límite
– Complejidad temporal: Exponencial respecto al factor de ramificación y la profundidad del límite de exploración O(bm).
– Complejidad espacial: Si no se controlan los nodos repetidos el coste es lineal respecto al factor de ramificación y el límite de profundidad O(bm). Si tratamos repetidos el coste es igual que en anchura. Si la implementación es recursiva el coste es O(m).
– Optimalidad: No se garantiza que la solución sea óptima
![Page 47: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/47.jpg)
4747 /54/54
Ejercicio 4• Considere el siguiente gráfico.
Los nodos sombreados ya fueron visitados y se han extendido.
• Dibuje el árbol de la búsqueda que corresponde a este gráfico, dónde la búsqueda se inició en A y se expandió hasta R, y puede visitar un nodo en el gráfico más de una vez.
1. Indicar el borde en el árbol de búsqueda. 2. ¿En BFS, qué nodo se extendería? 3. ¿En UCS, qué nodo se extendería? 4. ¿En DFS, qué nodo se extendería?
![Page 48: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/48.jpg)
4848 /54/54
Ejercicio 5Imagine un escenario con un robot que intenta navegar en el siguiente laberinto desde (S) hasta la meta (G). A cada paso, el robot puede seguir una de las cuatro direcciones del compas. El robot contempla las alternativas en el orden siguiente: Moverse al SurMoverse al EsteMoverse al NorteMoverse al Oeste
1. Formula el problema como un problema de búsqueda.2. Marcar el conjunto de estados que se expanden durante la búsqueda, en el
orden ellos se expanden, colocando un “1” en el primer estado, un “2” por el segundo, y así sucesivamente (Pon “1” en la celda marcada como S). Asume que la búsqueda es Primero en Profundidad (DFS). Use la versión de DFS que evita los ciclos y el re-expansión de un estado que está en el camino actual.
3. Usando la misma notación marca el conjunto de estados que el BFS puede expandir, en el orden en el cual son expandidos.
![Page 49: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/49.jpg)
4949 /54/54
Búsqueda limitada por profundidad
(DLS)
![Page 50: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/50.jpg)
5050 /54/54
Búsqueda limitada por profundidad• Con esta búsqueda se eliminan las dificultades de la
búsqueda preferente por profundidad, al imponer un límite a la profundidad máxima de una ruta.
• El establecer este límite es difícil, ya que no conocemos mucho sobre el espacio de estados.
• La búsqueda limitada puede no ser completa ni óptima: un límite de profundidad muy pequeño puede que no contenga la solución, y uno muy grande puede que contenga soluciones no óptimas que son encontradas primero.
• La complejidad espacio-temporal de la búsqueda limitada por profundidad es similar a la de la búsqueda preferente por profundidad: requiere un tiempo de O(bl) y un espacio O(bl), donde l es el límite de profundidad.
![Page 51: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/51.jpg)
5151 /54/54
Búsqueda por profundización iterativa
(IDS)
![Page 52: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/52.jpg)
5252 /54/54
Búsqueda por profundización iterativa• Elimina la dificultad de elegir un límite adecuado
de profundidad en la búsqueda limitada por profundidad.
• Lo anterior lo hace probando todos los límites de profundidad posibles, primero la profundidad 0, luego la 1, luego la 2, etc.
• En la profundización iterativa se combinan las ventajas de las búsquedas preferente por profundidad y preferente por amplitud.
• Es óptima y completa, como la búsqueda preferente por amplitud, pero la memoria que necesita es la de la búsqueda preferente por profundidad.
![Page 53: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/53.jpg)
5353 /54/54
Búsqueda por profundización iterativaFunción Búsqueda-por-profundización-iterativa(problema) responde
con una secuencia de solución.
entradas: problema, un problema.
para profundidad 0 a hacer
si Búsqueda-limitada-por-profundidad(problema,
profundidad) tiene éxito, entregue el
resultado obtenido
fin-para
responda con falla
![Page 54: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/54.jpg)
5454 /54/54
Búsqueda por profundización iterativa
Límite = 0
Límite = 1
Límite = 2
Límite = 3
...
![Page 55: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/55.jpg)
5555 /54/54
Búsqueda por profundización iterativa• La búsqueda por profundización iterativa puede
parecer un desperdicio, por repetir expansiones de estados, pero en la mayoría de los problemas esta expansión múltiple es realmente pequeña.
• La complejidad temporal sigue siendo O(bd) y la complejidad espacial es O(bd).
• La profundización iterativa es el método idóneo para aquellos casos donde el espacio de búsqueda es grande y se ignora la profundidad de la solución.
![Page 56: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/56.jpg)
5656 /54/54
Búsqueda Bidireccional(BS)
![Page 57: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/57.jpg)
5757 /54/54
Búsqueda bidireccional• Es básicamente una búsqueda simultánea que
avanza a partir del estado inicial y que retrocede a partir de la meta y que se detiene cuando ambas búsquedas se encuentran en algún punto intermedio.
• Si en un problema el factor de ramificación b es el mismo en ambas direcciones, la búsqueda bidireccional puede ser muy útil. Si la solución está a profundidad d, entonces la solución estará a O(2bd/2) = O(bd/2) pasos
![Page 58: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/58.jpg)
5858 /54/54
Cuestiones a resolver• La búsqueda hacia atrás implica la sucesiva generación de
predecesores a partir del nodo meta.• Si todos los operadores son reversibles, los conjuntos de
predecesor y sucesor son idénticos, pero en algunos problemas, el cálculo de los predecesores puede resultar muy difícil.
• Si hay varios estados meta listados en forma explícita, se puede aplicar una función de predecesor al conjunto de estados como en el caso de la búsqueda de estado múltiple. Pero si sólo hay una descripción de los estados meta, es realmente difícil (¿qué estados son predecesores del jaque mate en ajedrez?)
• Se requiere una manera eficiente de verificar cada uno de los nodos nuevos para ver si ya están en el otro árbol.
• Se tiene que definir un tipo de búsqueda para cada mitad. Amplitud – amplitud, amplitud – profundidad, etc. La complejidad espacial es igual a la temporal para esta búsqueda.
![Page 59: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/59.jpg)
5959 /54/54
Bibliografía• AIMA. Capítulo 3, primera edición.• AIMA. Chapter 3, second edition.
![Page 60: Mg. Samuel Oporto Díaz Lima, 12 de octubre de 2005 Búsqueda no Informada INTELIGENCIA ARTIFICIAL](https://reader033.vdocumento.com/reader033/viewer/2022061302/54e39fe64a795950188b5522/html5/thumbnails/60.jpg)
6060 /54/54
PREGUNTAS