.. index:: facteur chinois .. _l-algo_facteur_chinois: La tournée du camion poubelle ============================= A partir de 7-8 ans (mais ce n'est qu'une indication). Un camion poubelle doit passer dans toutes les rues d'une ville pour récolter tous les déchets. Il va avoir un petit peu d'aide car il ne sait pas comment faire pour trouver le chemin le plus court passant par toutes les rues. Mise en scène ------------- On part de la carte de votre ville. Avec un feutre, on encercle la zone dans laquelle le camion poubelle devra traverser toutes les rues. On recouvre la carte de papier calque. Avec un feutre d'une autre couleur, on surligne les rues par lesquelles le camion poubelle passe et on numérote le rues dans l'ordre dans lequel on les parcourt. Quelques dessins de difficulté croissantes : .. image:: images/touquet2.png Un peu plus dur : .. image:: images/touquet3.png Toujours un peu plus dur : .. image:: images/touquet.png Quelques indices : **Q1 :** Le point de départ importe-t-il peu ? **Q2 :** Avez-vous lu cette histoire sur les `sept ponts de Königsberg `_ ? Il est possible qu'elle ait un lien avec l'histoire du camion poubelle. **Q3 :** Maintenant que vous avez bien planché sur ces grands dessins, que diriez-vous de ces deux petits dessins ? Existe-t-il un moyen de parcourir ces deux petits réseaux de rues en ne passant qu'une seule fois par chaque rue ? Car si cela était possible, nous serions sûr alors d'avoir trouvé le chemin le plus court... .. image:: images/maison.png .. image:: images/maison_double.png Un problème simple avec la `ville de Seattle `_. Les villes en quadrillage sont un peu plus faciles. Solution -------- Voir :ref:`l-algo_facteur_chinois_sol`. A quoi ça sert ? ---------------- Le camion poubelle est un exemple d'utilisation. La tournée d'un homme politique pour visiter ses concitoyens en est un autre. Imaginer que vous deviez construire un labyrinthe avec un unique rouleau de carton selon un schéma déterminé à l'avance. Il vous faudra bien sûr découper et la réponse à la question 2 vous permettra de découper le moins possible.