Please enable JavaScript.
Coggle requires JavaScript to display documents.
IA: Búsqueda informada y exploración (Estrategias de búsqueda informada…
IA: Búsqueda informada y exploración
Estrategias de búsqueda informada (heurísticas)
Búsqueda primero el mejor:
selecciona un nodo, para expander basado en la f. de evaluación.
Escoje la evaluación más baja.
Venerable pero inexacto.
Usa una
función heurística
Búsqueda recursiva del primero mejor:
imita a BPEM pero utiliza solo un espacio lineal.
Mantiene la pista del f-valor de la mejor alternativa, si excede el actual, se devuelve a este camino alternativo. Se va sustituyendo los f-valores del camino con el de su hijo.
Más eficiente que A*PI pero tiene regeneración excesiva de nodos ):
Búsqueda voraz primero el mejor:
expandir el nodo más cercano al objetivo.
Caso de Rutas, lo hace con una distancia en línea recta
Puede caer en repetidos
Ventajas falsas
Búsqueda A*:
Evalúa los nodos combinando g(n), el coste para alcanzar el nodo, y h(n), el coste de ir al nodo objetivo.
El cálculo complementario es complicado pero es óptimo
Consistencia:
o montonía, una heurística es consistente si para cada nodo y sucesor el coste estimado para llegar al objetivo > que llegar al sucesor + alcanzar el objetivo.
Si es consistente también es admisible.
Curvas de nivel:
si los f-costos no bajan se dibujan estas curvas
Podado:
cuando se eliminan posibilidades sin tener que examinarlas
A* es óptimamente eficiente para cualquier f. heurística, pero no es práctico para problemas grandes.
Búsqueda heurística con memoria acotada:
se adapta A* a la idea de profundizar iterativamente al contexto de búsqueda heurística
Práctico para problemas de costos unidad y no mantiene colas.
Sufre con costos de valores reales.
A*M:
A* con memoria acotada
A*MS:
A*M simplificado
Retira la peor hoja.
Sucede similar al Thrashing.
Aprender a buscar mejor
Estado metanivel:
Cada estado en un espacio de estados metanivel captura el estado interno (computacional) de un programa que busca en un espacio de estados a nivel de objeto.
Algoritmo de aprendizaje metanivel:
aprende de estas experiencias para evitar explorar subárboles no prometedores
Funciones heurísticas
La distancia en la ciudad o distancia de Manhattan:
suma distancias horizontales y verticales.
El efecto de la precisión heurística en el rendimiento
Factor de ramificación eficaz
Una heurística bien diseñada tendría un valor de b* cerca de 1.
Inventar funciones heurísticas
Problema relajado:
tiene menos restricciones
Modelo de bases de datos:
almacenan estos costos exactos de las soluciones para cada posible subproblema.
Aprendizaje de heurísticas desde la experiencia
Aprendizaje inductivo:
un algoritmo que hace una función para predecir costos.
Ocupan características.
Algoritmos de búsqueda local y problemas de optimización
Búsqueda local solo usan un estado, actual.
Usan poca memoria.
Pueden encontrar soluciones razonables en lugares grandes.
Resuelven problemas de optimzación segun f. objetivo.
Pisaje del espacio de estados:
osea tiene una posición y elevación.
Usan formulación de estados completa.
Búsqueda de ascensión de colinas:
es un bucle que continuamente se mueve en dirección del valor creciente
Búsqueda local voraz
Máximo local: es más alto que cada uno de sus vecinos pero abajo de global.
Crestas
Meseta: f. evaluación es plana
Ascensión de colinas
La ascensión de colinas estocástica escoge aleatoriamente de entre los movimientos ascendentes
La ascensión de colinas de primera opción implementa una ascensión de colinas estocástica generando sucesores al azar hasta que se genera uno que es mejor que el estado actual
La ascensión de colinas de reinicio aleatorio, si al principio usted no tiene éxito, intente, intente otra vez
Búsqueda de temple simulado:
combina ascensión de colinas con un camino aleatorio de algún modo que produzca tanto eficaz
Usa gradiente desceendente
Sube y baja
Búsqueda por haz local:
guarda la pista de k estados
Si es objetivo para.
El algoritmo rápidamente abandona las búsquedas infructuosas y mueve sus recursos a donde se hace la mayor parte del progreso
Estocástica elige aleatoriamente.
Algoritmos genéticos:
combina y muta, rep. sexual.
Población
Individuo
Función idoneidad:
valores más altos para estados meores.
Cruce: el punto
Mutación: cambia
Esquemas
Cada cadema es una instancia
Búsqueda local en espacios continuos
Un modo de evitar problemas continuos es simplemente discretizar la vecindad de cada estado
Gradiente: se utiliza para encontrar un máximo.
Gradiente empírico:
puede determinarse evaluando la respuesta a pequeños incrementos y decrecimientos en cada coordenada
Línea de búsqueda: amplia dirección del gradiente actual.
Optimización con restricciones: está restringido si las soluciones debieran satisfacer algunas restricciones sobre los valores de cada variable.
Agentes de búsqueda online y ambientes desconocidos
Búsqueda offline
Búsqueda online, se usa para un problema de exploración.
Local
Agentes
Aprendizaje de