Categorías
Informática Universitario Videojuego

Ejercicios

Estos son algunos ejercicios que pueden realizarse para practicar lo aprendido en el tema de Navegación, sobre algoritmos de búsqueda en el espacio de estados, tanto con estrategias informadas como no informadas.

  1. Se puede representar un grafo pesado y dirigido como un conjunto de nodos y conexiones, donde además se puede reflejar el sentido de cada conexión y hasta el peso asignado a la misma.
    Dibuja los diagramas correspondientes a estos grafos:
    nodos = {A, B, C, D}
    conexiones = {(A, B): 4, (B, A): 4, (A, D): 5, (D, A): 5, (B, D): 6, (D, B): 6, (B, C): 5, (C, B): 5}
    nodos = {S, A, B, C, D, G}
    conexiones = {(S, A): 6, (S, B): 15, (A, C): 6, (A, D): 12, (B, D): 3, (B, G): 15, (D, C): 9, (D, G): 6}
  2. Las mallas de navegación pueden tener los nodos ubicados en los vértices de los polígonos, o en las aristas de dichos polígonos. 
    Considera el siguiente diagrama (Figura 1), ignora los nodos y las líneas continuas de conexión entre ellos y dibuja una nueva malla de navegación donde los nodos estén en el centro de las aristas de los polígonos y las conexiones sean como corresponda.
  3. La distancia Manhattan en un grafo de baldosas de dimensiones X y Z se define como:
    distancia(origen, destino)= |origenX – destinoX| + |origenZ – destinoZ|
    Explica por qué en algunos juegos suele ser mejor usar esta distancia en lugar de la euclídea.
  4. Escribe el pseudocódigo del algoritmo de Dijkstra en su versión para encontrar el camino de coste mínimo únicamente entre dos puntos.
  5. En el segundo grafo del Ejercicio 3, asume que S es el nodo origen y G el nodo destino. Asume también que hemos usado el algoritmo de Dijkstra para encontrar el camino de coste mínimo entre S y G y que queremos dejar anotado en la siguiente tabla el contenido de la lista abierta justo al terminar cada uno de los pasos del while (numerados por filas) que da el algoritmo. 
    Completa las filas que faltan en la siguiente tabla, en el formato Coste: Nodo ← NodoPadre, siempre ordenado por coste.
    Explica si se debe parar o no al visitar el nodo destino por primera vez, y por qué razón hacerlo.
  6. Podemos especificar el valor de la función heurística para cada nodo, añadiéndolo a su nombre así: A: 5.
    Dibuja otra vez los diagramas correspondientes a los grafos del Ejercicio 1, teniendo en cuenta esta heurística definida:
    nodos = {A: 5, B: 3, C: 2, D: 4}
    nodos = {S: 2, A: 6, B: 9, C: 3, D: 3, G: 0}
  7. Escribe el pseudocódigo del algoritmo A* y señala cuales son las diferencias con el algoritmo de Dijkstra en su versión para encontrar el camino de coste mínimo entre dos puntos.
  8. Asume que hemos usado el algoritmo de A* para encontrar el camino de coste mínimo entre S y G del segundo grafo del ejercicio anterior, y que queremos dejar anotado en la siguiente tabla el contenido de la lista abierta justo al terminar cada uno de los pasos del while (numerados por filas) que da el algoritmo. 
    Completa las filas que faltan en la siguiente tabla, en el formato Coste: Nodo ← NodoPadre, siempre ordenado por coste.
  9. Para el mismo grafo del ejercicio anterior, ¿cuál es el máximo valor que podría dar la función heurística en D antes de empezar ya a sobreestimar el coste real?
  10. Una heurística se considera consistente si tiene la propiedad de que para cada nodo A, el coste estimado de alcanzar el destino desde A nunca es mayor que el coste real de llegar desde A a cualquier nodo hijo B más el coste estimado de alcanzar el destino desde B:
    h(A) coste (A, B) + h(B)
    Indica si las heurísticas definidas en el Ejercicio 6 son consistentes.
  11. Explica por qué razón, si una heurística es consistente, sería posible ahorrarse el uso de la lista cerrada en la implementación del algoritmo A*.
    Indica además cómo podrías transformar una heurística admisible en una consistente.
Figura 1: Diagrama de la malla de navegación de un escenario.
00: S
16: A ← S, 15: B ←S
2
3
4
5
6
Tabla 1: Contenido de la lista abierta del algoritmo de Dijkstra al terminar cada iteración del bucle while.
02: S
112: A ← S, 24: B ← S
2
3
4
5
Tabla 2: Contenido de la lista abierta del algoritmo A* al terminar cada iteración del bucle while.

Esta página está licenciada bajo CC BY-NC-SA 4.0 por Laboratorios Narratech.