Skip to content

Le sac de bonbons


Après une présentation succincte de la notion de graphe et du rappel du vocabulaire de base : sommets, arêtes, arcs, chemins, on lance l'activité.

Etape 1 : Prendre connaissance du problème (5')

Voici un sac de bonbons. Et huit élèves A, B, C, D, E, F, G et H. C'est A qui a le sac de bonbon et ille va le transmettre à H en passant par les autres, mais voilà ce sont des gourmands et illes ne sont pas tous reliés les uns aux autres

  • A est relié à B et D et veut donner le paquet de bonbons à G
  • B est relié à A, D, E, C et mange 4 bonbons au passage
  • C est relié à B, E et G et mange 3 bonbons au passage
  • D est relié à A, B et E et mange 2 bonbons au passage
  • E est relié à B, C, D, F et mange 1 bonbon au passage
  • F est relié à E et G et mange 2 bonbons au passage
  • G est relié à C et F et veur recevoir le paquet de bonbon

du coup comment transmettre le paquet de bonbons pour en perdre un minimum ?

Etape 2 : Modéliser le problème sur papier, en binôme (15')

Faire un diagramme qui représente le problème, comparer entre les binomes les diagrammes et retenir celui qui est le plus pratique à utiliser.

Ajouter sur ce diagramme des flèches avec le coût pour passer le paquet de bonbons d'une personne à une autre.

Regarder sur wikipédia la page https://fr.wikipedia.org/wiki/Liste_des_algorithmes_de_la_théorie_des_graphes les algorithmes possibles et voir quel algorithme permettrait de résoudre le problème posé.

Notes pour le prof :

  • il y a une subtilité ici les "poids" sont portés par les sommets et non les arcs, il faut en faire des flèches pour leur mettre un poids, tout ça est intentionnel pour bien faire comprendre toutes ces nuances. Il y aussi des flèches avec des 0.
  • il faut cacher la suite pour ne pas spoiler la réponse à la dernière question, c'est vrai dans la suite où les questions doivent être données une à une.

Etape 3 : Entrer le graphe en machine (15')

Créer un tableau à deux dimensions qui encode le nombre de bonbons consommés à chaque passage d'une personne à une autre :

  • Quelle est la taille horizontale et verticale du tableau ? Quoi mettre dans les cases ?
  • Il y a des cases vides : à quoi correspondent-elles ?
  • Vaut-il mieux mettre la valeur 0 ou 100 dans ces cases pour faire signifier cette absence de valeur ?

À ce stade on définit juste un tableau python, sans le manipuler.

Etape 4 : Résoudre le problème à la main sur papier (15')

Individuellement, en s'entraidant en binôme, rechercher manuellement la meilleure solution, sur le diagramme.

Pour ce faire, prendre un stylo de couleur et ajouter à partir de A sur toutes les flèches le coût en bonbon de passer par cette flèche.

Il y a plusieurs solutions, il y a même des solutions sans fin si on boucle ! Que faire pour ne pas explorer des solutions inutiles ?

Essayer ensuite de formaliser la méthode pour qu'une autre personne bénéficie de votre expertise.

Etape 5 : Résoudre le problème par programmation, en binôme (45')

Regarder sur la page wikipédia https://fr.wikipedia.org/wiki/Liste_des_algorithmes_de_la_théorie_des_graphes On pourra prendre l'algorithme de Bellman-Ford "en place" qui semble le plus facile à implémenter, mais les élèves peuvent se lancer le défi d'implémenter celui de Dijkstra ou de Floyd-Warshall, à la place.

Voici quelques indications:

  • partir du tableau défini précédemment et créer (selon l'algorithme choisi) un tableau de distances
  • traduire en python l'algorithme donné dans sa version "en place" et
  • à chaque étape afficher les résultats intermédiaires pour vérifier et suivre ce qui se passe

Lancer et observer. On obtient un tableau de distances : comment en déduire le chemin ?

Etape 6 : Expérimenter avec des vrais bonbons (15')

Choisir 8 personnes, les installer pour reproduire la situation, utiliser des postits pour noter la lettre et la consommation de bonbons.

Lancer l'activité et vérifier que ça marche.

Etape 7 : Manger les bonbons :)