Resolucion - T9
15 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

¿Cuál de los siguientes heurísticos es considerado no admisible?

  • h2(n)
  • h1(n)
  • h4(n)
  • h3(n) (correct)

    • En el contexto de juegos de dos jugadores, ¿cuál es un enfoque común utilizado para determinar la estrategia ganadora?

  • Estrategia mixta
  • Búsqueda minimax (correct)
  • Búsqueda aleatoria
  • Búsqueda exhaustiva

    • La distancia Manhattan es un tipo específico de heurístico que se aplica en qué tipo de problemas?

  • Juegos de azar
  • Puzzles de deslizamiento (correct)
  • Problemas de programación lineal
  • Problemas de búsqueda en grafos

    • ¿Cuál es un criterio para evaluar la efectividad de un heurístico en IA?

    <p>Si es admisible o no</p> 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?

    <p>Exploran el espacio de estados sin información adicional</p> Signup and view all the answers

    ¿Qué algoritmo utiliza Bing Maps de Microsoft para el enrutamiento en redes de carreteras?

    <p>CRP</p> Signup and view all the answers

    ¿Qué motor de planificación de rutas utiliza datos de OpenStreetMap?

    <p>OSRM</p> 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?

    <p>Transfer Patterns</p> Signup and view all the answers

    ¿Qué algoritmo actualmente está utilizando OpenTripPlanner?

    <p>RAPTOR</p> Signup and view all the answers

    ¿Qué característica de búsqueda es utilizada por Google Maps y servicios VTC como Uber?

    <p>Planificación de rutas en tiempo real</p> Signup and view all the answers

    ¿Cuál de los heurísticos mencionados se basa en el número de fichas mal colocadas?

    <p>h1(n) = número de fichas mal colocadas</p> Signup and view all the answers

    ¿Qué representa S(n) en los heurísticos presentados?

    <p>La cuenta de secuencia de fichas</p> Signup and view all the answers

    ¿Qué cálculo se realiza en h3(n) según la descripción dada?

    <p>La distancia Manhattan más tres veces la cuenta de secuencia</p> 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)?

    <p>El conteo de fichas desordenadas</p> Signup and view all the answers

    ¿Cuál de los siguientes heurísticos podría considerarse más complejo debido a su cálculo?

    <p>h3(n) = h2(n) + 3·S(n)</p> 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.

    Quiz Team

    Related Documents

    9 TIA Resolucion.pdf
    9 TIA Resolucion.pdf
    9 TIA Resolucion.pdf

    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!

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser