Búsqueda informada y exploración

Estrategias de búsqueda informada (heurísticas)
1. Búsqueda primero el mejor
  1. Funcion evaluacion
    1. Función heurística
2. Búsqueda voraz primero el mejor
  1. Expandir el nodo más cercano al objetivo
  2. Distancia en línea recta
3. Búsqueda A*: minimizar el costo estimado total de la solución
  1. Evalúa los nodos combinando, el coste para alcanzar el nodo, y el coste de ir al nodo objetivo
4. Búsqueda heurística con memoria acotada
  1. Algoritmo sencillo recursivo que intenta imitar la operación de la búsqueda primero el mejor estándar, pero utilizando sólo un espacio lineal
5. Aprender a buscar mejor
  1. Espacio de estados metanivel
  2. Espacio de estados a nivel de objeto
Funciones heurísticas
1. Factor de ramificación eficaz.
2. Inventar funciones heurísticas admisibles
  1. Problema relajado
    1. Problema con menos restricciones en las acciones
    2. El costo de una solución óptima en un problema relajado es una heurística admisible para el problema original
3. Aprendizaje de heurísticas desde la experiencia
  1. Aprendizaje inductivo
    1. Suministrar características
Algoritmos de búsqueda local y problemas de optimización
1. Problemas de optimización
  1. Función objetivo
2. Paisaje del espacio de estados
3. Búsqueda de ascensión de colinas
  1. Bucle que continuamente se mueve en dirección del valor creciente
  2. Máximo local
    1. Pico que es más alto que cada uno de sus estados vecinos, pero más abajo que el máximo global
  3. Crestas
    1. Causan una secuencia de máximos locales que hace muy difícil la navegación para los algoritmos avaros
  4. Meseta
    1. Area del paisaje del espacio de estados donde la función de evaluación es plana
  5. Ascensión de colinas estocástica
    1. Escoge aleatoriamente de entre los movimientos ascendentes; la probabilidad de selección puede variar con la pendiente del movimiento ascendente
  6. Ascensión de colinas de primera opción
    1. Implementa una ascensión de colinas estocástica generando sucesores al azar hasta que se genera uno que es mejor que el estado actual
  7. Ascensión de colinas de reinicio aleatorio
    1. Si no tiene exito reinicia desde un punto aleatorio
4. Búsqueda de temple simulado
  1. Busca no estancarse en mínimos locales
  2. Evita salir del mínimo global
5. Búsqueda por haz local
  1. Si un estado genera buenos sucesores el resto irán a este
  2. Guarda mas de un solo estado en la memoria
6. Algoritmos genéticos
  1. Es una variante de la búsqueda de haz estocástica en la que los estados sucesores se generan combinando dos estados padres, más que modificar un solo estado
  2. Poblacion
    1. Individuo
  3. Función idoneidad
Agentes de búsqueda online y ambientes desconocidos
1. Búsqueda offline
  1. Calcula una solución completa antes de poner un pie en el mundo real y luego ejecutan la solución sin recurrir a su percepciones
2. Busqueda online
  1. Intercala el cálculo y la acción: primero toma una acción, entonces observa el entorno y calcula la siguiente acción
3. Ideal para problemas de exploración donde los estados y las acciones son desconocidas por el agente
4. Problemas de búsqueda en línea
  1. Proporción competitiva
  2. Argumento de adversario
5. Agentes de búsqueda en línea
  1. Luego de una acción el agente recibe una percepción del entorno para aumentar su mapa mental

Next up

Búsqueda informada y exploración

Description

Resource summary

Similar

	Created by Jack Fenix over 5 years ago