Questions and Answers
¿Cuál de los siguientes heurísticos es considerado no admisible?
En el contexto de juegos de dos jugadores, ¿cuál es un enfoque común utilizado para determinar la estrategia ganadora?
La distancia Manhattan es un tipo específico de heurístico que se aplica en qué tipo de problemas?
¿Cuál es un criterio para evaluar la efectividad de un heurístico en IA?
Signup and view all the answers
Dentro de las técnicas de búsqueda en IA, ¿cuál es la característica principal de las búsquedas no informadas?
Signup and view all the answers
¿Qué algoritmo utiliza Bing Maps de Microsoft para el enrutamiento en redes de carreteras?
Signup and view all the answers
¿Qué motor de planificación de rutas utiliza datos de OpenStreetMap?
Signup and view all the answers
¿Cuál de los siguientes algoritmos es utilizado para la planificación de viajes de transporte público en Google Maps?
Signup and view all the answers
¿Qué algoritmo actualmente está utilizando OpenTripPlanner?
Signup and view all the answers
¿Qué característica de búsqueda es utilizada por Google Maps y servicios VTC como Uber?
Signup and view all the answers
¿Cuál de los heurísticos mencionados se basa en el número de fichas mal colocadas?
Signup and view all the answers
¿Qué representa S(n) en los heurísticos presentados?
Signup and view all the answers
¿Qué cálculo se realiza en h3(n) según la descripción dada?
Signup and view all the answers
¿Qué se utiliza para medir cuántas fichas no están en su posición correcta en el heurístico h1(n)?
Signup and view all the answers
¿Cuál de los siguientes heurísticos podría considerarse más complejo debido a su cálculo?
Signup and view all the answers
Study Notes
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.
-
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
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!
