Resolucion - T9

Búsqueda Heurística

• La búsqueda heurística busca optimizar el número de nodos examinados en un espacio de búsqueda.
• La efectividad de esta búsqueda depende del heurístico seleccionado.

Heurísticos en el Puzle 8

• El "Puzle 8" consiste en reordenar ocho elementos en un tablero de 3x3 a partir de una configuración inicial.
• El objetivo es lograr una configuración final deseada.
• Dos heurísticos propuestos para el Puzle 8 son:
  • h1: Número de fichas mal colocadas; un mayor valor indica un peor estado.
  • h2: Distancia Manhattan; suma de las distancias de las fichas mal colocadas.

Evaluación de Heurísticos

• La elección del heurístico afecta la rapidez para alcanzar la solución.
• En ejemplos analizados, el movimiento óptimo se correlaciona con el segundo heurístico (h2).
• No siempre es fácil elegir el heurístico adecuado y no garantizan soluciones óptimas.

Rendimiento de Heurísticos

• Los heurísticos son estimativos, pueden llevar a errores en la solución.
• Un heurístico útil brinda soluciones suficientemente buenas la mayoría de las veces.
• Ejemplo de cálculo: h3 para una posición inicial (3 + 3 (2 + 2 + 1) = 18).

Admisibilidad de Heurísticos

• La tabla de valores muestra que los primeros dos heurísticos son admisibles, mientras que h3 no lo es debido a un valor superior al requerimiento para la solución.

Búsqueda en Juegos

• Consiste en identificar jugadas que permitan ganar ante un oponente.
• Abarca estrategias en juegos de dos jugadores con movimientos alternos, sin intervención del azar.

Métodos de Búsqueda de Soluciones

• La comprensión de los métodos de búsqueda es esencial para resolver problemas y se complementa con lecciones magistrales y recursos adicionales.
• Los alumnos deben ser capaces de describir y aplicar métodos de búsqueda adecuados según el problema presentado.

Tipos de Agentes

• Existen dos tipos de agentes: inteligentes y no inteligentes.
• Los agentes no inteligentes actúan según objetivos fijos y no se adaptan a situaciones nuevas.
• Los agentes inteligentes toman decisiones basadas en su estado, capacidades y objetivos, adaptándose dinámicamente.

Algoritmos de Búsqueda

• Algoritmos de búsqueda evalúan estados generados y determinan su viabilidad como soluciones potenciales.
• Se utilizan funciones heurísticas que miden la cercanía de los nodos al objetivo, ayudando a limitar la búsqueda en espacios grandes.

Aplicación de Heurísticos

• Heurísticos deciden qué nodo expandir y cuál sucesor considerar primero, optimizando el proceso de búsqueda.
• Expandir el nodo padre genera nodos hijos, que se clasifican en listas de nodos cerrados (expandidos) y abiertos (no expandidos).

Ejemplo de Progreso de Nodos

• En cada iteración, se evalúan nodos abiertos para encontrar uno que cumpla con el objetivo.
• Si ningún nodo abierto es la solución, se selecciona el más prometedor basado en una función heurística.

Algoritmo Minimax en Juegos

• El algoritmo Minimax se aplica en juegos de dos jugadores, MAX y MIN, donde MAX busca maximizar su ventaja y MIN minimizar la de MAX.
• Cada nivel del árbol de juego alterna entre nodos MAX y MIN, evaluando posibles jugadas.

Propagación de Valores

• Los nodos finales del árbol reciben valores: 1 para victoria de MAX y 0 para victoria de MIN.
• Los valores se propagan hacia arriba: en nodos MAX se toma el máximo de sus hijos, mientras que en nodos MIN se toma el mínimo.

Aplicaciones de Algoritmos de Búsqueda

• Algoritmos como CRP de Bing Maps y CH utilizado por OSRM mejoran el enrutamiento en redes de carreteras.
• Transfer Patterns y RAPTOR son usados por Google Maps y OpenTripPlanner, optimizando viajes de transporte público.
• Servicios de transporte como Uber y Cabify también emplean algoritmos de búsqueda para optimizar la contratación de VTC.

Descripción del entorno del robot

• El objetivo es describir el estado del entorno del robot mediante fórmulas que representan su posición y relación con otros objetos.
• Fórmulas clave:
  • MANO_LIBRE
  • SOBRE(B,C)
  • SOBRE(A,B)
  • SOBRE_LA_MESA(C)

Operadores STRIPS

• Los operadores STRIPS modelan acciones a través de tres componentes:
  • Precondiciones (P): condiciones que deben cumplirse para que se ejecute la acción.
  • Borrar (B): fórmulas que se eliminan de la descripción del entorno después de ejecutar la acción.
  • Añadir (A): fórmulas que se incorporan a la descripción del entorno tras la acción.

Procedimientos de búsqueda

• El objetivo de la búsqueda es encontrar un camino entre estados iniciales y finales (u objetivos).
• Existen dos enfoques de búsqueda:
  • Hacia adelante: busca un camino desde el estado inicial al final, utilizando información conocida.
  • Hacia atrás: inicia desde el estado final y busca regresar al estado inicial.

Búsqueda hacia adelante

• Método guiado por datos que utiliza información para descubrir nuevos estados.
• Un ejemplo incluye:
  • Si se conoce A y A implica B, se busca el estado B desde A.
• Problemas potenciales:
  • No siempre se garantiza que el camino encontrado sea el más corto.
  • Alto consumo de memoria y lentitud si se busca en profundidades grandes.
  • Aunque puede encontrar soluciones óptimas, es inflexible ante el conocimiento del problema.

Búsqueda en profundidad

• Prioriza la expansión de nodos más profundos en el grafo de búsqueda.
• Genera soluciones a partir de nodos hijos seleccionados tras cada expansión.
• Se continúa explorando hacia abajo hasta que se encuentra un bloqueo.
• Un nodo es considerado prometedor si su valor de evaluación es menor.

Ejemplo de evaluación de nodos

• Proceso de evaluación de nodos muestra cómo se seleccionan y expanden:
  • ABTOS representa los nodos a expandir en cada ronda.
  • CDOS representa los nodos ya evaluados.
• Un valor menor en la función de evaluación indica mayor promesa en el nodo.

Heurísticas y el problema del "Puzle 8"

• Se utiliza el "Puzle 8" para ilustrar heurísticas no admisibles.
• Heurísticos comunes a considerar:
  • h1(n): número de fichas mal colocadas.
  • h2(n): distancia Manhattan.
  • h3(n): combinación de la distancia Manhattan y una penalización por secuencia incorrecta de piezas.

En este cuestionario, exploraremos el concepto de búsqueda heurística y cómo se aplica en problemas como el Puzle 8. Aprenderás a decidir qué nodos deben ser descartados o podados para mejorar la eficiencia de la búsqueda, así como la importancia de seleccionar el heurístico adecuado. ¡Pon a prueba tus conocimientos sobre este tema fascinante!