Ejemplo en cartografía

Para estudiar los distintos algoritmos, vamos a interesarnos en un pequeño juego en el que controlamos a un personaje que representa un explorador. Como en muchos juegos de rol, nuestro héroe está limitado en cada turno (no tiene derecho más que a cierto número de puntos de acción). Para ir lo más rápido posible desde un punto a otro, buscaremos la ruta más corta en el mapa, teniendo en cuenta el tipo de terreno.

Existen varias formas, que requieren más o menos energía (y por consiguiente, puntos de acción):

  • Caminos, que requieren un punto de acción por casilla.

  • Hierba, que requiere dos puntos de acción.

  • Puentes, que requieren dos puntos de acción.

  • Agua, infranqueable.

  • Árboles, infranqueables también.

El mapa es el siguiente:

images/c03f08.PNG

Y la leyenda:

images/c03f09.PNG

Vamos a buscar la ruta que permita ir desde el punto de partida (P) hasta el destino (D), utilizando la menor cantidad posible de puntos de acción. La ruta más corta cuesta 27 puntos de acción (siguiendo la ruta y pasando el primer puente; a continuación, acortando por hierba hasta el final).

Si desea saber más, le proponemos el siguiente libro:
couv_DPT2INT.png
60-signet.svg
Versión impresa
20-ecran_lettre.svg
Versión online
41-logo_abonnement.svg
En ilimitado con la suscripción ENI
130-boutique.svg
En la tienda oficial de ENI
Anterior
Rutas y grafos
Siguiente
Algoritmos exhaustivos de búsqueda de rutas