|
||||||||||||||||||||||||||||||||||||||||
|
COMPTER les TRAJETS Compter les itinéraires Le problème du voyageur de
commerce consiste à minimiser son trajet pour visiter tous ses clients.
Ici, il s'agit de compter tous les trajets possibles pour rejoindre un point
d'arrivée en passant ou non par des points d'étape. |
|
|
||
|
Le parcours du matin De bon
matin, Madame ou Monsieur quitte la maison pour se rendre au bureau. Selon le
jour, il faut aller déposer les enfants à l'école, chercher les journaux et éventuellement passer à la poste. Combien
de possibilités d'itinéraires se présentent à eux selon les points de passage
envisagés ? |
|
|
|
Compter les trajets possibles La
personne peut se rendre directement au bureau. Elle peut
passer par seul endroit, par deux ou trois. Le tableau montre les trajets
possibles et leur nombre selon la quantité de points de passage. Une idée pour le dénombrement: avec deux
points d'étapes, par exemple, il y a trois possibilités de choix pour le
premier, puis deux pour l'autre. |
|
|
|
|
||
|
Spécifications du problème
Maths Quantité de trajets = nombre de traits droits qu'il est possible de
tracer d'un point à un autre parmi un ensemble de k points dans le plan
cartésien en ne passant pas plus d'une fois par chaque point. |
Avec un seul point de passage Deux trajets sont possibles:
Points rouges: départ et arrivée; Point orange:
point de passage. |
|
|
Avec deux points de passage
Un total
de 5 trajets possibles. On
constate que le trajet direct est toujours présent, de même que les k
passages par un seul point. Ce qui
veut dire que la formule de dénombrement commence par: |
|
|
|
|
||||
|
Avec trois points de passage:
|
Tableau des trajets pour trois
points de passage
Q = 1x1 + 1x3 + 2x3 + 6x1 Vous avez sans doute reconnu un problème de combinaisons:
choix de k objets parmi n, et l'introduction de leur
calcul. Vous reconnaissez aussi (en rouge), les coefficients du
binôme qui figurent dans le triangle
Pascal. |
|||
|
Avec Quatre points de passage: On vérifie la même logique de construction de la
formule. Et, on montre la formule générale. |
|
|||
|
Formulation
avec factorielles uniquement Le tableau montre la mise en facteur commun de
factorielle 4 qui fait apparaître la somme des
inverses des factorielles. Or celle-ci tend vers la constante e = 2,718…
pour i tendant vers l'infini.
Soit la formule simple suivante:
|
|
|||
|
|
||
|
|
Commentaires Appel aux logiciels de combinatoire. Lancement de la boucle d'analyse des valeurs de k de 1 à 10. Calcul de Q, la somme (add) de i factorielle
multipliée par la quantité de combinaisons et pour i de 0 à k. Calcul du même type pour QQ mais avec la
formule impliquant l'inverse des factorielles. Et, troisième valeur Qe, calcul avec
l'exponentielle. En bleu les résultats. Q et QQ sont logiquement égaux. Qe n'est qu'une approximation de Q. |
|
Voir Programmation – Index
|
Suite |
|
|
Voir |
|
|
DicoNombre |
|
|
Site |
|
|
Cette page |
