Resolución de
problemas
mediante búsqueda
1
Introducción

Agentes basados en el objetivo de
resolución de problemas.
»
»
»
»
Necesaria una formulación de objetivos.
Estados y posibles acciones.
Ejemplo de mapa de carreteras.
Un agente simple de resolución de
problemas:

La función RECOMMENDATION devuelve la
primera acción en la secuencia.
» La función REMAINDER devuelve el
resto.
2
Formulación de
problemas, I

Problema de aspiradora:
» 8 posibles estados
» Los estados están contenidos en esta
figura:

Dos tipos de problemas:
» Problemas de estados únicos.
– Aparecen en entornos accesibles (la percepción
determina completamente el estado) y
deterministas.
» Problemas de estados múltiples.
– Aparecen por ejemplo en entornos no accesibles
o no deterministas.
– Ejemplo (sin sensores; determinista, pero no
accesible):
3
Formulación de
problemas, II

Si el entorno es no determinista (por
ejemplo, “La absorción deposita
algunas veces suciedad, pero sólo
cuando previamente no hay suciedad”):
» Si el entorno es accesible, para cada
estado inicial, hay una secuencia fija de
operadores que llevan al objetivo.
» Si el entorno es semiaccesible (por
ejemplo, si tenemos un sensor de posición
y un sensor local del estado de suciedad):
– entonces, no hay una secuencia fija que
garantice una solución a partir de cualquier
estado:
 Estados (A=aspiradora, S=suciedad):
» (1, AS, S), (2, S, AS), (3, AS, )
» (4, S, A), (5, A, S), (6, , AS)
» (7, A, ), (8, , A)
4
Formulación de
problemas, III


{1,3} --(absorción)-->{5,7}--(derecha)-->
{6,8}--(absorción)-->{6,8}
» La solución sería: absorción, derecha,
absorción, “absorción si sucio”. Es un
árbol de posibles acciones (problema
con contingencias).
Posibles operadores para el estado inicial
{1,3}:
L
L
{1,3}
S
L
{5,7}
R
L
{6,8}
R
{2,4}
R
R
S
S
{5,1,7,3}
S
{.........}
5
Problemas bien definidos

Consideramos los problemas más
sencillos (problema de estado único):
» Estado inicial
» Espacio de estados.
» Posibles acciones (operadores) sobre cada
estado.
– Cada operador obtiene un estado a partir de otro
estado.
» Función objetivo (estados objetivo).
» Función de coste de aplicación de los
operadores.

Un problema de estados múltiples es
un caso particular del caso de un
problema de estado único, en donde
cada estado es un multiestado:
» Estado inicial: multiestado
» Cada operador obtiene un multiestado a
6
partir de otro multiestado.
Ejemplos, I

Los objetivos de la resolución de un
problema mediante búsqueda son:
» Encontrar una solución
» La solución debe tener coste total mínimo:
– Coste de búsqueda:
 Tiempo y memoria necesarios.
– Coste del camino solución.

Ejemplos:
» Problema del 8-puzle.
– Coste operadores: 1
» Problema de las 8 reinas (en general de las
N reinas/damas):
– Coste operadores: 1 (el camino solución siempre
tiene coste 8).
– Posible representación (1):
 estado: n reinas en el tablero
 operadores: añadir una reina a una posición
vacía.
7
Ejemplos, II
– Posible representación (2):
 estado: n reinas en el tablero (no
atacándose).
 Operadores: añadir una reina en la columna
vacía más a la izquierda tal que no sea
atacada por ninguna de las ya existentes.
 Menos operadores que en la representación
1.
» Criptoaritmética.
FORTY
+
TEN
TEN
-----SIXTY
29786
+
850
850
-----31486
– Estados: algunas letras sustituidas por dígitos.
– Operadores: sustituir una letra por un dígito que
no aparece ya dentro del estado.
– La solución se encuentra a profundidad
conocida.
8
Ejemplos, III
» Ejemplo de aspiradora.
– Entorno accesible y determinista.
 Estados: 8.
 Operadores: L, R, S
 Estados objetivo: 7, 8
 Coste: 1
– Agente sin sensores (entorno no accesible, pero
determinista)
 Estados: subconjuntos de los 8
 Coste: 1
 Estados objetivo: estados formados por una
combinación de 7,8.
9
Ejemplos, IV
» Misioneros y caníbales.
– Hay 3 misioneros y 3 caníbales en la orilla
izquierda de un río. Un bote puede transportar a
1 o 2 personas de una orilla a otra. Objetivo:
pasar a todos a la otra orilla.
 Condición: “No puede ocurrir nunca que si
en una orilla hay algún misionero, haya a la
vez un número mayor de caníbales (se los
comerían).”
– Estados:
 Parámetros: número misioneros lado
izquierdo, número caníbales lado izquierdo,
posición bote (izquierda o derecha).
 Se debe verificar la Condición.
– Operadores:
 Transportar 1 misionero.
 Transportar 1 canibal.
 Transportar 2 misioneros.
 Transportar 2 caníbales.
 Transportar 1 misionero y 1 caníbal.
– Coste operador: 1.
10
Ejemplos, V

Otros ejemplos (más reales):
» Problema de mapa de carreteras.
– Viajar de una ciudad a otra recorriendo la menor
distancia posible.
» Problema del viajante de comercio.
– Un viajante debe viajar recorriendo un conjunto
de ciudades. Debe partir de una ciudad inicial y,
tras recorrer todas las ciudades, volver a la
ciudad de inicio.
 Problema clásico: debe visitar exactamente
1 vez todas las ciudades (excepto la de
inicio que la visita 2 veces).
»
»
»
»
Diseño de circuitos.
Navegación de robots.
Montaje mecánico de robots.
Planificación de toma de imágenes
(telescopio Hubble).
11
Algoritmo general de
búsqueda, I

Problema del mapa de carreteras:
» Espacio de estados (finito).
» Árbol de nodos (infinito), generable.

Un nodo:
»
»
»
»
»
Un estado (del espacio de estados).
Su nodo padre.
Operador que lo generó.
Profundidad en el árbol de búsqueda.
Coste desde nodo inicial.
12
Algoritmo general de
búsqueda, II

Algoritmo general de búsqueda
(pseudo-C):
funcion búsqueda-general
(problema, estrategia)
returns una solución o fallo
{
“inicializa árbol de búsqueda con
estado inicial”
loop {
if “no es posible expandir ninguna hoja”,
return fallo
“elige un nodo hoja a expandir,
según la estrategia”
if “el nodo es objetivo”,
return “la solución”
else “expande nodo y añade los nodos
resultantes al árbol de búsqueda”
}
}

Con más detalle:
13
Estrategias de búsqueda
ciega, I


Búsqueda ciega: sin información.
Criterios:
»
»
»
»

Completitud (¿encuentra la solución)
Optimalidad (¿encuentra la mejor solución)
Complejidad espacial (memoria necesaria)
Complejidad temporal (tiempo necesario)
Estrategias de búsqueda:
» Hipótesis:
– Todos los operadores tienen el mismo coste (por
ejemplo 1). El factor de ramificación es siempre
finito.
– m=profundidad máxima del árbol de búsqueda
– d=profundidad de la mejor solución
– b=factor de ramificación
14
Estrategias de búsqueda
ciega, II

Estrategias:
» Búsqueda en anchura:
– Completo y óptimo
d
O
(
b
)
– Complejidad espacial =
– Complejidad temporal =
 número de nodos expandidos =
1  b  b  ...  b 
2
d
1 b
d 1
1 b
 O (b )
d
– Para b=10, 1000 nodos/segundo, 100
bytes/nodo:
 prof. 2, 111 nodos, 0.1 seg., 11 Kb
 prof. 6, 1.000.000 nodos, 18 minutos, 111
Mb
12
 prof. 12, 10
nodos, 35 años, 111 Tb
15
Estrategias de búsqueda
ciega, III
» Búsqueda en profundidad:
– No es óptimo
 Puede encontrar un camino peor
– No es completo
 Puede no acabar
m
– Complejidad temporal = O ( b )
– Complejidad espacial =
 número de nodos necesarios = un camino
hasta una hoja y los hermanos de cada nodo
del camino =
O (bm )
16
Estrategias de búsqueda
ciega, IV
» Búsqueda limitada en profundidad:
– Se utiliza un límite de profundidad (l)
– No es óptimo
 Puede encontrar un camino peor
– No es completo, en general, aunque:
 sí es completo cuando
l  d
– Complejidad temporal =
l
O (b )
– Complejidad espacial =
 número de nodos necesarios = un camino
hasta una hoja y los hermanos de cada nodo
del camino =
O (bl )
17
Estrategias de búsqueda
ciega,V
» Búsqueda iterativa en profundidad:
– Son búsquedas en profundidad con límites: 0, 1,
2, 3, 4, ...
– Es óptimo y completo.
– Complejidad espacial = como en la búsqueda en
profundidad:
O (bd )
– Complejidad temporal = número total de
expansiones (los nodos con profundidad de la
mejor solución se expanden 1 vez; los siguientes
2 veces, los siguientes 3 veces, ....) =
1b  2 b
d
d 1
 3b
d 2
 ....
 ( d  1) b  db  ( d  1)1
2
 O (b )
d
– Método preferido cuando no se conoce la
profundidad de la solución.
18
Estrategias de búsqueda
ciega,VI
» Búsqueda bidireccional:
– Buscar simultáneamente desde estado inicial
hasta objetivo y viceversa hasta que ambas
búsquedas “se encuentren”.
– Optimo y completo.
– Complejidad espacial y temporal:
d
O (b
2
)
– Problemas:
 Cálculo de predecesores.
 Varios estados objetivo.
 “Encontrar las búsquedas”.
 Determinación del tipo de búsqueda en cada
dirección.
19
Estrategias de búsqueda
ciega,VII


Los resultados anteriores pueden no
verificarse cuando los costes de los
arcos son variables.
Búsqueda de coste uniforme:
» Costes variables para los arcos  pero:
cos te (  )  k  0 ,  
» Para un nodo n, se define g(n)=coste
desde nodo inicial.
» Se expande el nodo con menor valor de g.
» Completo y óptimo.
» Si todos los arcos tienen el mismo coste, se
tiene búsqueda en anchura.
– Si todos los arcos tienen el mismo coste 1,
g(n)=profundidad(n)
» Complejidad espacial y temporal =
~
~
O ( b ), d 
d
cos te  de  mejor  solución
minimo  valor  cos tes
20
Estrategias de búsqueda
ciega,VIII

Un resumen se puede ver en:
21
Eliminación de estados
repetidos, I

En ejemplos como para los m+1
estados:
A
B
C
........
su árbol de búsqueda contendría 2
ramas.
m
22
Eliminación de estados
repetidos, II

Para evitar que se repitan estados, se
podrían considerar tres métodos:
» 1) No generar un nodo hijo de un nodo si
los dos pertenecen al mismo estado.
» 2) Evitar ramas con ciclos (en un camino
desde el nodo inicial, hay dos nodos que
pertenecen el mismo estado).
– El método 2) incluye al 1)
........
» 3) Si al generar un nodo, su estado
asociado, ya ha sido generado por otro
nodo, eliminar el nodo peor (y sus
descendientes) del árbol de búsqueda
– El método 3) incluye al 2) y, por tanto, al 1)
– Este método es el más caro (hay que mantener
todos los nodos en memoria).
23
Problemas de satisfacción
de restriciones, I


Variables. Posibles valores en dominios
(conjuntos finitos o infinitos).
Restricciones
» Eecuaciones (condiciones) entre las
variables.

Ejemplos:
» Problema 8 damas.
» Criptoaritmética.
24
Problemas de satisfacción
de restriciones, II

Los problemas discretos (el dominio es
finito) se pueden resolver utilizando
búsqueda:
» Estado inicial: todas las variables sin
asignar.
» Profundidad máxima=número de
variables=profundidad de todas las
soluciones.
– Se puede utilizar, por tanto, búsqueda en
profundidad.
» Cardinal espacio búsqueda=producto de
cardinales de los dominios de las variables.
» Se pueden hacer:
– Eliminación de ramas en donde alguna
restricción no se satisface (y se hace
“backtracking”)
– Propagación de restricciones, para reducir los
posibles valores de las variables por asignar.
25
Ejemplo, I

El problema del 8-puzle se podría
representar en LISP.
;;; EJEMPLO DE REPRESENTACION DE UN
PROBLEMA (sin variables)
(setf *estado0* '((0 1) (1 2) (2 3)
(3 4) (4 NIL) (5 5)
(6 6) (7 7) (8 8)))
(setf *problema-8-puzle*
'(:8-puzle
(:estado-inicial *estado0*)
(:operadores
(:mueve-arriba
(:accion #'mueve-arriba))
(:mueve-abajo
(:accion #'mueve-abajo))
(:mueve-izquierda
(:accion #'mueve-izquierda))
(:mueve-derecha
(:accion #'mueve-derecha)))
(:estados-objetivo #'reconoce)))
26
Ejemplo, II
(defun reconoce (estado)
(equal estado '((0 1) (1 2) (2 3)
(3 4) (4 8) (5 5)
(6 6) (7 7) (8 NIL))))
(defun posible-mover-arriba-p (estado)
(let ((posicion (posicion NIL estado)))
(not (member posicion '(0 1 2)))))
(defun posible-mover-abajo-p (estado)
(let ((posicion (posicion NIL estado)))
(not (member posicion '(6 7 8)))))
(defun posible-mover-izquierda-p (estado)
(let ((posicion (posicion NIL estado)))
(not (member posicion '(0 3 6)))))
(defun posible-mover-derecha-p (estado)
(let ((posicion (posicion NIL estado)))
(not (member posicion '(2 5 8)))))
27
Ejemplo, III
(defun mueve-arriba (estado)
(if (posible-mover-arriba-p estado)
(let* ((nuevo-estado
(copy-tree estado))
(posicion-vacia
(posicion NIL
nuevo-estado))
(posicion-arriba
(- posicion-vacia 3))
(ficha-arriba
(ficha posicion-arriba
nuevo-estado)))
(coloca posicion-arriba NIL
nuevo-estado)
(coloca posicion-vacia
ficha-arriba
nuevo-estado)
nuevo-estado)))
;;; Análogos mueve-abajo, mueve-izquierda
;;; y mueve-derecha
28
Ejemplo, IV
(defun posicion (ficha estado)
(first (first
(member ficha estado
:test
#'(lambda (x y)
(eql x
(second y)))))))
(defun coloca (posicion ficha estado)
(setf (second (nth posicion estado))
ficha))
(defun ficha (posicion estado)
(second (nth posicion estado)))
29
Ejemplo, V
;;; EJEMPLO DE REPRESENTACION DE UN
;;; PROBLEMA (con variables)
(setf *estado0* '((0 1) (1 2) (2 3)
(3 4) (4 NIL) (5 5)
(6 6) (7 7) (8 8)))
(setf *problema-8-puzle*
'(:8-puzle
(:estado-inicial *estado0*)
(:operadores
(:mueve
(:variables
(direccion
'(arriba abajo derecha izquierda)))
(:accion #'mueve)))
(:estados-objetivo #'reconoce)))
30
Ejemplo, VI
(defun reconoce (estado)
(equal estado '((0 1) (1 2) (2 3)
(3 4) (4 8) (5 5)
(6 6) (7 7) (8 NIL))))
(defun posible-mover-p (direccion estado)
(cond ((eql direccion 'arriba)
(posible-mover-arriba-p estado))
((eql direccion 'abajo)
(posible-mover-abajo-p estado))
((eql direccion 'izquierda)
(posible-mover-izquierda-p
estado))
((eql direccion 'derecha)
(posible-mover-derecha-p
estado))))
(defun posible-mover-arriba-p (estado)
(let ((posicion (posicion NIL estado)))
(not (member posicion '(0 1 2)))))
;;; Análogo para posible-mover-abajo-p,
;;; posible-mover-izquierda-p y posible31
mover-derecha-p
Ejemplo, VII
(defun mueve (direccion estado)
(if (posible-mover-p direccion estado)
(let* ((nuevo-estado
(copy-tree estado))
(posicion-vacia
(posicion NIL
nuevo-estado))
(posicion-nueva
(nueva-posicion
direccion
posicion-vacia))
(ficha-nueva
(ficha posicion-nueva
nuevo-estado)))
(coloca posicion-nueva NIL
nuevo-estado)
(coloca posicion-vacia ficha-nueva
nuevo-estado)
nuevo-estado)))
32
Ejemplo, VIII
(defun nueva-posicion (direccion
posicion-vacia)
(cond ((eql direccion 'arriba)
(- posicion-vacia 3))
((eql direccion 'abajo)
(+ posicion-vacia 3))
((eql direccion 'izquierda)
(- posicion-vacia 1))
((eql direccion 'derecha)
(+ posicion-vacia 1))))
(defun posicion (ficha estado)
(first (first
(member ficha estado
:test
#'(lambda (x y)
(eql x
(second y)))))))
33
Ejemplo, IX
(defun coloca (posicion ficha estado)
(setf (second (nth posicion estado))
ficha))
(defun ficha (posicion estado)
(second (nth posicion estado)))
;;; REPRESENTACION CON ESTRUCTURAS DE LISP
(defstruct problema
nombre
estado-inicial
operadores
test-objetivo)
(defstruct operador
nombre
accion
(variables nil))
34
Ejemplo, X
(setf *operadores*
(list
(make-operador
:nombre 'mueve-arriba
:accion #'mueve-arriba)
(make-operador
:nombre 'mueve-abajo
:accion #'mueve-abajo)
(make-operador
:nombre 'mueve-derecha
:accion #'mueve-derecha)
(make-operador
:nombre 'mueve-izquierda
:accion #'mueve-izquierda)))
(setf *problema-8-puzle*
(make-problema
:nombre '8-puzle
:estado-inicial *estado0*
:operadores *operadores*
:estados-objetivo #'reconoce))
35
Ejemplo, I

Realizar búsqueda en anchura
(suponemos costes=1):
A
B
C
F
D
G
E

Estado inicial: A; estados objetivo = {G}
36
Ejemplo, II

Solución (eliminando estados
repetidos)
A 1
2 B
3
5
D

E
6
C
4
F
7
G
Estado inicial: A; estados objetivo = {G}
37
Otros ejemplos



Problema del viajante de comercio.
Análisis sintáctico.
Otros de la hoja 3 de problemas:
» Localización de una moneda falsa.
» Reconocimiento de cadenas de caracteres
para una expresión regular.
» etc
38
Descargar

Búsqueda no informada