“Búsqueda ciega, no informada”



Descargar 26,01 Kb.
Fecha de conversión15.03.2017
Tamaño26,01 Kb.
  • Resolución de
  • problemas
  • mediante búsqueda
  • “Búsqueda ciega, no informada”
  • “Búsqueda heurística, informada”

Introducción

  • Agentes de resolución de problemas: es un tipo de agentes basados en el objetivo.
  • Algoritmos no informados: no disponen de ninguna información adicional a la propia definición del problema
    • Es necesario realizar
      • formulación de objetivos basada en:
        • la situación actual
        • medida sobre el desempeño de la tarea
      • Formulación del problema mediante
        • estados posibles
        • acciones a ejecutar
    • Algoritmo: simple-problem-solving-agent
      • Diseñado: Formulate, Search, Execute
    • Ejemplos
  • Agente simple de resolución de problemas
  • Etapas de la resolución de problemas con objetivos:
  • 1. Formulación de objetivos
  • 2. Formulación del problema
  • 3. Búsqueda de la secuencia de acciones que deberían resolver el problema
  • 4. Ejecuta las acciones una cada vez
  • “Formulate, Search, Execute”
  • Obs:
  • RECOMMENDATION
    • devuelve la primera acción (first) de la secuencia.
  • REMAINDER
    • devuelve el resto (rest) de la secuencia
  • (Russell 2nd. Ed.)

Formulación de problemas, I (ejemplo)

  • Problema de aspiradora:
    • Se dispone de una aspiradora con acceso a dos habitaciones y con la capacidad de aspirar basura
    • 8 posibles estados
    • 3 posibles acciones
    • Mundo: 2 posibles posiciones
      • Sucio - limpio
    • Dos tipos de problemas:
      • Problema de estados únicos:
        • entornos accesible y determinista
      • Problema de estados múltiples:
      • DEF: 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 partir de otro multiestado.

Formulación de problemas, II (abstracción)

  • Las acciones que puede
  • realizar el agente:
  • L: left (izquierda)
  • R: right (derecha)
  • S: suck (aspirar)
  • El mundo tiene dos posiciones: puede haber o no suciedad
  • El agente está en una u otra posición
  • Objetivo: limpiar toda la
  • suciedad.
  • Equivale al conjunto de
  • estados {7,8}
  • 1
  • 2
  • 5
  • 6
  • 3
  • 4
  • 7
  • 8

Formulación de problemas, III (abstracción)

Formulación de problemas, IV (definición)

  • Abstracción de un problema
    • DEF: Proceso de eliminar los detalles de la representación formal de un problema
  • Problemas bien definidos
    • La formulación de un problema requiere
      • Especificación de estados iniciales: uno o más estados que describen las situaciones de partida
      • Especificación de estados objetivos: uno o más estados que podrían ser soluciones admisibles del problema
        • Función/test objetivo: determina si un estado es un estado objetivo.
      • Especificación del conjunto de acciones/operadores que pueden realizarse sobre cada estado.
        • Función sucesor: estando en un estado, aplicando un operador indica a qué estado se accede. S: x  S(x)
      • Definición de un espacio de estados del problema
        • Conjunto de todos los estados alcanzables a partir del estado inicial aplicando cualquier secuencia de operadores
        • Determina un grafo: estados - arcos - caminos
      • Función de coste de aplicación de los operadores
  • Estados?
  • Posiciones de la suciedad y del robot
  • 1
  • 2
  • 5
  • 6
  • 3
  • 4
  • 7
  • 8
  • Operadores?
  • Left (L), right (R), suck (S)
  • 1 por operador
  • NoDirt(x)
  • Coste del camino?
  • Objetivo?
  • (1, AS, S), (2, S, AS), (3, AS, ) (4, S, A), (5, A, S), (6, , AS)
  • (7, A, ), (8, , A)
  • Formulación de problemas, V (Problema Bien Definido)
  • Estado inicial?
  • El que se designe
  • Función sucesor?
  • (1 R 2), (1 S 5) …

Resolución de problemas, I

  • La resolución de un problema consiste en definir un conjunto de acciones que nos permita llegar al objetivo.
    • Para la resolución de un determinado problema se necesita su formulación.
    • El entorno del problema influye sobre el curso de acciones hacia la solución.
      • Ejemplo (En un entorno no determinista)
        • 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 (sensor de posición y sensor local suciedad) 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)

Resolución de problemas, II

        • {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)
  • {1,3}
  • {5,7}
  • {2,4}
  • {6,8}
  • {5,1,7,3}
  • S
  • L
  • S
  • R
  • L
  • R
  • S
  • L
  • R
  • L
  • R
  • S
  • {.........}
  • 1
  • 2
  • 5
  • 6
  • 3
  • 4
  • 7
  • 8
  • Secuencia solución: Absorción - derecha – absorción
  • {1,3} --> {5,7} --> {6,8} --> {6,8}
  • Resolución de problemas, III

Resolución mediante búsqueda

  • La resolución de un problema de IA mediante búsqueda consiste en la aplicación de una determinada estrategia de control que conduzca a encontrar un camino desde el estado inicial hasta algún estado objetivo del espacio de estados.
  • Los objetivos fundamentales de la resolución de un problema mediante búsqueda son:
    • Encontrar una solución
    • Que la solución tenga coste total mínimo:
      • Coste de búsqueda (coste offline):
        • Tiempo y memoria necesarios.
      • Coste del camino solución (coste online).
  • Ejercicio Problema del 8-puzzle
  • Estados?
  • Operadores?
  • Coste del camino?
  • Objetivo?
  • Puzzle con 8 piezas, hay que llegar del estado inicial al objetivo, moviendo el hueco.
  • Estado inicial?
  • Ejercicio Problema de las N reinas
  • Estados?
  • Operadores?
  • Coste del camino?
  • Tablero con N reinas o damas.
  • Encontrar configuración de las damas no enfrentadas entre si
  • Objetivo?
  • Es esto una solución?
  • No, se amenazan
  • Estado inicial?

Ejemplos, I

  • Problema del 8-puzzle
    • Estados: posiciones de las piezas y hueco
      • (setf *estado0*
        • ‘((0 5)(1 4)(2 nil)
        • (3 6)(4 1)(5 8)
        • (6 7) (7 3) (8 2))
    • Operadores:
      • HuecoA: Dcha – Izda – Arriba – Abajo
    • Objetivo: (ver gráfico anterior)
    • 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.
    • 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)

Ejemplos, II

  • Problemas de Criptoaritmética
    • 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.
      • Todas las soluciones son igualmente válidas luego el coste del camino es 0
  • FORTY
  • + TEN
  • TEN
  • ------
  • SIXTY
  • 29786
  • + 850
  • 850
  • ------
  • 31486

Ejemplos, III

  • 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 ó 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 caníbal.
      • Transportar 2 misioneros.
      • Transportar 2 caníbales.
      • Transportar 1 misionero y 1 caníbal.
    • Coste operador: 1

Ejemplos, IV

  • 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).
    • Problemas de
      • Diseño de circuitos.
      • Navegación de robots.
      • Montaje mecánico de robots.
      • Planificación de toma de imágenes (telescopio Hubble).

Búsqueda en árboles, I

  • Representación de un nodo:
    • Estado: elemento del espacio de estados que corresponde con el nodo.
    • Nodo padre: el nodo en el árbol de búsqueda que ha generado este nodo.
    • Acción/Operador: operador que se aplicó al padre para generar este nodo.
    • Coste del camino: el coste desde el nodo inicial. Denotado por g(n).
    • Profundidad en el árbol de búsqueda: número de pasos a lo largo del camino desde el nodo inicial.
  • Distinguir los conceptos:
    • Espacio de estados:
      • Finito
    • Árbol de nodos: se genera
    • Ejemplo: mapa de carreteras

Búsqueda en árboles, II

  • Algoritmo de búsqueda en árboles (descripción informal):
    • funcion búsqueda-árboles (problema, estrategia)
    • devuelve una solución o fallo
    • inicializa árbol de búsqueda con estado inicial
    • bucle hacer
      • si no hay candidatos para expandir,
      • entonces devolver fallo
      • en otro caso
      • escoger, según estrategia, nodo para expandir
      • si el nodo es objetivo (contiene estado objetivo)
      • entonces devolver solución
      • en otro caso
      • expandir nodo
      • añadir nodos resultantes al árbol

Búsqueda no informada vs búsqueda informada

  • Búsqueda no informada o ciega:
    • Sólo usan la información de la definición del problema.
  • Estrategias:
    • Búsqueda primero en anchura.
    • Búsqueda primero en profundidad.
    • Búsqueda limitada en profundidad.
    • Búsqueda iterativa en profundidad.
    • Búsqueda bidireccional.
  • Búsqueda informada o heurística:
    • Usan la información de definición del problema y el coste del estado actual al objetivo.
  • Estrategias:
    • Best first
    • Búsqueda Avara
    • A*
    • IDA*
    • Mejora iterativa

Estrategias de búsqueda ciega, I

  • Criterios de evaluación de estrategias:
    • Completitud (encontrar solución)
    • Optimización (encontrar 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.
    • Las complejidades temporal y espacial se miden en términos de:
      • m = profundidad máxima del árbol de búsqueda (puede ser infinito)
      • d = profundidad de la mejor solución (de la de menor coste)
      • b = factor de ramificación (máximo nº de sucesores de cualquier nodo del árbol de búsqueda)

Estrategias de búsqueda ciega, II

  • Búsqueda en anchura:
    • Completo y óptimo
    • Complejidad espacial =
    • Complejidad temporal =
      • número de nodos expandidos =
      • Número de nodos generados
        • Para b=10, 1000 nodos/segundo, 100 bytes/nodo:
          • d=2, 111 nodos, 0.1 seg., 11 Kb
          • d=6, 1.000.000 nodos, 18 minutos, 111 Mb
          • d=12, nodos, 35 años, 111 Tb
    • Ejemplo: viajante de comercio

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 =
    • Ejemplo: viajante de comercio

Estrategias de búsqueda ciega, IV

  • Búsqueda limitada en profundidad:
    • Caso particular de Búsqueda 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 =
    • Complejidad temporal
      • número total de expansiones (los nodos con la 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 iterativa en profundidad (abstracción gráfica)

Estrategias de búsqueda ciega, VII

  • 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:
    • Dificultades
      • Cálculo de predecesores.
      • Varios estados objetivo.
      • Significado de “encontrarse las búsquedas”.
      • Determinación del tipo de búsqueda en cada dirección.
    • Ejemplo: viajante de comercio

Estrategias de búsqueda ciega, VIII

  • Búsqueda de coste uniforme:
    • Los resultados anteriores pueden no verificarse cuando los costes de los arcos son variables  tener en cuenta costes
    • 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, g(n)=profundidad(n)
    • Complejidad espacial y temporal =
    • Ejemplo: viajante de comercio

Estrategias de búsqueda ciega, IX

  • Cuadro resumen:

Eliminación de estados repetidos, I

  • La repetición de estados incrementa la complejidad de la estrategia de búsqueda
  • Si la estrategia no los detecta (comparar el nodo a expandir con los ya expandidos), un problema resoluble puede llegar a ser irresoluble.
  • Situación habitual en problemas de rutas y acciones reversibles
    • Ejemplo: espacio con d+1 estados
  • Para los d+1 estados (d es la profundidad máxima)
  • El árbol de búsqueda contendrá 2d ramas. Poda.

Eliminación de estados repetidos, II

  • Para evitar que se repitan estados, se pueden considerar tres métodos:
    • No generar un nodo hijo de un nodo si los dos pertenecen al mismo estado
    • 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)
    • 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).
  • Estructuras de datos
    • Listas cerradas (nodos expandidos)
    • Listas abiertas (frontera de nodos no expandidos)
  • Algoritmo general de búsqueda en grafos
    • (Russell, 2nd. Ed., sec. 3.5)

Ejemplo

  • Realizar búsqueda en anchura (eliminando estados repetidos) (suponemos costes=1):
  • Estado inicial: A
  • estados objetivo: {G}
  • A
  • B
  • D
  • C
  • F
  • G
  • E
  • A
  • B
  • D
  • C
  • F
  • G
  • E
  • 4
  • 3
  • 6
  • 5
  • 7
  • 2
  • 1
  • SOLUCIÓN

Problemas de satisfacción de restricciones, I

  • Constraint Satisfaction Problems (CSP)
  • Problema definido por:
    • Un conjunto de variables cuyos valores están definidos en un dominio (finitos o infinito)
    • Un conjunto de restricciones que involucran una o más variables del problema (ecuaciones lineales/no lineales)
    • Los estados del problema que se definen mediante asignaciones variable – valor
    • Una función objetivo que optimice la solución del CSP
  • Estrategia de backtracking
    • Búsqueda en profundidad
    • Asigna valores a variables (una cada vez)
    • Retrocede en el árbol cuando el dominio de asignación de una variable en el árbol es vacío
  • Ejemplos
    • Problema 8 damas.
    • Criptoaritmética.

Problemas de satisfacción de restricciones, II

  • Los problemas discretos (dominio 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 puede hacer:
      • Eliminación de ramas en donde alguna restricción no se satisface (backtracking)
      • Propagación de restricciones, para reducir los posibles valores de las variables por asignar.

Otros ejemplos

  • Problema del viajante de comercio
  • NLP
    • Problemas de análisis sintáctico
  • Ejercicios de la hoja 3
    • Localización de una moneda falsa.
    • Reconocimiento de cadenas de caracteres para una expresión regular.
    • Etc.


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal