Discussion :

[gasche]

Bon, je n'ai pas pu résister à l'appel du code. Une version avec un BFS plus classique (mais pas tout à fait non plus), si tu veux comparer :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
let bfs depart voisins arrivee =
  let deja_vu = Array.make (Array.length voisins) false in
  let rec parcours actuels distance suivants resultat =
    match actuels with
    | (sommet, chemin) :: reste ->
        if sommet = arrivee then
          parcours reste distance suivants (chemin :: resultat)
        else if deja_vu.(sommet) then
          parcours reste distance suivants resultat
        else begin
          deja_vu.(sommet) <- true;
            let ajoute_voisin suivants voisin =
              (voisin, voisin :: chemin) :: suivants in
            let suivants' =
              List.fold_left ajoute_voisin suivants voisins.(sommet) in
            parcours reste distance suivants' resultat
        end
    | [] ->
        if resultat <> [] then
          (* les chemins ont été accumulés à l'envers *)
          (List.map List.rev resultat, distance)
        else
          parcours suivants (distance + 1) [] resultat in
  parcours [depart, [depart]] 0 [] []

[drunkskater]

Oui effectivement c'est clair, et peut-être un peu trop. Je dois avouer que de toute façon, j'avais fini par comprendre ton code (en le réécrivant fonction par fonction en utilisant la bibliothèque standard). Je pourrais te donner ma version, mais je pense qu'il serait plus formateur que tu fasses le nettoyage toi-même.

Si ça t'intéresse, j'ai utilisé List.filter, List.concat et List.map.

Oui, je vais essayer de le "nettoyer" moi-même, mais garde ton code sous la main histoire que je puisse comparer lorsque j'aurai fini !

En fait, ton algo fait ce qu'on appelle un "parcours en largeur", et que tu as peut-être déjà vu en cours. Il le fait d'une manière assez lourde : dans un parcours classique sur les graphes, on associe à chaque noeud une information binaire ou ternaire (déja visité ou pas ? est-ce que je n'ai jamais visité, je suis en cours de visite ou j'ai déjà visité ?), qu'on nomme classiquement "couleur" (blanc/noir ou blanc/gris/noir). On associe donc une couleur à chaque noeud, par le biais d'un tableau par exemple, et avant de passer par un noeud on vérifie que sa couleur convient (si je suis déjà passé par là, j'annule).

En fait je n'ai jamais vu ce type de truc : Je sais plus si je l'ai dit mais ce programme servait d'illustration à un TIPE blanc de maths sur la théorie des graphes, et comme je n'ai commencé l'info qu'au deuxième trimestre on avait rien vu sur les graphes.

Par contre en fin d'année on avait fait un truc sur des graphes qui ressemblait d'ailleurs pas mal à cet algorithme : en gros le réseau était modélisé de la même façon (càd un tableau de liste), et ce qu'on avait fait c'était une fonction qui trouvait les "fils" d'un noeud. Sur le coup j'avais pas fait gaffe parce que j'étais tout content de voir que j'avais retrouvé tout seul la même modélisation du réseau, mais maintenant que tu en parle, c'est exact, on avait un système de "marquage" des noeufs qui correspond exactement à ce que tu dis sur les couleurs ! Et effectivement, c'est mille fois mieux, c'est évident !

Bon ben du coup je vais reprendre mon truc pour y intégrer ça, ça sera beaucoup mieux Juste une question, tu parle d'une couleur "grise" correspondant à "en cours de visite" : quel est l'intérêt ? C'est juste par curiosité

Bref, en fait tu as recodé (et peut-être redécouvert) un algo déjà connu, avec une approche visuelle mais pas forcément la plus efficace.

En fait cet algorithme vient effectivement d'une approche visuelle du problème : on en a essayé plusieurs et finalement celui-là - le plus bête - semblait le plus simple à programmer, donc c'est celui là qui a été retenu (à part qu'on avait quand même mis une double propagation et qu'on avait vite fait justifié l'intérêt, histoire que ça fasse pas trop simple non plus). L'histoire de suppression des arêtes vient du fait que quand on travaille à la craie sur un tableau c'est super simple de les effacer.........

mais si en plus tu veux optimiser la rapidité, si ça t'intéresse, le BFS (bread first search) classique utilise :
- plutôt qu'un filtrage des arrêtes, une table de couleurs (par exemple un tableau de booléens) pour les sommets déjà visités
- plutôt qu'un ensemble de listes qu'on fait toutes grandir de 1 à chaque itération, une file des "prochaines sommets à visiter" que l'on parcourt un par un, mais par ordre de distance au point de départ

Ouais, bien sûr que je veux optimiser ! Enfin je veux surtout apprendre à utiliser de nouveaux outils, sans que ce soit trop compliquer (je veux y aller progressivement). Sinon il n'y a absolument pas d'enjeux dans ce programme, comme je l'ai dit c'était pour un TIPE blanc de maths sup, mais vu que l'année prochaine je vais en BCPST c'est juste un hobby (en gros je me suis dit : "Quitte à avoir passé du temps sur ce truc, autant qu'il soit pas trop mal" - et puis je dois avouer que j'ai bien accroché à l'info et que j'ai vraiment envie de continuer à en faire même si malheureusement ça ne pourra plus être dans le cadre de mes études)

Pour l'histoire de marquage plutôt que de suppression des arêtes, j'ai bien compris et je vais essayer de faire ça (je sais juste pas trop quelle structure adopter...)

Par contre j'ai pas trop compris ce que tu voulais dire par le truc que j'ai mis en italique.

En tous cas encore merci, c'est vraiment super cette aide que tu m'apporte !

[drunkskater]

Bon, je n'ai pas pu résister à l'appel du code. Une version avec un BFS plus classique (mais pas tout à fait non plus), si tu veux comparer :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
let bfs depart voisins arrivee =
  let deja_vu = Array.make (Array.length voisins) false in
  let rec parcours actuels distance suivants resultat =
    match actuels with
    | (sommet, chemin) :: reste ->
        if sommet = arrivee then
          parcours reste distance suivants (chemin :: resultat)
        else if deja_vu.(sommet) then
          parcours reste distance suivants resultat
        else begin
          deja_vu.(sommet) <- true;
            let ajoute_voisin suivants voisin =
              (voisin, voisin :: chemin) :: suivants in
            let suivants' =
              List.fold_left ajoute_voisin suivants voisins.(sommet) in
            parcours reste distance suivants' resultat
        end
    | [] ->
        if resultat <> [] then
          (* les chemins ont été accumulés à l'envers *)
          (List.map List.rev resultat, distance)
        else
          parcours suivants (distance + 1) [] resultat in
  parcours [depart, [depart]] 0 [] []

merci ! Bon, j'essaie de pas le regarder avant d'avoir fini le mien par contre !

EDIT : Je viens d'avoir une idée (qui vient du fait que la perspective d'avoir à changer toute la modélisation du réseau ne me réjouissait pas) : pour l'histoire de marquage des stations visités, vu que mes stations sont des enregistrement, est-ce que je ne pourrais pas tout simplement ajouter une information pour faire un truc du genre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
type station = {
  indice: int; 
  nom: string; 
  voisins: int list; 
  ligne: string
  mutable visite : bool } 
;;

[gasche]

Bon ben du coup je vais reprendre mon truc pour y intégrer ça, ça sera beaucoup mieux Juste une question, tu parle d'une couleur "grise" correspondant à "en cours de visite" : quel est l'intérêt ? C'est juste par curiosité

Ça dépend des méthodes de parcours, et dans ce cas on n'en a pas besoin.

Le parcours en largeur a une propriété d' "oubli" : quand on a vu un sommet pour la première fois, on peut le marquer comme "vu", et refuser tous les autres chemins qui passent par ce sommet. Cela vient du fait que, comme dans ton implémentation, on parcours d'abord les sommets à distance 1, puis à distance 2, puis à distance 3, etc. Quand on voit un sommet pour la première fois, on est sûr que le chemin qu'on a pris pour y parvenir est le chemin le plus rapide, et que tous les suivants seront donc moins intéressants, et on peut les virer.

Mais tu peux avoir des graphes plus compliqués où les sommets ne sont pas à la même distance les uns des autres. On continue à regarder les noeuds dans l'ordre de leur distance au point de départ (en utilisant une file de priorité plutôt qu'une simple file; c'est l'algorithme de Dijkstra), mais on peut avoir une situation où tu as un noeud A, proche, et un noeud B un peu plus loin, qui permettent tous les deux d'accéder à un noeud C qui est très loin du noeud A et proche du noeud B. Tu vas rencontrer C en premier en parcourant les voisins de A, mais le chemin total est assez grand (distance(A) + distance(A,C)). Si tu le mets tout de suite dans les "noeuds déjà visités", il ne va pas considérer la deuxième possibilité qui vient ensuite : passer par C en tant que voisin de B, donc avec la distance distance(B) + distance(B, C) qui est plus petite. Il y a plusieurs manières de s'en sortir, et l'une d'elle est de différencier les noeuds "déjà rencontrés mais pas encore visités" (gris) et "déjà visités" (noirs).


Dans ma version du code ci-dessus, il y a en fait trois catégories de noeuds :
- les noeuds à distance N du point de départ qui restent à parcourir (liste qui diminue au fil du parcours)
- les noeuds à distance (N+1) que l'on a déjà trouvés (liste qui augmente)
- les noeuds déjà visités à une distance inférieure à N, par lesquels on ne veut plus repasser (ensemble qui augmente)

[drunkskater]

Voilà, j'ai un peu modifié mon truc : j'ai donné des noms beaucoup plus explicites aux arguments, j'ai essayé d'utiliser un peu plus de modules tout faits et surtout j'ai utilisé le système de marquage, ce qui devrait accélérer considérablement le calcul d'itinéraire.

Par contre je n'ai pas utilisé de "file des prochains sommets à visiter", parce que je suis pas sûr d'avoir bien compris et surtout je ne vois pas l'avantage par rapport au listes qu'on fait grossir.

Je n'ai pas non plus ajouté les commentaires au code (ça vient )

[le fichier se trouve une fois encore en pièce jointe pour la coloration]

Est-ce que c'est un peu plus lisible ?

Bon, maintenant dès que j'ai le temps je fait pareil pour les fonctions d'interprétation des trajets trouvés (=celles qui déterminent le nombre de changements/correspondances à pied qu'un trajet nécessite et mâchent le travail pour l'affichage du résultat).

Ah, par contre je ne sais pas si le code que j'ai mis marche vraiment : je n'ai pas pu le tester étant donné que la modélisation du réseau dont je dispose ne convient plus tout à fait.