Please enable JavaScript.
Coggle requires JavaScript to display documents.
Búsqueda informada y exploración (Algoritmos de búsqueda local (Ascensión…
Búsqueda informada y exploración
Estrategia de búsqueda informada
Búsqueda de soluciones eficiente
Optimalidad
Excesivo ej costo de búsqueda
Tipos
Búsqueda primero el mejor
Búsqueda grafo
Costo mínimo
Expansión de nodos
Uso de función heurística
Búsqueda voraz primero el mejor
Expande todos los nodos
Heurística mínima
No óptima
Eficiente
Función evaluación
Devolver valores de nodos
Escoger mejor nodo
Problema
Posible costo elevado
Búsqueda A*
Minimizar costo total
Nodo origen
Nodo objetivo
Función de evaluación
Costo de camino más barato
Óptima
Función heurística
Admisible
Consistente
Búsqueda heurística con memoria acotada
Expansión de nodos similar a A*
Evita agregar nodos
Eliminar peor nodo hoja
Costo y calidad del subarbol
Óptimo
Solución alcanzable
Función heurística
h(n)
Costo estimado camino más barato
Rendimiento
Factor de ramificación
Problema encontrado
Problemas complejos
Valor cercano a 1
Inventar funciones heurísticas admisibles
Problema relajado
Pocas restricciones
Llega a estado objetivo
Absolver
Generar función heurística
Problema cualquiera
Aprendizaje de heurísticas desde la experiencia
Aproximarse a solución óptima
Inductivo
Evalúa costo de solución
Algoritmos de búsqueda local
Enfoque en estado actual
Desplazarse hacia estados vecinos
Ventajas
Ahorrativos
No usan mucha memoria
No almacenan secuencia de estados
Razonables
Ofrecer posibles soluciones
Óptimo
Encontrar mejor estado
Función objetivo
Ascensión en colina
Contiene
Estado actual
Valor de función objetivo
Iteraciones
Búsqueda hacia arriba
Alcanza lugar más alto
Problemas
Encuentra óptimo local, no global
No garantiza solución óptima
Situaciones
Máximo o mínimo local
Meseta
Cresta
Variantes
Estocástica
Aleatorio
Primera opción
Genera estados aleatorios
Mejor que estado actual
Reinicio aleatorio
Repetición
Encontrar estado objetivo
Temple Simulado
Verifica caminos cuesta arriba
No pasa por estados bajos
Combinación
Ascensión de colinas
Aleatoriedad
Aleatorio
¿Mejora situación?
Aceptado
Haz local
Varios estados
Genera estados sucesores
Escoger mejores sucesores
Algoritmos genéticos
Variante de Haz local
Búsquedas y problemas de optimización
Basado en organismos biológicos
Combinación de dos estados (padres)
Agentes de búsqueda online
Búsqueda online
Entorno desconocido
Agentes exploradores
No conocen sobre el ambiente
Más usados
Problemas
Callejón sin salida
Costo elevado de camino
Búsqueda Local en línea
Ascensión de colinas
Guarda estado actual
No permite reinicio aleatorio
Encontrar objetivo
Aprendizaje en la Búsqueda en Línea
Continuo
Contacto con entorno
Aprender de percepciones
Acción determinada
Mapa de direcciones