Manœuvres et cabotage

[bogie-wogie]

Un petit problème de manoeuvre qui m'intrigue et que je vous soumets donc en dehors des défis zebdomadaires.

L'énoncé : j'analysais quelques configurations particulières de mon petit triage à deux voies favori de Jevret, et en particulier les rames se terminant en -DAE/-EAD, -EAF/-FAE, -FAG/-GAF, etc. (plus généralement du type -RAS/-SAR où R et S sont les deux dernières destinations). En effet une belle règle apparaît permettant (presque) d'affirmer que la rame se terminant en -SAR nécessite une (et une seule) manoeuvre de plus que la rame en -RAS.

Exemples : BCDAE se trie en 4 coups, il en faut 5 pour BCEAD ; de même CDBEAF se trie en 6 coups alors que 7 sont nécessaires pour CDBFAE. Et soudain je tombe sur un os avec les deux rames suivantes :

Si la rame [2] se trie en 7 manoeuvres (vous pouvez vous amuser à le vérifier) la rame [1] qui devrait se trier en 6 coups en nécessite pas moins de 8 Et j'ai eu beau triturer cette rame dans tous les sens, pas moyen de descendre en dessous de 8 manoeuvres. De plus un certain nombre d'autres règles et indicateurs semblent montrer que 8 est le minimum dans ce cas précis.

Pourtant selon toute logique, si on inverse E et F dans cette rame pour placer le F avant le E, comme dans la rame [2], on devrait augmenter le nombre de manoeuvres nécessaires, pas le diminuer !

Autre élément à verser au dossier : pour trier la rame [1] il y a au moins 11 solutions différentes possibles... Un peu beaucoup, et cela tendrait à montrer qu'il existe une (ou des) solution(s) plus courte(s). En 6 coups alors, car une autre règle (qui ne souffre aucune exception) affirme que cette rame se trie en un nombre pair de manoeuvres.

J'avais presque envie d'attendre lundi pour vous proposer ce défi, mais après avoir passé pas mal de temps dessus il me paraît un peu trop ardu pour servir de petit problème distrayant. En outre je n'ai pas vraiment envie d'attendre une bonne semaine pour avoir une réponse (j'ai besoin de la réponse pour d'autres analyses), et enfin je continue moi-même à chercher LA solution en 6 manoeuvres : il ne serait pas très correct de vous soumettre un problème dont je ne connais pas la réponse...

Voilà : un problème à la fois classique et inhabituel. Et comme je sais qu'il y a dans l'assistance des manoeuvriers plus compétents que moi, autant que je profite (pour une fois) de leur savoir-faire

bw

[piko30]

Bonjour à tous
Privé d'internet depuis quelques jours, je profite d'un retour, mais pour combien de temps?
Dons pas d'inquiétudes si je ne donne pas les résultats ce soir. Du reste je n'est reçu d'une solutions

[dania]

...
Exemples : BCDAE se trie en 4 coups, il en faut 5 pour BCEAD ; de même CDBEAF se trie en 6 coups alors que 7 sont nécessaires pour CDBFAE. Et soudain je tombe sur un os avec les deux rames suivantes :
...

j'arrive a me demander si tu as su le démontrer mathématiquement ou empiriquement ? <= je vote 2
j'ai rien essayé d'autre mais il est possible que le cas favorable soit directement fonction du nombre de voitures (pair/impair) ? comment solutionner un problème facilement

[bogie-wogie]

Pour l'instant (en ce qui concerne le problème précis posé) je n'en suis qu'à l'expérimentation. C'est-à-dire que j'examine un grand nombre de configurations similaires pour essayer de dégager une règle générale. Et ce n'est qu'ensuite, une fois une règle "supputée", que j'essaye (dans une deuxième étape) de la démontrer de manière théorique. En fait je suis (par formation et par goût) plus physicien que mathématicien : je préfère déduire les règles et les lois à partir de la pratique que théoriser dans l'abstrait.

J'ai d'ailleurs eu, il y a quelques années (disons une bonne dizaine à présent) une grande discussion avec des profs de maths en classe préparatoire au lycée Louis-le-Grand sur la théorie et la pratique de l'analyse de Fourier. Je l'avais étudié autrefois (il y a plus de 40 ans) mais de manière purement théorique, et 30 ans plus tard c'est toujours ainsi qu'elle était enseignée en France alors que depuis... Ainsi les étudiants français (à l'époque, je crois que ça a changé depuis et j'essaie de me faire croire que c'est grâce à cette discussion et à mes arguments) ignoraient tout de la FFT (Fast Fourier Transform = Transformée de Fourier Rapide). Au niveau des transformées tout je que j'avais appris était celle de Laplace. Fort utile en théorie électronique mais... Dans mon travail quotidien, c'était la FFT qui dominait, et cela très largement. Et cela continue dans la vie de tous les jours : il n'y a qu'à prenser à la TNT, au format d'images *.jpg etc. qui font tous abondamment appel à la FFT.

Le gros problème, pour l'Education Nationale en France, c'est que la FFT (comme la plupart des transformées numériques récentes telles qu'à base d'ondelettes et autre) c'est de la cuisine mathématique. Ce n'est pas une belle théorie bien ficelée et tout (même si son aspect théorique a été développé et son emploi validé). Et moi je dis : ce sont les mathématiques qui doivent être au service de la science et pas l'inverse. Il est bien sûr intéressant et même indispensable que les maths se développent en tant que telles : les retombées sont parfois inattendues et spectaculaires. Mais quand on forme des scientifiques ou des ingénieurs on devrait leur apprendre le côté plus utilitaire de toutes ces belles théories.

Je ne crois pas que cela ait beaucoup changé depuis mon époque (à lire avec une voix chevrotante svp). On forme des théoriciens sans aucun sens pratique, aucune notion de la réalité : ce sont nos élites...
Et on se demande pourquoi la France va si mal.

bw
[A propos de la France qui va mal, il y a 10 mn Mme bw est venue me voir en me demandant si sa souris avait ou non perdu son AAA elle aussi Elle voulait en fait juste changer la pile (c'est une souris sans fil) et savoir s'il fallait une pile AA ou AAA... ]

[piko30]

Houla la ,il sont ou les comprimés, j'ai du mal à suivre...

[bogie-wogie]

J'avoue que je me suis un peu défoulé, là, mais ça fait du bien !
Ceci dit, et pour répondre un peu plus directement à dania, en utilisant cette méthode d'analyse comparative pour en dégager des règles générales, j'ai réussi à établir un certain nombre de ces règles permettant souvent de simplifier la résolution de l'un ou l'autre problème ardu (pas tous, malheureusement).

Par exemple, le nombre minimum absolu de manoeuvres nécessaires pour résoudre un problème donné est obtenu par la formule : min = 2n+1, où "n" est le nombre d'inversions présentes dans la rame. Une "inversion", ici, est toute paire de wagons où le second devra être placé devant son prédécesseur.
Un peu confus ? (J'avais expliqué cette règle il y fort longtemps, tout au début de ce fil) Prenons donc un exemple précis, tel le dernier problème qui vous a été soumis fin 2011 : trier la rame EBADFC. Elle comporte les "inversions" suivantes : "EB", "BA" et "FC", soit n=3. On sait donc dès le départ qu'on ne pourra pas descendre en dessous de 2*3+1 = 7 manoeuvres pour effectuer le tri. Et dans ce cas c'est effectivement le nombre de manoeuvres obtenu pour la meilleure solution.

Mais ce n'est pas toujours le cas, et bien trop souvent on n'arrivera pas à descendre aussi bas en nombre de manoeuvres pour notre solution. D'autres règles peuvent alors mieux cerner le problème. Par exemple la règle dite Qs pour les rames où le dernier wagon est déjà à sa place. Une autre règle établie et validée après une analyse "sur le terrain". En reprenant notre exemple ci-dessus, si on augmente la rame EBADFC du wagon G en queue, pour obtenir la rame EBADFCG, que va devenir notre solution ? On a toujours 3 inversions et le minimum absolu est donc toujours de 7 manoeuvres. Mais peut-on atteindre ce minimum ? La réponse est : non car la règle Qs nous dit (entre autre) que pour EBADFCG le tri s'effectuera en un nombre PAIR de manoeuvres. Et 7 étant impair, le nombre pair le plus petit possible est 8. Donc 8 coups seront nécessaires, au moins. Fort heureusement la règle Qs nous précise que, sachant que EBADFC se trie en 7 manoeuvres, il ne faut qu'une manoeuvre supplémentaire pour trier EBADFCG. Et donc 8 est parfaitement réalisable.

Petit détail qui a son importance : ce genre de règles telles que Qs ne s'appliquent qu'aux rames où tous les wagons ont des destinations différentes, c'est-à-dire sans doublon (je précise cela parce que mon problème pour tout à l'heure comporte justement un "doublon", c'est-à-dire deux ouagons ayant la même destination ) Mais là encore il y a des règles pour se ramener aux cas connus, à ceux des rames sans doublons, ni triplons ni multiplons !

Voilà à quoi servent ces petites règles. A mieux cerner les limites de bien des problèmes rencontrés. Quant à trouver une méthode infaillible et simple pour résoudre ce genre de problème de tri, je ne crois pas que ce soit possible. Il ne devrait pas être bien difficile d'écrire un programme pour calculette scientifique (genre HP49 ou TI ou Casio) capable de résoudre ce genre de problèmes automatiquement. Mais le meilleur algorithme, en l'état actuel des connaissances (les miennes ) serait d'utiliser la "force brute" en testant les différentes configurations successives possibles. Ce n'est pas aussi rocambolesque qu'on pourrait le croire a priori : il n'y a pas tant de configurations que ça d'une part, et il n'est pas difficile d'améliorer cet algorithme pour ne pas tenir compte ou pour éliminer certaines branches dans l'arborescence des possibilités. J'avais envisagé d'écrire un tel programme et j'avais pas mal avancé dans l'élaboration d'un tel algorithme : donc je sais que c'est réalisable. Ce que je ne sais pas, c'est le temps qu'il faudrait à ce programme pour trouver la ou les solutions optimales. Peut-être quelques heures (une calculette n'est pas un PC avec microprocesseur 32 ou 64 bits !) Jai encore la prétension de croire que l'intelligence humaine est supérieure à celle d'une calculette et je me suis dit : l'humain (que je suis encore) ira plus vite que la machine, donnons-lui donc sa chance. Et je n'ai jamais écrit ce progamme (à vrai dire c'est plutôt parce que je suis trop feignasse, mais faut pas le répéter).

Bon, je vois que j'ai encore débordé sur mon temps de parole : je vous retrouve tout à l'heure pour vous proposer un nouveau défi (après l'avoir vaguement évoqué ci-dessus !)

bw

[piko30]

Bonsoir
Alors deux vaillants Participants Joël et Alain
La meilleur réponse est de Joël

Bonne

[bogie-wogie]

à Alain et surtout à Joël puisqu'il a trouvé une meilleure réponse que moi !
Certes j'avais trouvé plusieurs réponses en 10 coups, mais la "meilleure", c'est-à-dire celle déplaçant le moins de ouagons à la fois, en déplaçait quand même 4 à deux reprises alors que la solution de Joël n'en déplace jamais plus de 3. Encore

A titre indicatif, voici quand même ma solution (ne serait-ce que pour montrer des ouagons un peu n'importe où sur les voies du triage, comme promis à dania) :

Je préciserai en outre que selon diverses des petites règles que je m'amuse à établir, il n'est pas possible de résoudre ce problème en moins de 10 manoeuvres. Pour la petite histoire : CEBAD nécessite 7 manoeuvres ; FCEBAD en nécessite 2 de plus (soit 9 en tout) ; et FCEBADG en nécessite encore une supplémentaire, soit pas moins de 10. CQFD

Mais trêve de bavardages. Vous attendez tous le nouveau problème. Alors le voici sans plus tarder !

Oui, vous n'avez pas : il y a bien deux ouagons pour B. Et cela ne facilite pas les choses, malgré les apparences Mais vous allez bien trouver la solution la plus courte en nombre de manoeuvres (je n'en ai qu'une ; y en aurait-il d'autres ? et d'un autre côté je suis confiant : on ne peut pas faire plus court).

Ah oui, je n'ai pas dit en combien de coups : assez facile à trouver si vous suivez attentivement mes propos (ou mes divagations) de plus tôt dans la journée. C'était hier en fait. Déjà ? Mais il est grand temps d'aller

Amusez-vous bien
bw
[Rassurez-vous, le problème de la semaine prochaine sera pire...]

[pierre du rail - 61]

Bonsoir,
-
Moi aussi j'ai participé
Même si je ne suis pas descendu aussi bas que les deux autres
Mais malgré tout je suis content du retour d'Alain

Cordialement.
Pierre

[Jojo37]

Bonsoir à tous.
Bravo à Alain pour s'ètre battu tout comme moi contre le maitre.
J'attends donc les réponses pour lundi prochain concernant le problème,que B.W a voulu un plus difficile en incluant
un wagon en double.
Battons nous pour faire mieux que lui en nombre de manoeuvres,enfin celà n'est pas gagné.
Bonne semaine.