Ressource
  Initiation aux algorithmes . Activité débranchée . Collège . Lycée . Activité . .

Plus court chemin

 

Objectif : Ce problème permet d’introduire la notion de complexité pour classer les problèmes, et la recherche de solution optimale ou approchée.

 

Résumé : Comment trouver le chemin le plus court possible ? Ce problème d’optimisation aux applications innombrables nous permet d’introduire la notion de complexité pour classer les problèmes, et la recherche de solution optimale ou approchée.

Déroulé de l’activité : Sur une planche à clous, on fait passer un fil une fois et une seule par chaque clou avant de revenir au point de départ. Comment trouver le chemin le plus court possible ? Ce problème d’optimisation aux applications innombrables nous permet d’introduire la notion de complexité pour classer les problèmes, et la recherche de solution optimale ou approchée.

Il faut bien distinguer ce problème dit du voyageur de commerce dont la complexité explose avec la taille du problème et celle du plus court chemin dont la complexité augmente de manière seulement polynomiale.

Pour  fabriquer vous-même un kit, voici quelques fichiers qui pourront vous aider https://github.com/InfoSansOrdi/planches-a-clous

En savoir plus : http://interstices.info/voyageur-commerce http://interstices.info/plus-court-chemin

On peut utiliser des ressources complémentaires

 

Élément de la boite d’activités débranchées de NyBi.cc, réalisé avec le support de Cap’maths.

Dernière modification : juin 2016.
Partager:
    show post QRcode

    Vous pourriez aussi être intéressé-e-s par :
    …/…