Un voyageur de commerce doit visiter plusieurs villes en passant une seule fois par chacune d'entre elles puis en revenant à son point de départ. Son problème est de trouver le chemin le plus court.
1) Avec 3 villes ABC, combien y-a-t-il de chemins possibles en partant de A ?
2) Avec 4 villes ABCD,
a) combien y-a-t-il de chemins possibles en partant de A ? .
b) On suppose que les trajets s'effectuent tous en ligne droite. Parmi les possibilités trouvées, justifiez pourquoi les parcours non croisés sont meilleurs que les croisés.
c) On suppose que les trajets choisis ne sont pas forcément droits mais sont à chaque fois les plus courts entre deux villes et peuvent être effectués dans les deux sens. Pouvez-vous justifier pourquoi les parcours non croisés sont toujours parmi les plus intéressants.
3) On suppose maintenant un nombre de villes quelconque. Peut-on affirmer que la meilleure solution est forcément non croisée ?
4)
a) Prenons un problème simple avec 5 villes en partant de l'une d'elles.
Pouvez-vous compléter le raisonnement suivant :A la première étape, nous avons le choix entre ..... destinations différentes.
A la deuxième étape, nous avons encore .... possibilités de déplacements vers une ville non visitée.
...
Pour finir, il nous reste une seule possibilité, revenir à la ville de départ..
Au total nous avons .................................. trajets possibles.
b) En reprenant le raisonnement mené à l'étape précédente, pouvez-vous nous donner le nombre de trajets possibles pour 12 villes. Quel temps sera-t-il nécessaire pour qu'un ordinateur explore toutes ces possibilités en analysant 1000 trajets par seconde ?
5) Voici un tableau donnant les distances entre 7 villes de France.
| Bordeaux | Bourges | Dijon | Limoges | Marseille | Nancy | Rennes | |
| Bordeaux | 0 | 395 | 638 | 223 | 650 | 835 | 439 |
| Bourges | 395 | 0 | 235 | 192 | 600 | 399 | 375 |
| Dijon | 638 | 235 | 0 | 420 | 505 | 210 | 610 |
| Limoges | 223 | 192 | 420 | 0 | 636 | 630 | 372 |
| Marseille | 650 | 600 | 505 | 636 | 0 | 720 | 1070 |
| Nancy | 835 | 399 | 210 | 630 | 720 | 0 | 637 |
| Rennes | 439 | 375 | 610 | 372 | 1070 | 0 |
a) Placez ces villes sur une carte.b) Recherchez le meilleur parcours possible. Pour cela, utilisez le tableau Excel fourni qu'il vous suffira de compléter.
6) Ce qui précède vous a permis de remarquer que la technique consistant à analyser toutes les possibilités conduit vite à des calcul impossibles à réaliser à l'échelle humaine. Afin de trouver tout de même des solutions, les chercheurs ont inventé différentes techniques permettant d'accélérer la recherche. Parmi les plus efficaces, nous trouvons celle de « l'algorithme génétique » et celle de « la colonie de fourmis ». En recherchant sur Internet, pourriez-vous nous donner une explication succincte d'une de ces deux méthodes.
|
|
| Jean-Luc Juveneton : Ingénierie Educative - CRDP - Grenoble (38) / imel@ac-grenoble.fr / 12 avril 2005 |
