Exercice 3 - Partie B · Bac Numérique et Sciences Informatiques Métropole 2024 (sujet 2)

EXERCICE 3 (8 points)

Cet exercice porte sur la programmation orientée objet, les graphes et utilise la structure de données dictionnaire.

La direction de la station de ski Le Lièvre Blanc, spécialisée dans la pratique du ski de fond, souhaite disposer d'un logiciel lui permettant de gérer au mieux son domaine skiable. Elle confie à un développeur informatique la mission de concevoir ce logiciel. Celui-ci décide de caractériser les pistes de ski à l'aide d'une classe Piste et le domaine de ski par une classe Domaine.

Le code Python de ces deux classes est donné en Annexe.

Partie B – Recherche par force brute

Le plan des pistes du domaine Le Lièvre Blanc peut être représenté par le graphe suivant:

Sur chaque arête, on a indiqué le nom de la piste et sa longueur en kilomètres. Les sommets correspondent à des postes de secours.

Un pisteur-secouriste de permanence au point de secours D est appelé pour une intervention en urgence au point de secours A. La motoneige de la station étant en panne, il ne peut s'y rendre qu'en skis de fond. Il décide de minimiser la distance parcourue et cherche à savoir quel est le meilleur parcours possible. Pour l'aider à répondre à ce problème, on décide d'implémenter le graphe ci-dessus grâce au dictionnaire de dictionnaires suivant:

domaine = {'A': {'G': 7.5, 'H': 6.8},

'B': {'C': 3.0, 'D': 9.2, 'E': 1.8, 'F': 4.6},

'C': {'B': 3.0, 'D': 2.5, 'E': 6.1, 'G': 10.7},

'D': {'B': 9.2, 'C': 2.5},

'E': {'B': 1.8, 'C': 6.1, 'F': 10.1, 'G': 12.7},

'F': {'B': 4.6, 'E': 10.1, 'G': 2.6, 'H': 3.4},

'G': {'A': 7.5, 'C': 10.7, 'E': 12.7, 'F': 2.6,

'H': 5.5},

'H': {'A': 6.8, 'F': 3.4, 'G': 5.5} }

7.

Écrire une instruction Python permettant d'afficher la longueur de la piste allant du sommet 'E' au sommet 'F'.

8.

Écrire une fonction voisins qui prend en paramètres un graphe G et un sommet s du graphe G et qui renvoie la liste des voisins du sommet s.

Exemple: l'instruction voisins(domaine, 'B') renvoie la liste ['C', 'D', 'E', 'F'].

9.

Recopier et compléter la fonction longueur_chemin donnée ci-dessous: cette fonction prend en paramètres un graphe G et un chemin du graphe G sous la forme d'une liste de sommets et renvoie sa longueur en kilomètres.

Exemple: l'instruction longueur_chemin(domaine, ['B', 'E', 'F', 'H']) renvoie le nombre flottant 15.3.

1 def longueur_chemin(G, chemin):

2 precedent =...

3 longueur = 0

4 for i in range(1, len(chemin)):

5 longueur = longueur +...

6 precedent =...

7 return...

On donne ci-dessous une fonction parcours qui renvoie la liste de tous les chemins du graphe G partant du sommet depart et parcourant les sommets de façon unique, c'est-à-dire qu'un sommet est atteint au plus une fois dans un chemin.

Par exemple, l'appel parcours(domaine, 'A') renvoie la liste de tous les chemins partant du sommet A dans le graphe domaine sans se soucier ni de la longueur du chemin, ni du sommet d'arrivée. Ainsi, ['A', 'G', 'C'] est un chemin possible, tout comme ['A', 'G', 'C', 'B', 'E', 'F', 'H'].

1 def parcours(G, depart, chemin = [], lst_chemins = []):

2 if chemin == []:

3 chemin = [depart]

4 for sommet in voisins(G, depart):

5 if sommet not in chemin:

6 lst_chemins.append(chemin + [sommet])

7 parcours(G, sommet, chemin + [sommet])

8 return lst_chemins

10.

Expliquer en quoi la fonction parcours est une fonction récursive.

Un appel à la fonction parcours précédente renvoie une liste de chemins dans laquelle figurent des doublons.

11.

Recopier et compléter la fonction parcours_dep_arr ci-après qui renvoie la liste des chemins partant du sommet depart et se terminant par le sommet arrivee dans le graphe G entrés en paramètres. La liste renvoyée ne doit pas comporter de doublons. Attention, plusieurs lignes de code sont nécessaires.

1 def parcours_dep_arr(G, depart, arrivee):

2 liste = parcours(G, depart)

3...

12.

Recopier et compléter la fonction plus_court donnée ci-dessous. La fonction plus_court prend pour paramètres un graphe G, un sommet de départ depart et un sommet d'arrivée arrivee; elle renvoie un des chemins les plus courts sous la forme d'une liste de sommets.

1 def plus_court(G, depart, arrivee):

2 liste_chemins = parcours_dep_arr(G, depart, arrivee)

3 chemin_plus_court =...

4 minimum = longueur_chemin(G, chemin_plus_court)

5 for chemin in liste_chemins:

6 longueur = longueur_chemin(G, chemin)

7 if...:

8 minimum =...

9 chemin_plus_court =...

10 return chemin_plus_court

13.

Expliquer en quoi le choix fait par le pisteur-secouriste de choisir la distance minimale pour arriver le plus rapidement possible sur le lieu de l'incident est discutable. Proposer un meilleur critère de choix.