Les graphes et la recherche de chemins — Informatique, 14–17 ans
Un graphe représente des éléments et les liens entre eux. Une fois le problème dessiné ainsi, un ordinateur peut explorer des itinéraires, des connexions ou des dépendances sans traiter chaque situation comme un cas particulier.
Des éléments et des liens
Dans un graphe, un sommet représente un élément et une arête représente une relation ou un trajet entre des éléments. Les villes peuvent être des sommets et les routes des arêtes ; les personnes, des sommets et les amitiés, des arêtes. Les arêtes peuvent avoir une direction ou un poids, comme une rue à sens unique ou une distance.
Pourquoi dessiner un graphe ?
Beaucoup de problèmes réels concernent des connexions : livrer des colis, acheminer des messages, suggérer des amis ou ordonner des tâches avec des prérequis. Des listes de faits isolés cachent ces liens. Les graphes donnent à l'ordinateur une forme commune pour les routes, les sites web ou les dépendances.
Choisir le trajet le plus court
Supposons que A est relié à B par 4 km, à C par 1 km, que C est relié à B par 2 km et B à D par 3 km. De A à B, le trajet direct fait 4 km, mais A–C–B fait 1 + 2 = 3 km : il est donc plus court. De A à D par C et B, le total est 1 + 2 + 3 = 6 km.
Le moins d'étapes n'est pas toujours le plus court
Il est naturel de compter seulement le nombre de liens : deux routes semblent préférables à trois. Mais les liens peuvent avoir des longueurs, des retards ou des prix très différents. Trois arêtes de 1 km peuvent être meilleures que deux de 10 km ; le graphe doit donc mesurer ce qui compte vraiment.
Les graphes hors de la classe
Les applications de navigation utilisent des graphes routiers avec distances et temps de circulation. Les réseaux sociaux utilisent des graphes de comptes et de relations, tandis qu'un moteur de recherche suit les liens entre pages. Le résultat dépend de ce qui compte comme connexion et du poids choisi : distance, temps, coût ou pertinence.
Continue d'explorer
Autres langues
Chargement de MyLeoNes™…