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)= |origen_X – destino_X| + |origen_Z – destino_Z|
   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 Tabla 1 el contenido de la lista abierta para todos los pasos (numerados por filas) que da el algoritmo. 
   Completa las filas de la tabla que faltan, y 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: 0, 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 Tabla 2 el contenido de la lista abierta para todos los pasos (numerados por filas) que da el algoritmo. 
   Completa las filas de la tabla que faltan.
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, entonces en realidad no necesitas usar la lista cerrada del algoritmo A*.
    Indica además cómo podrías transformar una heurística admisible en una consistente.

1	0: S
2	6: A ← S, 15: B ←S
3
4
5
6
7

1	0: S
2	12: A ← S, 24: B ←S
3
4
5
6
7