Promenade absolue, ne rater aucune ruelle.

[ccciolll]

Bonjour,

Je ne sais pas le nom de ce que je cherche mais je suis sûr que ça a déjà été pensé et repensé par divers mathématiciens et ce depuis belle lurette. Je crois que ça rentre dans la topologie mais je ne sais même pas ce que signifie topologie ! Honte.

Bref, je sais qu'il existe une méthode logique pour sortir d'un simple labyrinthe en 2D comme ceux des jeux dans les journaux ou dans les foires au manège ou les jardins : toujours tourner à droite (ou à gauche, ça revient au même). C'est pas intuitif ni toujours très rapide, mais l'efficacité est garantie.

Je suis persuadé qu'il existe des méthodes logiques pour s'assurer de visiter chaque ruelle autour d'un point de départ.

Le besoin "réel" est simple : j'emménage dans une maison et je voudrais apprendre à connaître le quartier sans me laisser perturber par mon intuition ou mon désir (ça j'aurais le temps de le faire en famille). Une méthode un peu rigoureuse qui m'assurerait de découvrir un peu à la fois chaque petit chemin existant.

Alors dites moi si une méthode existe ou s'il s'agit d'une quadrature de cercle.
-----

[stefjm]

Bref, je sais qu'il existe une méthode logique pour sortir d'un simple labyrinthe en 2D comme ceux des jeux dans les journaux ou dans les foires au manège ou les jardins : toujours tourner à droite (ou à gauche, ça revient au même). C'est pas intuitif ni toujours très rapide, mais l'efficacité est garantie.

S'il y a un îlot, on va tourner autour indéfiniment.

[Médiat]

Je suis persuadé qu'il existe des méthodes logiques pour s'assurer de visiter chaque ruelle autour d'un point de départ.

Bonjour,

C'est le problème (dual : rue = ville, carrefour = chemin) du voyageur de commerce (90 900 000 références google).

[ccciolll]

S'il y a un îlot, on va tourner autour indéfiniment.

C'est pourquoi je précise un labyrinthe 2D basique, avec l'entrée et la sortie donnant sur le même périmètre extérieur.
Dès qu'on rajoute la possibilité de passer au dessus ou en dessous d'un couloir, ou qu'on place l'entrée ou la sortie à l'intérieur du labyrinthe, cette technique ne fonctionne plus.

Bonjour,

C'est le problème (dual : rue = ville, carrefour = chemin) du voyageur de commerce (90 900 000 références google).

Je croyais que le pb du voyageur de commerce c'était de définir le plus court chemin entre un grand nombre de points. Là c'est un problème différent. Il n'y a pas de volonté à faire le plus court possible entre différents points mais le plus exhaustif possible à partir d'un point central.
Ou alors il y a 2 problèmes nommés "problème du voyageur de commerce". Et alors là quel foutoir (genre : des érudits s'échangent des théories mais en partant d'un énoncé différent portant le même nom, alors ils se disent que l'autre est complètement branque…)

[A voir en vidéo sur Futura]

[invite4ef352d8]

Salut !

le problème si on ne met pas la condition "minimiser la distance parcouru" le problème devient essentiellement bête : prend la liste des rues de ton quartier, un plan et visite les dans un ordres quelconque et tu aura fait toutes les rues !

[Médiat]

Ou alors il y a 2 problèmes nommés "problème du voyageur de commerce". Et alors là quel foutoir (genre : des érudits s'échangent des théories mais en partant d'un énoncé différent portant le même nom, alors ils se disent que l'autre est complètement branque…)

Vous avez oublié de lire l'intérieur des parenthèses.

[ccciolll]

Vous avez oublié de lire l'intérieur des parenthèses.

Je l'avais lu mais sans y prêter attention.

par contre mon cerveau n'arrive pas bien à remplacer les éléments. Pouvez-vous refaire l'explication en plus adapté pour des gens comme moi qui n'ont pas fait des études scientifiques mais artistiques

Mais malgré tout, si on n'essaye pas de minimiser la distance ou la durée, on sort du problème du VRP, non ?

Salut !

le problème si on ne met pas la condition "minimiser la distance parcouru" le problème devient essentiellement bête : prend la liste des rues de ton quartier, un plan et visite les dans un ordres quelconque et tu aura fait toutes les rues !

Oui, bien sûr, mais il se peut que certaines rues ne soient pas indiquées, et puis partir à l'aventure en suivant une règle mathématique ça me paraît une peu grisant (oui, je suis bizarre par moment).

Je me dis que justement, quand aucune carte n'existe, les cartographes qui parcourent les rues doivent bien utiliser une technique pour n'en louper aucune. Enfin peut-être qu'ils ne parcourent pas comme moi je voudrais le faire en touriste.

[Médiat]

Mais malgré tout, si on n'essaye pas de minimiser la distance ou la durée, on sort du problème du VRP, non ?

La première réponse est celle de Ksilver, prenez la liste alphabétique et parcourez dans l'ordre ; mais surtout dans ce que je vous propose, ce qui sera minimisé, ce n'est pas la distance ni la durée, mais les passages aux carrefours.

[ccciolll]

D'accord, je crois que je viens de comprendre la version du PVC (Problème du Voyageur de Commerce) que tu proposes pour répondre à ma question. Comment se pointer dans toutes les rues répertoriées en passant par le moins de carrefours possible. En effet on est alors dans le fameux PVC.
Mais ça n'est pas vraiment mon énoncé de départ. Car pour traiter ma demande via le PVC, il faudrait déjà avoir répertorié toutes les rues, je dirais même toutes les portions de rues (une portion de rue étant alors un segment défini par 2 carrefours). Donc la réponse par le PVC, outre que ce fameux problème est très lourd à résoudre, demanderait en amont un travail de repérage fastidieux qui nécessiterait aussi l'existence d'une cartographie parfaite.
Or si j'ai une cartographie parfaite, je ne vais pas m'embêter. Je prends la carte en question, je ne me pose même pas la question d'un ordre alphabétique qui me ferait faire des détours inutiles. Je me balade et je surligne une rue dès que je l'ai parcourue.

Mais ce n'est pas là ce que je souhaite faire. J'ai pris l'exemple du labyrinthe et ce n'est pas par hasard, c'est parce que je recherche qqchose d'un peu similaire. Un système du genre "toujours prendre la direction la plus à droite et quand on repasse à un endroit déjà parcouru prendre la prochaine à gauche de la plus à droite". Mais je ne suis pas sûr que ce que je viens d'écrire soit vraiment une méthode qui me fasse faire un parcours en colimaçon mais plutôt me dirige dans une direction par petites rotations autour de différents ilots. C'est l'idée qui me vient pour répondre à mon problème, mais c'est une idée intuitive, absolument pas démontrée.
C'est pourquoi je venais poser la question car je suppose que je ne suis pas le premier à me demander comment garantir l'exhaustivité du parcours d'un réseau.
Une méthode de ce type permettrai notamment de parcourir de façon exhaustive un réseau qui ne serait pas cartographié (un marché, une braderie, un salon, un musée, une ville touristique pour laquelle on n'a pas de carte).

[Garf]

Effectivement, peut-être qu'un algorithme de ce genre pourrait fonctionner :
(1) Toujours prendre à gauche, jusqu'à être revenu à son point de départ.
(2) Sur le chemin, répertorier et numéroter tous les carrefours "intéressants" (i.e. point duquel part au moins une route que l'on n'a pas visitée au cours du (1)).
(3) Pour chacun de ces points : prendre la route la plus à gauche (quand on fait face à l'ensemble des routes non visitées) que l'on n'a pas déjà visitée. Continuer en prenant toujours à gauche, jusqu'à être revenu sur une route déjà visitée au cours de l'une des étapes précédentes.
(4) Goto (2)
Après, pour optimiser, c'est une autre histoire...

[KerLannais]

Bonjour,

Il s'agit simplement du parcours d'un graphe, on peut faire un parcours en profondeur ou en largeur comme on veut et on en déduit une forêt couvrante. C'est juste une façon plus pédante de dire ce que Garph a dit

[ccciolll]

Plus pédante et surtout moins accessible aux non-initiés (mais c'est peut-être une des définitions de pédant).
Bon, les balades ce ne sera pas avant août de toutes façons, je crois.
Si je découvre par hasard une méthode pour obtenir le résultat attendu, je viendrai en faire part.
Mais je crois que je vais me contenter de le faire en touriste.

[invite986312212]

bah, tu poses une question, on peut supposer que tu viens ici pour apprendre...

@Kerlannais: ces notions d'exploration en profondeur ou en largeur, je les connais pour les arbres, on peut les étendre à des graphes quelconques?

[KerLannais]

Oui justement, si tu as un graphe non orienté et connexe tu peux le recouvrir par un arbre appelé arbre couvrant, c'est un arbre qui relie tous les sommets du graphe en utilisant que des arètes du graphes (il n'est pas unique). Lorsque le graphe n'est pas connexe on peut recouvrir chaque composante connexe par un arbre on parle alors de forêt couvrante. Je n'ai pas trouvé grand chose à ce sujet sur wiki
http://fr.wikipedia.org/wiki/Arbre_c..._poids_minimal
mais il y a des algorithmes (enfin an tout cas au moins 1) de construction de forêt couvrante.

[invitefa064e43]

au moins 2, même, et tu les a cités : parcours en largeur et parcours en profondeur.

+1 pour ce que tu dis, c'est simplement un algorithme de parcours de graphe qu'il cherche.

[invite986312212]

Oui justement, si tu as un graphe non orienté et connexe tu peux le recouvrir par un arbre appelé arbre couvrant, c'est un arbre qui relie tous les sommets du graphe en utilisant que des arètes du graphes (il n'est pas unique). Lorsque le graphe n'est pas connexe on peut recouvrir chaque composante connexe par un arbre on parle alors de forêt couvrante.

mouais, c'est ce que j'imaginais. Mais alors il me semble que ça n'aide pas beaucoup pour la question pratique du parcours des rues d'une ville dont tu ne possèdes pas le plan. Si on te laisse initialement à un carrefour, tu dois choisir de parcourir telle ou telle rue, mais tu ne connais pas l'arbre couvrant. Il faut le construire au fur et à mesure, c'est peut-être possible, mais je me demande s'il n'y a pas le risque d'oublier des rues.

[KerLannais]

je me demande s'il n'y a pas le risque d'oublier des rues.

Tu ne pense pas sincèrement que des spécialistes d'informatique théorique et de théorie des graphes aient pu pondre un algorithme d'exploration de graphe non exhaustif

L'idée est la même que pour l'exploration des arbres sauf que tu détecte les boucles. C'est grosso modo l'algorithme décrit par Garf pour le parcours en profondeur. Le parcours en largeur consiste à dire que tu pars d'un carrefour, tu visite toutes les rues qui partent de ce parcours jusqu'à la prochaine intersection et tu reviens à ton carrefour. Tu considère alors que ton carrefour est visité, tu a découvert d'autres carrefour pas complètement visités au bout de chacune des rues que tu as visité. Tu vas au premier non visité et tu visite toutes les rues non visitées autour. Tu continue jusqu'à ce tu ais tout visité. Une boucle peux t'amener à un carrefour non visité mais c'est pas grave, tu ne le revisite pas. Dire qu'on peut l'exécuter en flanant ... il faut quand même une bonne mémoire et c'est sûr que c'est plus facile de tracer un graphe au fur et à mesure sur un papier en se balladant. Tu peut considérer que ta ville est connexe (puisque de toute façon tu ne peut accéder à d'autre composantes connexes) et la seule différence entre un graphe connexe non orienté et un arbre ce sont les boucles. A priori ce n'est pas plus difficile d'explorer un graphe qu'un arbre, surtout que les plans de villes ne sont pas forcément compliqués (surtout si tu te ballade à New York).

[invite986312212]

ah ben oui, je sais plus ce que j'avais en tête... mais ça devait être un peu fumeux!