Le chemin du moindre coût

Question posée au contrôle continu du 15 juin 1998 1997

Un concurrent d'un cross-country doit traverser un terrain difficile du point A au point B. Avant la course, il veut choisir le chemin à suivre. Il a une carte du terrain:

La légende montre les types de terrains, et un nombre associé à chaque type qui indique la difficulté de sa traversée. D'une case de la carte on ne peut accéder qu'à ses quatre voisines au nord, au sud, à l'est et à l'ouest (le déplacement en diagonale est interdit).

Le concurrent est équipé d'un ordinateur, dans lequel la carte peut être stockée. On vous a demandé de participer à l'écriture d'un programme qui lui permette de trouver le meilleur chemin dans cette situation, c'est-à-dire le chemin du moindre coût.

3.a)

Comment représenteriez-vous l'ensemble des données fournies par la carte en utilisant un graphe? (Donnez juste une courte explication - ne dessinez pas le graphe entier.)

3.b)

Quelle(s) structure(s) de données serait la(les) plus efficace(s) pour stocker les noeuds et arcs d'un tel graphe? Ecrivez les déclarations Pascal qui définissent la(les) structure(s) que vous proposez.

3.c)

Quel algorithme de recherche utiliseriez-vous pour trouver le chemin le moins coûteux entre les points A et B? Justifier votre réponse, en considérant d'autres algorithmes possibles.

3.d)

Ecrivez une description précise, en pseudo-code, de l'algorithme de recherche choisi.

Site Hosting: Bronco