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
Estrategias de búsqueda ciega, II
Estrategias:
Búsqueda en anchura:
Completo y óptimo
Complejidad espacial =
Complejidad temporal =
número de nodos expandidos =
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
prof. 12, nodos, 35 años, 111 Tb
Estrategias de búsqueda ciega, III
Búsqueda en profundidad:
No es óptimo
Puede encontrar un camino peor
No es completo
Puede no acabar
Complejidad temporal =
Complejidad espacial =
número de nodos necesarios = un camino hasta una hoja y los hermanos de cada nodo del camino =
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
Complejidad temporal =
Complejidad espacial =
número de nodos necesarios = un camino hasta una hoja y los hermanos de cada nodo del camino =
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:
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, ….) =
Método preferido cuando no se conoce la profundidad de la solución.
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:
Problemas:
Cálculo de predecesores.
Varios estados objetivo.
“Encontrar las búsquedas”.
Determinación del tipo de búsqueda en cada dirección.
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:
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 =
Estrategias de búsqueda ciega,VIII
Un resumen se puede ver en:
Eliminación de estados repetidos, I
En ejemplos como para los m+1 estados:
su árbol de búsqueda contendría ramas.
A
B
C
……..
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).
……..
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.
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.
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)))
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)))))
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
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)))
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)))
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 posible-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)))
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)))))))
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))
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))
Ejemplo, I
Realizar búsqueda en anchura (suponemos costes=1):
Estado inicial: A; estados objetivo = {G}
(Gp:) A
(Gp:) B
(Gp:) D
(Gp:) C
(Gp:) F
(Gp:) G
(Gp:) E
Ejemplo, II
Solución (eliminando estados repetidos)
Estado inicial: A; estados objetivo = {G}
(Gp:) A
(Gp:) B
(Gp:) D
(Gp:) C
(Gp:) F
(Gp:) G
(Gp:) E
4
3
6
5
7
2
1
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
 Página anterior | Volver al principio del trabajo | Página siguiente  |