Modélisation logicielle d'un réseau - le système de Jean-Luc

[DDEFF]

Génial !!!
Je vais essayer de décortiquer

[Jean-Luc]

Je viens de pousser de nouvelles choses sur le repository :

1 - Le programme calcule tous les itinéraires de la gare de DDEFF, il y en a 241 (x2 si on compte le même en sens inverse).
2 - Il y 18 couples source, destination qui n'ont pas d'itinéraire possible.
3 - Le programme mesure le temps de calcul de tous les itinéraires : 77ms sachant qu'il y a du code de comptage la dedans (si si je pensais que ça ferait plus, je suis épaté par les perfs du Due).

L'affichage des dits itinéraires est commenté. Pour les afficher, il faut décommenter les lignes 288 à 293 de GestionnaireReseau.ino

[Dominique]

Questions :

• Est-ce ces itinéraires tiennent compte des positions des aiguilles ?
• Sinon, pour en parcourir un faut-il positionner les aiguilles avant le départ du train ?
• Quid des autres itinéraires pendant les mouvements des trains ?

[Jean-Luc]

Questions :

• Est-ce ces itinéraires tiennent compte des positions des aiguilles ?
• Sinon, pour en parcourir un faut-il positionner les aiguilles avant le départ du train ?
• Quid des autres itinéraires pendant les mouvements des trains ?

Dans l'ordre :

• Non, les itinéraires ne tiennent pas compte de la position des aiguilles. En fait il s'agit ici du problème inverse de celui que tu exposes plus haut. Il s'agit, à partir d'un couple d'emplacements (A,B) sur le réseau, de déterminer les itinéraires possibles et donc la position des aiguilles à appliquer.
• Oui
• Ce n'est pas traité pour l'instant mais c'est facilement faisable.

[DDEFF]

Tu vois, calculer tous les itinéraires, ça n'est pas si long.
Et pourtant, il y en a plein.

Evidemment, j'ai quelques questions

1°) Je passe sur le :

Code: [Sélectionner]

static Voie **sVoies;
Je comprends (enfin, je crois), mais ça se complique.
Un pointeur de pointeur…

2°) je ne comprends pas pourquoi tu dois avoir un creeCheminVers (…) et un tousLesCheminsVers(…) dans chaque classe.
Quand on hérite, on n'hérite pas de tout ?

3°) Là, je décroche :

Code: [Sélectionner]

static const byte taille() {
      return ((sNombre >> 3) + ((sNombre & 7) != 0));
Je comprends (grosso-modo) la syntaxe, mais pourquoi tu fais ça ?

4°) Et ailleurs, encore mieux (mais je ne comprends plus la syntaxe) :

Code: [Sélectionner]

void EnsembleDeVoies::ajouteVoie(byte identifiant)
{
  mEnsemble[identifiant >> 3] |= 1 << (identifiant & 7);
}

void EnsembleDeVoies::enleveVoie(byte identifiant)
{
  mEnsemble[identifiant >> 3] &= ~(1 << (identifiant & 7));
}

bool EnsembleDeVoies::contientVoie(byte identifiant)
{
  return (mEnsemble[identifiant >> 3] & 1 << (identifiant & 7)) != 0;
}

5°) Tu as marqué un commentaire, c'est vrai, mais pour comprendre, là, c'est costaud :

Code: [Sélectionner]

  /* Si sVoies n'est pas alloue, alloue arbitrairement 256 emplacements */
  if (sVoies == NULL) {
    sVoies = (Voie **)malloc(sTailleTableau * sizeof(Voie **));
  }

Et, la plus drôle pour la fin : le loop() est ... vide !

[Jean-Luc]

Tu vois, calculer tous les itinéraires, ça n'est pas si long.
Et pourtant, il y en a plein.

Je n'aurais pas dit plein. Ça reste très raisonnable.

1°) Je passe sur le :

Code: [Sélectionner]

static Voie **sVoies;
Je comprends (enfin, je crois), mais ça se complique.
Un pointeur de pointeur…

Oui, je maintiens une table de pointeurs, des Voie* où chaque objet Voie, ou dérivé de Voie vient inscrire son pointeur  à l'index de son identifiant. De cette manière, je peux retrouver un objet Voie par son identifiant. Comme je ne sais pas à priori combien d'éléments de voie je vais avoir. Je pars sur 256 et une fois que j'ai tout, je retaille le tableau au nombre d'élément effectif.

2°) je ne comprends pas pourquoi tu dois avoir un creeCheminVers (…) et un tousLesCheminsVers(…) dans chaque classe.
Quand on hérite, on n'hérite pas de tout ?

J'ai laissé creeCheminVers et ajouté tousLesCheminsVers à côté mais à terme, creeCheminVers disparaîtra car tousLesCheminsVers fait mieux.

3°) Là, je décroche :

Code: [Sélectionner]

static const byte taille() {
      return ((sNombre >> 3) + ((sNombre & 7) != 0));
Je comprends (grosso-modo) la syntaxe, mais pourquoi tu fais ça ?

Ok. Comme je l'ai dit, je gère un vecteur de bits. Là je calcule la taille en nombre d'octets du tableau nécessaire au stockage de ce vecteur. sNombre est le nombre de bits nécessaires, sNombre >> 3 correspond à une division par 8 (2^3 = 8)et donc au nombre d'octets. Mais c'est une division entière. Si sNombre n'est pas divisible par 8 j'ai un reste et j'ai besoin d'un octet de plus. sNombre & 7 est le reste de la division. Si il est différent de 0, je dois avoir un octet de plus et c'est çe que je calcule puisque le != 0 me renvoie 1 si il y a un reste et 0 sinon.

4°) Et ailleurs, encore mieux (mais je ne comprends plus la syntaxe) :

Code: [Sélectionner]

void EnsembleDeVoies::ajouteVoie(byte identifiant)
{
  mEnsemble[identifiant >> 3] |= 1 << (identifiant & 7);
}


Pareil. Je veux mettre à 1 le bit de rang identifiant. Je divise identifiant par 8 pour avoir l'octet puis sur cet octet je fais un ou avec un 1 décalé du reste.

Code: [Sélectionner]

void EnsembleDeVoies::enleveVoie(byte identifiant)
{
  mEnsemble[identifiant >> 3] &= ~(1 << (identifiant & 7));
}

bool EnsembleDeVoies::contientVoie(byte identifiant)
{
  return (mEnsemble[identifiant >> 3] & 1 << (identifiant & 7)) != 0;
}


Et là auss, je mets le bit a 0 et je le teste.

5°) Tu as marqué un commentaire, c'est vrai, mais pour comprendre, là, c'est costaud :

Code: [Sélectionner]

  /* Si sVoies n'est pas alloue, alloue arbitrairement 256 emplacements */
  if (sVoies == NULL) {
    sVoies = (Voie **)malloc(sTailleTableau * sizeof(Voie **));
  }


malloc alloue une zone mémoire comptée en nombre d'octets. Ici je veux allouer sTailleTableau pointeurs. Un pointeur a une taille de sizeof(Voie **) octets. Je caste le resultat qui est un void * en Voie **

Et, la plus drôle pour la fin : le loop() est ... vide !

Tout est fait dans setup :-)

[Jean-Luc]

Je continue sur le programme (et incidemment la bibliothèque associée).

Actuellement il n'est pas possible d'avoir un réseau bouclé (c'est ballot hein ?  ). En effet, la recherche d'itinéraires ne termine pas car il n'existe pas de moyen de savoir que l'on est déjà passé par un élément de voie (nœud du graphe). En fait ça finirait par planter par manque de mémoire car lorsque la recherche du but est faite sur un mauvais chemin et que ce mauvais chemin ramène à un élément déjà parcouru sur ce chemin, on tourne en rond et l'appel récursif des fonctions conduit à une pile qui ne fait que croître.

La solution est bien connue en algorithmique sur les graphes : il faut jouer au petit poucet et marquer les endroits où on est déjà passé. Il ne faut pas les marquer globalement en marquant les éléments de voie car cela empêcherait la découverte des chemins qui partagent un sous ensemble d'éléments de voie. Il faut donc un historique de parcours que l'algo emmène avec lui (c'est la version petit poucet avec un GPS). J'ai déjà la classe permettant de faire ça : les ensembles de voies. Je suis en train d'ajouter ça dans l'algo existant.

Il y a le problème des croisements. En effet, c'est le seul élément de voie que l'on peut parcourir deux fois sans emprunter le même chemin. Il doit être considérer comme unique en terme d'occupation d'itinéraire mais permet deux chemins disjoints. La solution est simple, on n'ajoute pas les croisements dans l'ensemble des éléments de voies parcourus dans l'algorithme d'exploration. On pourra donc passer par un croisement autant de fois qu'on le veut sans savoir que l'on y est déjà passé. À moins d'avoir un réseau exclusivement constitué de croisements ça ne pose pas de problème.

Denis, as-tu le reste de ton futur réseau ?

[DDEFF]

Et pourquoi on ne ferait pas un réseau composé uniquement de croisements ?

J'ai déjà cherché pour la suite du réseau, mais je pense que ça va t'embêter :



1°) Si tu sors par l'une des VoieLibre0 ... VoisLibre9 et que tu reviens par une autre de ces voies, tu fais une boucle de retournement 
Je n'y avais pas pensé au début, mais c'est logique.

2°) La seule voie bouclable "normalement", c'est VoieLibre0 <-> VoieLibre7. C'est ce que je fais.
La voieLibre7 longe la gare et passe dessous pour rejoindre la VoieLIbre0.
Comme ce circuit passe au travers de toute la gare, j'en profite pour mettre une gare cachée, du type "biceps" (appellation perso pour 1 tendon, plusieurs fibres et un tendon), comme la quasi totalité des gares cachées.
La facture chez Peco s'alourdit 
Comme ça, la gare cachée donne accès à toutes les voies. 



3°) VoieLibre6 <-> VoieLibre5
      VoieLibre4 <-> VoieLibre1
      VoieLibre3 <-> VoieLibre2.

4°) Et j'aurais quelques bifurcations pour passer d'un circuit à l'autre.
Le but est simple : quand un train sort par une voie, on ne doit pas savoir par laquelle il reviendra.

Il me reste à caser tout ça dans 3.42 x 2,57 

Donc, M. Peco m'attend au coin du bois...

[Jean-Luc]

Et pourquoi on ne ferait pas un réseau composé uniquement de croisements ?

Faire un réseau exclusivement composé de croisement est un des droits fondamentaux du modéliste ferroviaire  mais il s'expose à être la risée de ses confrères 

1°) Si tu sors par l'une des VoieLibre0 ... VoisLibre9 et que tu reviens par une autre de ces voies, tu fais une boucle de retournement 
Je n'y avais pas pensé au début, mais c'est logique.

J'ai réfléchi aux boucles de retournement et je pense avoir trouvé une solution élégante et simple. J'ajoute une classe d'élément de voie : BoucleDeRetournement. Dans un parcours qui est une boucle de retournement, un élément de ce type doit être inséré. L'un des connecteurs est dans le sens normal mais l'autre doit être connecté à contresens.




Par exemple voici une boucle simple. On commence la construction par E. On connecte le SORTANT de E à l'ENTRANT de l'aiguillage A. On connecte le SORTANT_DROIT de A à l'ENTRANT de B. On connecte le SORTANT_GAUCHE de A à l'ENTRANT de C. On connecte le SORTANT de B sur l'ENTRANT de D et on connecte le SORTANT de C sur le SORTANT de D. Comme D est une instance de BoucleDeRetournement, cette dernière connexion doit être faite à contresens.

Ensuite pour le parcours des éléments, comme je l'ai dit, on décide d'un sens de parcours. Ainsi si on cherche E depuis A dans le sens normal, que va-t-il se passer ? On commence par explorer côté SORTANT_DROIT, on arrive sur B, on continue sur D. Là on a un probléme, si on continue sur C, on arrive dans C avec le sens normal et en faisant ça, C va continuer sur D et on part en boucle infinie (ou bien si l'algo joue au petit poucet, il stoppe car il passe deux fois par un élément et il ne trouve pas. Comment faire ? c'est assez simple, il suffit d'inverser le sens de parcours quand on traverse un élément BoucleDeRetournement (ça servira aussi à commuter l'alim d'ailleurs :-)). Donc avant que D appelle C, il retourne le sens. C continuera donc avec A qui continuera avec E et E est trouvé. Du côté de la branche SORTANT_DEVIE, on arrive sur C qui appelle D, qui inverse le sens et appelle B qui appelle A et E est également trouvé. Deux chemins possibles, donc, selon le sens de parcours de la boucle de retournement.

On a maintenant un nouveau problème. Si on joue au petit poucet en notant les éléments parcourus pour ne pas passer deux fois par les mêmes éléments et permettre à l'algorithme de terminer, on va arrêter sur A. Comment faire ? C'est pas compliqué non plus, il ne faut pas marquer seulement les éléments mais le couple élément/sens de parcours. ainsi quand on parcoure A dans le sens normal, on marque A/normal. Quand on le reparcoure dans le sens inverse, on marque A/inverse. Donc deux marquages différents qui font qu'on ne va pas reconnaître A en le parcourant en sens inverse.

Donc, M. Peco m'attend au coin du bois...

My model train reseller is rich 

PS: on peut insérer une image de la pièce jointe dans le texte : clic sur la pièce jointe pour l'agrandir, clic droit « copier l'adresse de l'image », puis coller l'adresse dans une balise BBCode img

[Jean-Luc]

J'ai programmé et testé la recherche d'itinéraires avec marquage des nœuds visités. Ça fonctionne mais ca n'est pas satisfaisant.

En effet, l'algorithme actuel n'est pas très économe. Quand un aiguillage ou une TJD est rencontré (une divergence), l'exploration est faite dans la branche droite et déviée. Si on rencontre N aiguillages/TJD, on fait donc 2^N explorations. Ça, on n'y peut pas grand chose.

Par contre, si lors de l'exploration, on a une convergence des chemins, on n'y voit que du feu et la suite du chemin est explorée plusieurs fois et l'algorithme travaille donc de manière redondante.

Avec le marquage, ça engendre beaucoup de copies. En effet, comme, en cas de convergence, le chemin est exploré plusieurs fois, on ne peut pas le marquer de manière globale, en posant des cailloux sur le chemin car en, cas de convergence, l'algorithme échouerait. Il est donc marqué via un carnet que l'explorateur emmène avec lui. Lors d'une divergence, le carnet est copié et l'original est emmené sur la branche droite, la copie sur la branche déviée et ainsi de suite. On fait donc 2^N copies.

Évidemment sur mon Mac, ça s'exécute en un clin d'œil mais sur l'Arduino ca posera problème.

Je vais donc refaire l'algorithme pour tenir compte des convergences et ne pas dupliquer du travail. L'avantage est qu'un marquage global, donc beaucoup plus simple et rapide, est utilisable dans ce cas.

[DDEFF]

Merci pour l'info permettant (enfin !) de mettre des images dans le texte. Yeaahh. 

Progressivement, à force de décortiquer, je me pose des questions.

Je proposerais bien de n'en avoir que deux classes :
Une classe arc et une classe nœud.

Dans la classe arc, on garde la tienne pour les cantons et pour une voie sans issue, on dit que le suivant, c'est 0 (zéro).

Dans la classe nœud, on définit 4 entrées sorties, systématiquement.
- pour une aiguille, l'une des entrées-sorties est à zéro, simplement.
- pour un croisement, une TJS, une TJD, un  triple, on définit les 4.

Ordre proposé :     1    2
                              4    3                               

Par ailleurs, on définit quels sont les aboutements INTERNES sont possibles dans les nœuds :
- pour une aiguille,     on aura 1,2,3,0 et 1-2, 1-3,    0,    0
- pour un croisement, on aura 1,2,3,4 et 1-3, 2-4,    0,    0
- pour une TJS,           on aura 1,2,3,4 et 1-2, 1-3, 3-4,    0
- pour une TJD,           on aura 1,2,3,4 et 1-2, 1-3, 2-4, 3-4
- pour un triple,          on aura 1,2,3,4 et 1-2, 1-3, 1-4,    0

Les aboutements sont ordonnés (A<B). Quand on l’interrogera, on ordonnera aussi la demande.

Une autre remarque : quand on cherche à aller d'un point à un autre, c'est toujours d'un canton à un autre, jamais d'un nœud à un autre nœud.
Je sais qu'en théorie des graphes, on va d'un nœud à un autre...

Et, d'ailleurs, pour sortir des labyrinthes (ce qui est un peu notre cas), on met une croix à côté de l'entrée du tunnel qu'on choisit.
Donc, ce qu'on marque, ce n'est pas le nœud lui-même, mais l'une de ses extrémité.
Je ne me rappelle pas avoir déjà vu de méthode qui tenait compte du sens de parcours d'un arc (ce qui est différent du problème des arcs orientés dès la départ).

Dans ton exemple et ce que tu disais auparavant sur les circuits complets qui seraient impossibles, je dirai que :
Je sais aller de E à B, de E à D, de B à D, de D à B, de D à E, de E à C, de C à E. Mais ni de D à C ou de C à D.
Et tu t'occuperas du problème de l'inversion dans le loop{}
De cette manière, on ne retourne pas sur ses pas.

Dernière remarque :
J'ai l'impression que tu veux faire deux choses à la fois :
1°) Trouver toutes les façons d'aller de A à B. Là, je comprends bien.
2°) Gérer les incompatibilités en même temps.

J'aurais mieux compris, surtout dans le setup{}, que tu cherches tous les itinéraires possibles (quelques ms).
Tu les ranges (A<B).
Dans le setup{}, on peut perdre une seconde...
Et, dans le loop{}, tu géreras le fait que tel itinéraire ne peux pas être fait en même temps que tel autre, en testant parmi ceux que tu as trouvé auparavant.

J'espère avoir été constructif 

[Jean-Luc]

Je proposerais bien de n'en avoir que deux :
Une classe arc et une classe nœud.

Dans la classe arc, on garde la tienne pour les cantons et pour une voie sans issue, on dit que le suivant, c'est 0 (zéro).

Dans la classe nœud, on définit 4 entrées sorties, systématiquement.
- pour une aiguille, l'une des entrées-sorties est à zéro, simplement.
- pour un croisement, une TJS, une TJD, un  triple, on définit les 4.

Par ailleurs, on définit quels sont les aboutements INTERNES sont possibles dans les nœuds :
- pour une aiguille,     on aura 1,2,3,0 et 1-2,1-3,   0,   0
- pour un croisement, on aura 1,2,3,4 et 1-3,2-4,   0,   0
- pour une TJS,           on aura 1,2,3,4 et 1-2,1-3,3-4,   0
- pour une TJD,           on aura 1,2,3,4 et 1-2,1-3,2-4,3-4
- pour un triple,          on aura 1,2,3,4 et 1-2,1-3,1-4,   0

Les aboutements sont ordonnés (A<B). Quand on l’interrogera, on ordonnera aussi la demande.

Oh non non non.

Pas de remplacement du graphe d'objets utilisant le polymorphisme par deux types d'objets (en fait un seul car je ne vois pas l'avantage de faire des arcs puisqu'un arc n'est rien de plus que le pointeur que l'on suit ici) est à l'encontre de la programmation objet. Tu vas, au lieu d'avoir un code spécifique à chaque type d'objet, avoir un code générique ou tu vas retrouver le code actuel dans une seule fonction enrobé de test pour savoir dans quel type de voie on est. Donc un truc énorme et moins conpréhensible. C'est pas du tout le principe. C'est clairement remplacer la programmation objet par de la programmation classique. On repart en arrière de 20 ans.

Une autre remarque : quand on cherche à aller d'un point à un autre, c'est toujours d'un canton à un autre, jamais d'un nœud à un autre nœud.
Je sais qu'en théorie des graphes, on va d'un nœud à un autre...

Les cantons ne sont pas le problème pour l'instant, ce n'est tout simplement pas traité. Par la suite, on peut regrouper les nœuds du graphe en cantons. Ça reste à faire mais je ne vois pas de difficultés. Pour mon réseau j'ai besoin du graphe car mes cantons contiennent 0 ou plusieurs aiguillages. Par ailleurs je pense ajouter la longueur des éléments de voie. pour calculer les distances.

Et, d'ailleurs, pour sortir des labyrinthes (ce qui est un peu notre cas), on met une croix à côté de l'entrée du tunnel qu'on choisit.
Donc, ce qu'on marque, ce n'est pas le nœud lui-même, mais l'une de ses extrémité.
Je ne me rappelle pas avoir déjà vu de méthode qui tenait compte du sens de parcours d'un arc (ce qui est différent du problème des arcs orientés dès la départ).

C'est équivalent à marquer le nœud où on arrive.

Dernière remarque :
J'ai l'impression que tu veux faire deux choses à la fois :
1°) Trouver toutes les façons d'aller de A à B. Là, je comprends bien.
2°) Gérer les incompatibilités en même temps.

Non, pour l'instant je ne fait que 1). Je construis une liste d'ensembles de nœuds liant un point de départ à un point d'arrivée.

Une fois que tu as fait 1), faire 2) n'est pas compliqué, savoir si deux itinéraires sont incompatibles consiste à faire une intersection des deux ensembles de chemins. Si l'intersection est vide, les itinéraires sont compatibles.

J'aurais mieux compris, surtout dans le setup{}, que tu cherches tous les itinéraires possibles (quelques ms).
Tu les ranges (A<B).
Dans le setup{}, on peut perdre une seconde...
Et, dans le loop{}, tu géreras le fait que tel itinéraire ne peux pas être fait en même temps que tel autre, en testant parmi ceux que tu as trouvé auparavant.

En informatique, on échange de la mémoire contre du temps de calcul et inversement. Il faut doser entre les deux. Dans ta gare, il y a 93 éléments de voies, il faut donc 12 octets pour stocker un itinéraire. Il suffit de reboucler voieLibre0 sur voirLibre7 pour avoir plus de 600 itinéraires entre les extrémités (7,2ko). Et on n'a pas traité le cas des voie en gares. En fait c'est exponentiel et sur un réseau complet, ça fait un sacré paquet d'itinéraires si on considère tous ceux possibles entre 2 paires de cantons. Je crains donc que la mémoire disponible ne suffise pas (mais alors pas du tout). Il faut donc les calculer au vol. Avec le nouvel algorithme que je fais ça sera encore plus rapide et le temps de calcul ne sera pas un problème.

J'espère avoir été constructif 

Tout à fait !

[DDEFF]

On repart en arrière de 20 ans

Et pan sur le bec !
Mais c'est dit gentiment et c'est parfaitement vrai.

J'avoue avoir un peu de mal avec la programmation objet complète comme celle que tu utilises. Il y a encore un aspect "magique"...
Mais je suis forcé de constater que c'est redoutablement efficace. Et ça me plait.

J'ajouterais que la croissance exponentielle dont tu parles (l'idée de calculer tous les couples) pourrait ne pas avoir lieu.
En effet, il y a énormément de couples qui ne servent à rien.

Il y a deux types de trains : les trains gérés en automatique et LE train géré en manuel.
On peut changer à tout moment de train suivi en manuel.
L'ancien devient un train automatique et le nouveau sélectionné est le train manuel.

Pour que l'ancien train sache où il va, il faut qu'on lui donne une destination.
Il y a trois types de destinations possibles :
1°) Une voie précise d'une gare visible
2°) N'importe quelle voie d'une gare cachée
3°) Un circuit qui boucle indéfiniment qu'on choisit dans une liste.

Les circuits peuvent être mémorisé fois pour toute : ils sont peu nombreux.
Un circuit, c'est une suite définie d'itinéraires A-B.
Un itinéraire A-B, tu as montré qu'on peut en avoir jusqu'à 11 pour un couple donné de ma gare. Et l'exponentielle peut être monstrueuse si on cherche toutes les façons de boucler un circuit.
Par contre, si on définit un circuit qui boucle de A -> A, on peut dire que c'est de (A->A1) + (A1->A2) + (A2->A3) + .... + (An->A) et là, plus de croissance exponentielle.
En fonction des occupations, le train automatique qui suit un circuit adaptera chaque partie à l'état du terrain.

Et on n'a plus à gérer que 1°) et 2°), sachant qu'à chaque fois, on ne va que d'une gare à la gare suivante.

[Jean-Luc]

J'ajouterais que la croissance exponentielle dont tu parles (l'idée de calculer tous les couples) pourrait ne pas avoir lieu.
En effet, il y a énormément de couples qui ne servent à rien.

Il y a deux types de trains : les trains gérés en automatique et LE train géré en manuel.
On peut changer à tout moment de train suivi en manuel.
L'ancien devient un train automatique et le nouveau sélectionné est le train manuel.

Pour que l'ancien train sache où il va, il faut qu'on lui donne une destination.
Il y a trois types de destinations possibles :
1°) Une voie précise d'une gare visible
2°) N'importe quelle voie d'une gare cachée
3°) Un circuit qui boucle indéfiniment qu'on choisit dans une liste.

Justement, le cas que tu cites fait que tous les nœuds peuvent être, au moins, point de départ. Si l'opérateur prend le contrôle d'un train géré en automatique, il peut le faire à n'importe quel moment et donc alors que que le train est à n'importe quelle position dans le réseau. Par ailleurs il peut y avoir plusieurs opérateurs.

Les circuits peuvent être mémorisé fois pour toute : ils sont peu nombreux.
Un circuit, c'est une suite définie d'itinéraires A-B.
Un itinéraire A-B, tu as montré qu'on peut en avoir jusqu'à 11 pour un couple donné de ma gare. Et l'exponentielle peut être monstrueuse si on cherche toutes les façons de boucler un circuit.
Par contre, si on définit un circuit qui boucle de A -> A, on peut dire que c'est de (A->A1) + (A1->A2) + (A2->A3) + .... + (An->A) et là, plus de croissance exponentielle.
En fonction des occupations, le train automatique qui suit un circuit adaptera chaque partie à l'état du terrain.

Oui, on peut construire des itinéraires en faisant l'union de sous itinéraires. On économisera de la mémoire mais on en perdra car il faudra mettre en place des structures de données pour construire les circuits comme des listes de sous itinéraire, ce qui aura un coût en mémoire. Ça sera plus compliqué à exploiter et je crains que l'on ne soit en fait perdant au niveau mémoire.

Et on n'a plus à gérer que 1°) et 2°), sachant qu'à chaque fois, on ne va que d'une gare à la gare suivante.

Mais la construction des itinéraires sera rapide, ce n'est pas la peine de les stocker.

[Jean-Luc]

Bonsoir,

Je viens de pousser une nouvelle version avec le nouvel algorithme.

Le temps de calcul des 603 itinéraires de la version bouclée est de 170ms.

Certains itinéraires bouclés peuvent ne pas être trouvés quand un itinéraire possible est inclus. Ca n'est pas très grave.  J'ai l'idée d'une variante pour les inclure tous mais je me pose la question de l'intérêt.