Discussion :

[ammoula55]

Bonjour,
je travaille sur une application java qui cherche tous les chemins possibles entre deux points dans une carte. j'ai pensé à utiliser l'algorithme de recherche en profondeur
est-ce qu'on peut utiliser cet algorithme sur une carte en java?
est-ce que je dois utiliser la base de données de pays (dans ce cas j'ai besoin de pays de Tunisie) pour utiliser l'algorithme?
comment afficher toutes les routes sur la carte?
Cordialement

[ChipsAlaMenthe]

Salut à toi!
Alors concrètement c'est quasiment impossible à ma connaissance d'afficher tous les chemins possibles pour aller d'un point à un autre, car il y en a une infinité. Par contre afficher les N plus courts chemins ça c'est possible!
Pour aller d'un point A à un point B, il faut utiliser ce qu'on appelle l'algorithme de Dijkstra. Il te permettra de trouver le chemin le plus court pour y parvenir. Il existe bien sûr d'autres algos mais celui-là est pas mal.
Il ne te reste plus qu'à améliorer l'algo ou alors l'intégrer dans une autre fonction pour trouver d'autres chemins, comme par exemple le 2ème chemin le plus court, le 3ème, etc...

[Flodelarab]

Bonjour

Tous les chemins mènent à Rome. Tu n'auras jamais l'exhaustivité.

Alors concrètement c'est quasiment impossible à ma connaissance d'afficher tous les chemins possibles pour aller d'un point à un autre, car il y en a une infinité.

Sauf en considérant les routes déjà construites qui sont monotones (toujours croissantes) sur le chemin à vol d'oiseau entre ton départ et ton arrivée.
Ce modèle ne convient pas aux routes de montagnes par exemple.

[dourouc05]

Alors concrètement c'est quasiment impossible à ma connaissance d'afficher tous les chemins possibles pour aller d'un point à un autre, car il y en a une infinité.

. Puisque l'ensemble des routes est fini (on peut le représenter dans un ordinateur, par essence fini), non, il existe un nombre fini de chemins entre deux points, sous l'hypothèse d'élimination des boucles (par exemple, interdire de faire trois fois le tour du pâté de maisons ; en faisant le tour une fois de plus, tu as un nouveau chemin, mais pas très intéressant). (Par contre, s'il y avait un ensemble infini mais dénombrable de routes, je ne me prononcerais pas sur la dénombrabilité de l'ensemble des chemins, ça ressemble fort à l'ensemble des sous-ensembles.) Cela ne préjuge cependant en rien de la faisabilité d'une visualisation utile .

Par conséquent, l'idée d'effectuer un parcours complet du graphe me semble bonne — en largeur, en profondeur, je ne vois pas d'inconvénient, il faut juste éviter les boucles (éviter l'exploration d'un chemin si tu repasses par une arête déjà visitée, en gros). Niveau complexité en temps, par contre, ça risque d'être un peu plus qu'élevé (donc algorithme impraticable sur de "grands" graphes). Si tu veux éviter ce traitement spécifique des boucles ou utiliser l'algorithme en pratique, alors utilise une recherche de plus court chemin (à adapter), comme suggéré par ChipsAlaMenthe.

[Flodelarab]

. Puisque l'ensemble des routes est fini (on peut le représenter dans un ordinateur, par essence fini), non, il existe un nombre fini de chemins entre deux points,

Si on va par là, la quantité de parties d'échecs possibles est finie.

[ChipsAlaMenthe]

. Puisque l'ensemble des routes est fini (on peut le représenter dans un ordinateur, par essence fini), non, il existe un nombre fini de chemins entre deux points, sous l'hypothèse d'élimination des boucles (par exemple, interdire de faire trois fois le tour du pâté de maisons ; en faisant le tour une fois de plus, tu as un nouveau chemin, mais pas très intéressant).

En fait je considèrais à ce moment là qu'un chemin déjà parcouru peut être parcouru plusieurs fois ^^, même si ça n'a aucun intérêt sauf si le mec s'entraine pour son footing matinal ^^.