50 clés pour comprendre les maths
186
est toujours supérieure à la longueur du troisième côté ; dans ce cas, le graphe est dit
euclidien et les méthodes de résolution sont bien connues. C’est différent lorsqu’il
s’agit de temps. Emprunter les voies aériennes principales est souvent plus rapide
que de prendre les voies secondaires et James Cook remarque qu’en allant d’El Paso
à Chicago, il est plus rapide de passer par Dallas. Ce que l’on appelle l’inégalité du
triangle ne s’applique pas ici.
La méthode gloutonne appliquée au problème du temps donne 22 heures sur le
trajet BCDEAB, alors que deux trajets optimaux différents BCADEB et BCDAEB totalisent 14 heures chacun. Le premier est de 6 618 km et le second de 5 482. James
Cook se réjouit d’avoir réalisé la plus grande économie en choisissant BCDAEB. Il
projette ensuite de réfléchir au trajet le moins onéreux.
Des secondes aux siècles La vraie difficulté que ce problème du voyageur
de commerce soulève apparaît lorsqu’il y a un très grand nombre de villes. James
Cook est tellement brillant qu’il ne tarde pas à être promu au poste de directeur. Il
doit maintenant visiter 13 villes à partir de Bismarck au lieu des 4 villes précédentes.
La méthode gloutonne ne lui plaît pas, et il préfère étudier une liste complète des
itinéraires possibles. Il entreprend d’en dresser la liste pour ses 13 villes. Il découvre
bientôt qu’il n’y aurait pas moins de 3,1 × 10
9 itinéraires à étudier. En d’autres
termes, s’il fallait une seconde pour qu’un ordinateur imprime un itinéraire, il lui
faudrait un siècle pour les imprimer tous. Un problème comportant 100 villes occuperait l’ordinateur pendant des milliers d’années.
On a appliqué certaines méthodes sophistiquées au problème du voyageur de
commerce. Des méthodes exactes ont été données qui s’appliquent à 5 000 villes
ou moins, et l’une d’elles a même permis de traiter un problème particulier de
33 810 villes, en ayant toutefois recours à un ordinateur d’une puissance colossale.
Des méthodes inexactes produisent des itinéraires proches de la solution optimale
avec une probabilité donnée. Les méthodes de ce type ont l’avantage de permettre
de traiter des problèmes concernant des millions de villes.
Complexité algorithmique En nous plaçant du point de vue de l’ordinateur, pensons simplement au temps qu’il lui faudrait pour trouver une solution.
Dresser simplement la liste de tous les trajets possibles est le pire scénario. James a
découvert qu’avec cette méthode musclée, il faudrait presque un siècle pour 13 villes.
Si l’on ajoutait deux villes supplémentaires, on passerait alors à 20 000 ans !
Ces estimations dépendent bien sûr de l’ordinateur utilisé, mais pour n villes, le
temps nécessaire augmente proportionnellement à n! (nombre obtenu en multipliant tous les nombres entiers de 1 à n). On a calculé 3,1 × 10
9 itinéraires pour
13 villes. Déterminer pour chaque itinéraire s’il est le plus court devient un problème de temps factoriel… dont la résolution prend du temps.
D’autres méthodes peuvent être utilisées pour résoudre le problème dans lequel le
temps pour n villes augmente proportionnellement à 2
n (2 multiplié par lui-même
n fois) ; pour 13 villes cela impliquerait donc quelque chose de l’ordre de 8 192
186
est toujours supérieure à la longueur du troisième côté ; dans ce cas, le graphe est dit
euclidien et les méthodes de résolution sont bien connues. C’est différent lorsqu’il
s’agit de temps. Emprunter les voies aériennes principales est souvent plus rapide
que de prendre les voies secondaires et James Cook remarque qu’en allant d’El Paso
à Chicago, il est plus rapide de passer par Dallas. Ce que l’on appelle l’inégalité du
triangle ne s’applique pas ici.
La méthode gloutonne appliquée au problème du temps donne 22 heures sur le
trajet BCDEAB, alors que deux trajets optimaux différents BCADEB et BCDAEB totalisent 14 heures chacun. Le premier est de 6 618 km et le second de 5 482. James
Cook se réjouit d’avoir réalisé la plus grande économie en choisissant BCDAEB. Il
projette ensuite de réfléchir au trajet le moins onéreux.
Des secondes aux siècles La vraie difficulté que ce problème du voyageur
de commerce soulève apparaît lorsqu’il y a un très grand nombre de villes. James
Cook est tellement brillant qu’il ne tarde pas à être promu au poste de directeur. Il
doit maintenant visiter 13 villes à partir de Bismarck au lieu des 4 villes précédentes.
La méthode gloutonne ne lui plaît pas, et il préfère étudier une liste complète des
itinéraires possibles. Il entreprend d’en dresser la liste pour ses 13 villes. Il découvre
bientôt qu’il n’y aurait pas moins de 3,1 × 10
9 itinéraires à étudier. En d’autres
termes, s’il fallait une seconde pour qu’un ordinateur imprime un itinéraire, il lui
faudrait un siècle pour les imprimer tous. Un problème comportant 100 villes occuperait l’ordinateur pendant des milliers d’années.
On a appliqué certaines méthodes sophistiquées au problème du voyageur de
commerce. Des méthodes exactes ont été données qui s’appliquent à 5 000 villes
ou moins, et l’une d’elles a même permis de traiter un problème particulier de
33 810 villes, en ayant toutefois recours à un ordinateur d’une puissance colossale.
Des méthodes inexactes produisent des itinéraires proches de la solution optimale
avec une probabilité donnée. Les méthodes de ce type ont l’avantage de permettre
de traiter des problèmes concernant des millions de villes.
Complexité algorithmique En nous plaçant du point de vue de l’ordinateur, pensons simplement au temps qu’il lui faudrait pour trouver une solution.
Dresser simplement la liste de tous les trajets possibles est le pire scénario. James a
découvert qu’avec cette méthode musclée, il faudrait presque un siècle pour 13 villes.
Si l’on ajoutait deux villes supplémentaires, on passerait alors à 20 000 ans !
Ces estimations dépendent bien sûr de l’ordinateur utilisé, mais pour n villes, le
temps nécessaire augmente proportionnellement à n! (nombre obtenu en multipliant tous les nombres entiers de 1 à n). On a calculé 3,1 × 10
9 itinéraires pour
13 villes. Déterminer pour chaque itinéraire s’il est le plus court devient un problème de temps factoriel… dont la résolution prend du temps.
D’autres méthodes peuvent être utilisées pour résoudre le problème dans lequel le
temps pour n villes augmente proportionnellement à 2
n (2 multiplié par lui-même
n fois) ; pour 13 villes cela impliquerait donc quelque chose de l’ordre de 8 192