Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Resolución de problemas y
Búsqueda No Informada
Guía de Estudio
[email protected] de Informática
Universidad Nacional de San LuisArgentina
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Aspectos a abordar
Agentes de resolución de problemas
Formulación de problemas
Ejemplos de Problemas
Bibliografía: Capítulo 3, Secciones 3.1 y 3.2 (libro de Russell, 3eraedición).
Búsqueda en Árbol y en Grafo
Estrategias de búsqueda no informadas
Bibliografía: Capítulo 3, Secciones 3.3 y 3.4 (libro de Russell, 3eraedición).
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Agentes: breve repaso
Interacción entre el agente y su ambiente...
percepciones
acciones
sensores
efectores
agente
?ambiente
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Tipos generales de agentes
Agentes reflejos simples
Agentes reflejos basados en modelo
Agentes basados en objetivos
Agentes de resolución de problemas
Agentes de Planning
Agentes basados en utilidades
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Agentes de resolución de problemas
Son agentes basados en objetivos⇒ pueden considerar accionesfuturas y la deseabilidad de sus resultados
Para decidir qué hacer encuentran secuencias de acciones queconducen a estados deseables (objetivos)
Un objetivo es un conjunto de estados del mundo que satisfacenalguna condición de deseabilidad
Elementos que constituyen un problema y su solución...
Algoritmos de búsqueda de propósito general para resolver estosproblemas
Algoritmos de búsqueda no informados (ciegos) e informados(próximas teorías)
Agentes inteligentes –> max medida de performance –> establecer unobjetivo...
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Ejemplo: un agente en Rumania
Giurgiu
UrziceniHirsova
Eforie
Neamt
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Sibiu Fagaras
Pitesti
Vaslui
Iasi
Rimnicu Vilcea
Bucharest
71
75
118
111
70
75
120
151
140
99
80
97
101
211
138
146 85
90
98
142
92
87
86
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Ejemplo: un agente en Rumania
De vacaciones en Rumania; actualmente en AradEl vuelo partirá mañana desde Bucharest
Formular objetivo:estar en Bucharest
Formular problema:estados: las distintas ciudadesacciones: conducir entre ciudades
Encontrar solución:secuencia de ciudades, ej., Arad, Sibiu, Fagaras, Bucharest
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Agentes de resolución de problemas
Búsqueda: Proceso de buscar una secuencia de acciones que conducea estados de valor conocido y elegir la mejor. El agente sólo tiene unconjunto de acciones inmediatas.
Algoritmo de búsqueda:
AB : Problema→ Solucion
La solución es una secuencia de acciones que conducen desde elestado actual a un estado objetivo. Esta solución también esdenominada un plan.
La fase de ejecución es aquella en que las acciones recomendadas enla solución son llevadas a cabo.
Esto conduce a un diseño de agente basado en los pasos de formular,buscar, ejecutar.
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Agentes de resolución de problemas
función Agente-Resolución-Problema-Simple (percep) retorna una acciónestático (o persistente):
sec, una secuencia de acciones, inicialmente ∅estado, alguna descripción del estado actual del mundoobjetivo, un objetivo, inicialmente “NULL”problema, una formulación del problema
estado ← Actualizar-Estado(estado, percep)si sec = ∅ entonces
objetivo ← Formular-Objetivo(estado)problema ← Formular-Problema(estado, objetivo)sec ← Búsqueda(problema)
acc ← Primera(sec)sec ← Resto(sec)retorna acc
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Problemas bien definidos
Un problema (de estado único) podría ser definido formalmente por cincocomponentes:
El estado inicial.
Las acciones posibles en cada estado.
Una descripción de lo que hacen las acciones (modelo de transición),mediante operadores, función sucesor, o función Result(s,a)
El test de objetivo.
La función de costo del paso.
Para facilitar la implementación, consideraremos las acciones posibles y sudescripción como una única componente, y por consiguiente a un problemacomo definido por cuatro componentes.Una solución a un problema es un paso desde el estado inicial a un estadoobjetivo.La calidad de una solución es medida por la función de costo de paso. Unasolución óptima es la que tiene costo de paso más bajo entre todas lassoluciones.
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Definiendo el problema de Rumania en Prolog
Representación de estado: ...Representación de acciones: ...
Giurgiu
UrziceniHirsova
Eforie
Neamt
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Sibiu Fagaras
Pitesti
Vaslui
Iasi
Rimnicu Vilcea
Bucharest
71
75
118
111
70
75
120
151
140
99
80
97
101
211
138
146 85
90
98
142
92
87
86
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Definiendo el problema de Rumania en Prolog
Representación de estado: una constante simbólica con el nombre de laciudad en que se encuentra el agente. Representación de acciones:functores ir(X,Y) donde X e Y son las ciudades de origen y destinorespectivamente. Asumiremos que el estado inicial es el agente en Arad.
inicial(arad).
sucesor(ir(arad,zerind),arad,zerind).
sucesor(ir(arad,sibiu),arad,sibiu).
......
costo(ir(arad,zerind),75).
costo(ir(arad,sibiu),140).
......
costo(ir(X,Y),R) :- costo(ir(Y,X),R).
objetivo(bucharest).
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Ej.: grafo de espacio de estados del mundo de la aspiradora
R
L
S S
S S
R
L
R
L
R
L
S
SS
S
L
L
LL R
R
R
R
estados: casillas con la condición de basura y el robot (ignorar cantidad debasura etc.)acciones: Izquierda(L), Derecha(R), Aspirar(S)test de objetivo: nada de basuracosto del paso: 1 por acción
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Definiendo el problema de la aspiradora en Prolog
Representación de estado: functor est([I,D],A). I y D representan elestado de las casillas Izquierda y Derecha (sucia o limpia). A representala posición de la aspiradora (iz (izquierda) o de (derecha)). Representaciónde acciones: constante simbólica derecha, izquierda o aspirar. Elestado inicial puede ser cualquiera. Asumiremos las dos casillas sucias y laaspiradora a la izquierda.
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Definiendo el problema de la aspiradora en Prolog
Representación de estado: functor est([I,D],A). I y D representan elestado de las casillas Izquierda y Derecha (sucia o limpia). A representala posición de la aspiradora (iz (izquierda) o de (derecha)). Representaciónde acciones: constante simbólica derecha, izquierda o aspirar. Elestado inicial puede ser cualquiera. Asumiremos las dos casillas sucias y laaspiradora a la izquierda.
inicial(est([sucia,sucia],iz)).
sucesor(derecha, est([I,D],_), est([I,D],de)).
sucesor(izquierda, est([I,D],_), est([I,D],iz)).
sucesor(aspirar, est([_,D],iz) , est([limpia,D],iz)).
sucesor(aspirar, est([I,_],de) , est([I,limpia],de)).
costo(derecha,1). costo(izquierda,1). costo(aspirar,1).
objetivo(est([limpia,limpia],_)).
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Ejemplo: el 8-puzzle
7
4 5
6
5
2
81
7 3
1 2 3
4
56
8
Estado ObjetivoEstado Inicial
estados: ...acciones: ...test de objetivo: el que se muestra arriba a la derechacosto del paso: 1 por movimiento
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Ejemplo: el 8-puzzle
7
4 5
6
5
2
81
7 3
1 2 3
4
56
8
Estado ObjetivoEstado Inicial
estados: ubicaciones de las fichas en el tableroacciones: mover el blanco arriba, abajo, a la izquierda o a la derechatest de objetivo: el que se muestra arriba a la derechacosto del paso: 1 por movimiento
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Ejemplo: las 8 reinas
estados: cualquier disposición de 0 a 8 reinas sobre el tableroacciones: agregar una reina en alguna casilla del tablerotest de objetivo: las 8 reinas sobre el tablero, sin que ninguna se ataqueentre sícosto del paso: cero
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Agente resolvedor de problemas
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Agente resolvedor de problemas
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Agente resolvedor de problemas
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Agente resolvedor de problemas
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Búsqueda de soluciones
Idea básica: generar sucesores de estados ya explorados(expandiendo estados)
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Estados repetidos
Si no se considera la detección de estados repetidos unproblema lineal se puede convertir en uno exponencial!
A
B
C
D
A
BB
CCCC
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Búsqueda en Grafo
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Ejemplo: Rumania
Giurgiu
UrziceniHirsova
Eforie
Neamt
Oradea
Zerind
Arad
Timisoara
Lugoj
Mehadia
Dobreta
Craiova
Sibiu Fagaras
Pitesti
Vaslui
Iasi
Rimnicu Vilcea
Bucharest
71
75
118
111
70
75
120
151
140
99
80
97
101
211
138
146 85
90
98
142
92
87
86
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Ejemplo de búsqueda en árbol
Rimnicu Vilcea Lugoj
ZerindSibiu
Arad Fagaras Oradea
Timisoara
AradArad Oradea
Arad
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Ejemplo de búsqueda en árbol
Rimnicu Vilcea LugojArad Fagaras Oradea AradArad Oradea
Zerind
Arad
Sibiu Timisoara
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Ejemplo de búsqueda en árbol
Lugoj AradArad OradeaRimnicu Vilcea
Zerind
Arad
Sibiu
Arad Fagaras Oradea
Timisoara
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Búsqueda de soluciones
Idea: Mantener y extender un conjunto de soluciones parciales
Expansión de un estado: Generar el conjunto de estadosque se obtienen de la aplicación de las acciones válidasen dicho estado
Proceso de búsqueda:
Elegir un estado a explorarControlar si el estado es un estado objetivoExpandir el estado
Estrategia de búsqueda: Criterio que determina cual es elpróximo estado a expandir
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Búsqueda de soluciones
Árbol de Búsqueda: Estructura de datos resultante de laaplicación del proceso de búsqueda.
Raíz: Nodo correspondiente al estado inicial
Hojas del árbol: Nodos que corresponden a estados queno tienen sucesores en el árbol (todavía no han sidoexpandidos, o lo fueron y no tienen sucesores)
Espacio de estados 6= árbol de búsqueda
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Estructuras de datos para árboles de búsqueda
Nodo: Estructura de datos con cuatro componentesEstado que le corresponde al nodoNodo padre que generó el nodoAcción aplicada por el nodo padre para generar el nodoCosto del paso desde el estado inicial hasta el nodo (g)
Importante: Nodo 6= estado
Frontera: Colección de nodos que están esperando paraser expandidos. Se suele implementar como una cola (consus variantes FIFO, LIFO o cola de prioridades). Elordenamiento de la frontera dependerá de la estrategia debúsqueda que se utilice.
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Implementación: estados vs nodos
Un estado corresponde a una configuración del mundoUn nodo es una estructura que es parte de un árbol debúsqueda incluye padre, hijos, acciones, costo del paso g(x)Los estados no tienen padres, hijos, acciones, o costo delpaso!
La función EXPANDIR crea nuevos nodos, completando losdistintos campos y usando SUCESOR-FN del problema paracrear los estados correspondientes.
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Implementación: búsqueda en árbol general
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Estrategias de búsqueda
Una estrategia se define especificando el orden de expansiónde los nodos (o dicho de otra manera, ordenando la frontera de
forma tal de siempre expandir el primer nodo de la cola)
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Estrategias de búsqueda
Las estrategias son evaluadas de acuerdo a las siguientesdimensiones:
completitud—siempre encuentra una solución si alguna existe?complejidad de tiempo—cuanto tarda en encontrar una solución?complejidad de espacio—cuanta memoria se necesita?optimalidad—siempre encuentra la mejor solución (la de menor costo)?
La complejidad es medida en términos de:
b—factor de ramificación máximo del árbol de búsquedad—profundidad del nodo objetivo menos profundom—profundidad máxima del espacio de estado (longitud max de cual
paso en el espacio de estados)
El tiempo es medido en términos del número de nodos generados enla búsqueda y el espacio en términos del máximo número de nodosalmacenados en la memoria.
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Estrategias de búsqueda no informadas
Las estrategias no informadas sólo usan la informacióndisponible en la definición del problema
Búsqueda primero en anchura (BPA) (o Breadth-first search)
Búsqueda de costo uniforme (BCU) (o Uniform-cost search)
Búsqueda primero en profundidad (BPP) (o Depth-first search)
Búsqueda en profundidad limitada (BPL) (o Depth-limited
search)
Búsqueda con profundidad iterativa (BPI) (o Iterative
deepening search)
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPA
Búsqueda primero en anchura
Es un caso particular de la búsqueda en grafo
Expande el nodo no expandido menos profundo
El test de objetivo es realizado cuando el nodo esgenerado (antes de colocarlo en la frontera)
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPA
Búsqueda primero en anchura
Expande el nodo no expandido menos profundo
Implementación:frontera es una cola FIFO: los nuevos sucesores van al final
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPA
Búsqueda primero en anchura
Expande el nodo no expandido menos profundo
Implementación:frontera es una cola FIFO: los nuevos sucesores van al final
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPA
Búsqueda primero en anchura
Expande el nodo no expandido menos profundo
Implementación:frontera es una cola FIFO: los nuevos sucesores van al final
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPA
Búsqueda primero en anchura
Expande el nodo no expandido menos profundo
Implementación:frontera es una cola FIFO: los nuevos sucesores van al final
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPA
Propiedades
Completa — Si (si b is finito)
Tiempo — b + b2 + b3 + . . . + bd = O(bd), es decir,exp. en d
Espacio — O(bd) (mantiene cada nodo en memoria)
Óptima — Si (si costo = 1 por paso); no es óptima en elcaso general
El Espacio es el gran problema
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPA
Tiempo y memoria en la BPA
Ejemplo: factor de ramificación b = 10, se generan 1 000 000nodos por segundo y cada nodo requiere 1 000 bytes dealmacenamiento.
Profundidad Nodos Tiempo Memoria
2 110 .11 milisegundos 107 kilobytes4 11110 11 milisegundos 10.6 megabytes6 106 1.1 segundos 1 gigabyte8 108 2 minutos 103 gigabytes10 1010 3 horas 10 terabytes12 1012 13 días 1 petabyte14 1014 3.5 años 99 petabytes16 1016 350 años 10 exabytes
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BCU
Búsqueda de costo uniforme
Es la extensión óptima de la BPA.
Expande el nodo que tiene menor costo de paso (no elnodo menos profundo como BPA).
Realiza el test de objetivo cuando el nodo es seleccionadopara expansión (cuando lo saca de la frontera).
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BCU
Búsqueda de costo uniforme
Expande el nodo que tiene menor costo de paso
Implementación:frontera: la cola está ordenada por costo del paso, el más bajo
primero
—Y si los costos de paso son todos iguales?
Equivalente a BPA!!
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BCU
Propiedades
Completa — Si, sólo si costo del paso ≥ ǫ
Tiempo — # de nodos con g ≤ costo de la soluciónóptima, O(b⌈C∗/ǫ⌉) donde C∗ es el costo de la soluciónóptima
Espacio — # de nodos con g ≤ costo de la soluciónóptima, O(b⌈C∗/ǫ⌉)
Óptima — Si, nodos expandidos en orden incremental deg(n)
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPP
Búsqueda primero en profundidad
Expande el nodo no expandido más profundo
Implementación:frontera: cola LIFO, es decir, coloca sucesores al frente
A
B C
D E F G
H I J K L M N O
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPP
Búsqueda primero en profundidad
Expande el nodo no expandido más profundo
Implementación:frontera: cola LIFO, es decir, coloca sucesores al frente
A
B C
D E F G
H I J K L M N O
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPP
Búsqueda primero en profundidad
Expande el nodo no expandido más profundo
Implementación:frontera: cola LIFO, es decir, coloca sucesores al frente
A
B C
D E F G
H I J K L M N O
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPP
Búsqueda primero en profundidad
Expande el nodo no expandido más profundo
Implementación:frontera: cola LIFO, es decir, coloca sucesores al frente
A
B C
D E F G
H I J K L M N O
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPP
Búsqueda primero en profundidad
Expande el nodo no expandido más profundo
Implementación:frontera: cola LIFO, es decir, coloca sucesores al frente
A
B C
D E F G
H I J K L M N O
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPP
Búsqueda primero en profundidad
Expande el nodo no expandido más profundo
Implementación:frontera: cola LIFO, es decir, coloca sucesores al frente
A
B C
D E F G
H I J K L M N O
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPP
Búsqueda primero en profundidad
Expande el nodo no expandido más profundo
Implementación:frontera: cola LIFO, es decir, coloca sucesores al frente
A
B C
D E F G
H I J K L M N O
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPP
Búsqueda primero en profundidad
Expande el nodo no expandido más profundo
Implementación:frontera: cola LIFO, es decir, coloca sucesores al frente
A
B C
D E F G
H I J K L M N O
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPP
Búsqueda primero en profundidad
Expande el nodo no expandido más profundo
Implementación:frontera: cola LIFO, es decir, coloca sucesores al frente
A
B C
D E F G
H I J K L M N O
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPP
Búsqueda primero en profundidad
Expande el nodo no expandido más profundo
Implementación:frontera: cola LIFO, es decir, coloca sucesores al frente
A
B C
D E F G
H I J K L M N O
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPP
Búsqueda primero en profundidad
Expande el nodo no expandido más profundo
Implementación:frontera: cola LIFO, es decir, coloca sucesores al frente
A
B C
D E F G
H I J K L M N O
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPP
Búsqueda primero en profundidad
Expande el nodo no expandido más profundo
Implementación:frontera: cola LIFO, es decir, coloca sucesores al frente
A
B C
D E F G
H I J K L M N O
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPP
Propiedades
Completa — No, falla en espacios de profundidad infinita(espacios con loops). Modificar para evitar estadosrepetidos a lo largo del paso ⇒ completa en espaciosfinitos
Tiempo — O(bm): terrible si m is mucho más largo que d
pero si las soluciones son densas, puede ser mucho másrápido que BPA
Espacio — O(bm), es decir, lineal en espacio!
Óptima — No
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPL
Búsqueda en profundidad limitada
= Búsqueda primero en profundidad PERO incorpora un límite(de profundidad) L, es decir, nodos a profundidad L no tienensucesores
Implementación recursiva:
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPI
Búsqueda en profundidad iterativa
= Búsqueda en profundidad limitada aplicada iterativamente
Implementación recursiva:
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPI
Búsqueda en profundidad iterativa
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPI
Búsqueda en profundidad iterativa
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPI
Búsqueda en profundidad iterativa
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPI
Búsqueda en profundidad iterativa
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPI
Propiedades
Completa — Si
Tiempo — (d + 1)b0 + db1 + (d − 1)b2 + . . .+ bd = O(bd )
Espacio — O(bd)
Óptima — si, con costo de paso = 1
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
BPI
Tiempo y memoria en la BPI vs BPA
Comparación para b = 10 y d = 5, solución en la hoja más a laderecha:
N(BPI) = 50 + 400 + 3000 + 20000 + 100000 = 123450
N(BPA) = 10 + 100 + 1000 + 10000 + 100000 + 999990 = 1111100
BPI se comporta mejor ya que otros nodos a profundidadd no son expandidos
BPA puede ser modificado para testear el objetivo algenerar un nodo
Introducción Agentes resolvedores de problemas Definición Ejemplos Búsqueda Estrategias
Resumen de las estrategias
Criterio BPA BCU BPP BPL BPI
Completa? Si∗ Si∗ No Si, l ≥ d SiTiempo bd b⌈C∗/ǫ⌉ bm bl bd
Espacio bd b⌈C∗/ǫ⌉ bm bl bd
Óptima? Si∗ Si No No Si∗