Resolver problemas mediante busqueda

Agentes resolventes - problemas
1. Formulacion del objetivo
  1. Decidir metas
2. Formulacion del problema
  1. Decidir acciones y estados a considerar
    1. Secuencia de acciones
      1. Busqueda
        Proceso de hallar una secuencia
      2. Solucion
      3. Ejecucion
        Ejecutar las acciones que recomienda la solucion
  2. Abstraccion
3. Problemas y soluciones
  1. Estado inicial
  2. Funcion sucesor
    1. Espacio de estados
      1. Camino
        Secuencia de estados
        Secuencia de acciones
  3. Test objetivo
    1. Determina si un estado es un estado objetivo
  4. Costo del camino
    1. Asigna un costo numérico a cada camino
      1. Costo individual de cada accion
  5. Solucion optima
Ejemplos de problemas
1. Juguete
  1. 8 Puzle
    2. Alcanzar el estado objetivo deslizando las piezas
    3. Test para las IA
  2. 8 Reinas
    2. Colocar las ocho reinas en un tablero de ajedrez de manera que cada reina no ataque a ninguna otra
    3. Test para los algoritmos de busqueda
2. Mundo real
  1. Problema de busqueda de una ruta
    1. Rutas en redes de computadoras
    2. Planificacion de operaciones militares
    3. Sistemas de planificación de viajes de líneas aéreas
  2. Ploblemas turisticos
    1. Relacionados con los problemas de búsqueda de una ruta pero incluyen los anteriores destinos
  3. Problema del viajante de comercio
    1. Cada destino solo se visita una vez
    2. Encontrar viaje mas corto
  4. Distribución VLSI
    1. Colocación de millones de componentes y de conexiones en un chip verificando que el área es mínima
      1. Distribución de las celdas
      2. Dirección del canal
  5. Navegación de un robot
    1. Se requiere es que las técnicas avanzadas hagan el espacio de búsqueda finito
  6. Secuenciación para el ensamblaje automático
    1. Lo principal es encontrar un orden en los objetos a ensamblar
  7. Búsqueda en Internet
    1. Búsqueda de respuestas a preguntas
Busqueda de soluciones
1. Arbol de busqueda
  1. Nodo de busqueda
    1. Estado inicial
  2. Expandir
    1. Aplicar la función sucesor al estado actual
    2. Generar un nuevo conjunto de estados
  3. Estrategia de búsqueda
  4. Frontera
    1. Nodos que se han generado pero todavía no se han expandido
  5. Hoja
    1. Nodo sin sucesor
2. Medir rendimiento
  1. Completitud
    1. El algoritmo encontrara solucion cuando exista
  2. Optimización
    1. Encuentra la solucion optima
  3. Complejidad en tiempo
    1. Cuánto tarda en encontrar una solución
  4. Complejidad en espacio
    1. Cuánta memoria se necesita para el funcionamiento
3. Estrategias de búsqueda no informada
  1. No se tiene información adicional acerca de los estados más allá de la que proporciona la definición del problema
  2. Primero en anchura
    1. Se expande primero el nodo raíz, a continuación se expanden todos sus sucesores
    2. Necesita mucha memoria
    3. Dura mas que los otros metodos
  3. Costo uniforme
    1. Expande el nodo n con el camino de costo más pequeño
    2. Está dirigida por los costos de los caminos
  4. Primero en profundidad
    1. Siempre expande el nodo más profundo en la frontera actual del árbol de búsqueda
    2. Utiliza poca memoria
    3. Variante busqueda hacia atras
  5. Profundidad limitada
    1. Los nodos a profundidad L se tratan como si no tuvieran ningún sucesor
  6. Primero en profundidad con profundidad iterativa
    1. Se hace aumentando gradualmente el límite hasta que se encuentra un objetivo
  7. Bidireccional
    1. Ejecutar dos búsquedas simultáneas: una hacia delante desde el estado inicial y la otra hacia atrás desde el objetivo, parando cuando las dos búsquedas se encuentren en el centro
Evitar estados repetidos
1. Dos rutas que llevan al mismo estado
2. No hacerlo lleva a convertir problemas resolubles en irresolubles
Búsqueda con información parcial
1. Problemas sin sensores
  1. Si el agente no tiene ningún sensor, entonces (por lo que sabe) podría estar en uno de los posibles estados iniciales, y cada acción por lo tanto podría conducir a uno de los posibles estados sucesores
2. Problemas de contingencia
  1. Si el entorno es parcialmente observable o si las acciones son inciertas, entonces las percepciones del agente proporcionan nueva información después de cada acción
3. Problemas de exploración
  1. Cuando se desconocen los estados y las acciones del entorno, el agente debe actuar para descubrirlos

Next up

Resolver problemas mediante busqueda

Description

Resource summary

Media attachments

Similar

	Created by Jack Fenix over 5 years ago