Manœuvres et cabotage

par **Aldayo** 25 Fév 2013, 22:52

J'ai effectivement trouvé en 9 coups dès mon premier essai

J'ai ensuite voulu testé plusieurs autres solutions mais en m'éloignant très largement des 9 coups (14/16 coups facile à chaque fois :apero:

)

J'attends donc vos réponses (enfin, si BW nous poste un nouveau exercice, bien entendu :siffle:

)

par **bogie-wogie** 26 Fév 2013, 00:30

Je pourrais en fait continuer et faire toute une ligne de :applause:

pour Aldayo.
La raison ? Je n'avais moi-même que des solutions en 10 coups. :oops:

Donc là, chapeau et encore bravo !

(Je ne vais plus oser porter mon ruban de "Maître" désormais...)
Ceci dit, voici donc un nouveau problème avec retour dans le grand classique.

Détail important : il y a plusieurs solutions possibles (et je ne les ai sans doute pas toutes trouvées) mais il y en a une qui déplace moins de wagons que les autres. Donc : cette fois-ci la fameuse règle "écolo" sur le nombre total de wagons déplacés prendra tout son sens pour départager les ex-aequo ! Songez-y en cherchant vos solutions.

Demain je posterai l'astuce n° 2 (mais elle n'a aucun impact sur le nouveau problème : j'ai pris soin de choisir un problème qui ne l'utilise pas :diable:

)

bw

par **bogie-wogie** 26 Fév 2013, 20:56

Chose promise...

Astuce 2 : tête de rame.

L’une des premières choses à faire lorsqu’on est confronté à une nouvelle rame à trier est d’examiner ses extrémités : la tête et la queue. Dans un premier temps nous ne nous préoccuperons que de la tête. La queue fera l’objet de l’astuce suivante.

Le cas le plus simple et le plus simplificateur est celui où le tout premier wagon est A. Dans ce cas-là la règle absolue est de ne surtout pas dételer ce wagon A de la loco. A aucun moment, quelle que soit la complexité du triage par ailleurs ! Le reste de la rame se trie alors comme une rame comprenant un wagon de moins, et exactement comme la rame équivalente où tous les wagons (sans le wagon A de tête) auraient été dégradés d’un rang. Prenons un exemple parmi les plus simples, la rame ACB.

Pour la trier on va totalement ignorer le A de tête qui va rester attelé à la loco du début à la fin et qui n’interviendra donc pas dans le tri. Il nous reste CB. Ce morceau de rame est en fait équivalent à la rame BA (C est dégradé en B et B en A). En pratique, pour mes petits travaux je prends le point de vue inverse, considérant que C est B élevé d’un rang et que B est A également élevé d’un rang. De façon plus formelle j’écris cela de façon condensée : [CB] = [BA]¹. On peut d’ailleurs étendre ce principe et élever une rame de plusieurs rangs. Ainsi [ED] = [BA]³ et en prenant des exemples plus complexes : [DFEC] = [BDCA]².

Mais oublions le formalisme et la théorie : l’idée de base est que maintenant nous avons une rame beaucoup plus facile à trier. BA se trie en 3 coups, la solution se trouvant en quelques secondes. ACB se triera donc exactement de la même façon, également en 3 coups.

Une petite parenthèse pour les amateurs de la notation par décompte des wagons déplacés (qui nous sera fort utile dans d’autres astuces). La solution pour le triage de BA s’écrit (dans ma notation personnelle) : [BA] = [1-0+1] (oubliez les signes + et – pour l’instant). Le tri de la rame ACB est équivalent à celui de la rame BA décalée d’un rang, sa solution en wagons déplacés, s’écrira donc tout bêtement, c’est-à-dire pratiquement sans réfléchir : [ACB] = [BA]¹ = [1-0+1]¹ = [2-1+2] en ajoutant 1 à chaque valeur de la solution entre crochets. C’est quand même beau le formalisme ! Et ce n’est pas fini…

On a vu le cas où la rame débute par le wagon A. Mais si sa tête est composée d’un groupe de wagons tel que AB ou ABC ? C’est encore mieux. On ne va surtout pas séparer ces wagons (nous verrons d’ailleurs les groupes joints avec l’astuce 4) mais les traiter comme un groupe indissociable et, tout comme le wagon A isolé de tout à l’heure, nous conserverons ce groupe attelé à la loco du début à la fin du tri.

En pratique, notre formalisme nous facilite énormément la tâche. Prenons la rame ABCED. Elle se compose du groupe ABC en tête suivi de ED. Or [ED] = [BA]³ (nous l’avons vu plus haut). ABCED se résoudra donc exactement comme [BA]³ = [1-0+1]³ = [4-3+4]. Et vous pouvez vérifier que c’est la bonne solution.
1. On déplace les 4 wagons ABCE de la voie 0 (de départ) à la voie 1.
2. On ramène les 3 wagons ABC sur la voie 0.
3. On déplace les 4 wagons ABCD de la voie 0 à la voie 1 pour les atteler au wagon E et former la rame triée ABCDE. Fin.

Ces exemples sont simples mais la technique marche à tous les coups, même avec des rames beaucoup plus complexes. Essayez avec ABDGEFC. La première chose à faire est de décomposer en AB+DGEFC puis d’oublier (ou presque) le AB de tête. Il nous reste DGEFC, soit [BECDA]². Le tri de la rame BECDA ne devrait pas soulever trop de difficultés. Sa solution en 5 coups et en notation par wagons déplacés est : [2-1+3-0+1]. On décale de 2, c’est-à-dire qu’on ajoute 2 à chaque étape, et cela donne immédiatement la solution finale à notre petit problème : [4-3+5-2+3]. Pas besoin d’aller chercher plus loin : c’est la solution du tri de la rame complète ABDGEFC qui paraissait si effrayante au départ.

bw

par **bogie-wogie** 03 Mar 2013, 20:31

On continue ?...

Astuce 3 : queue de rame.

Toute rame a deux extrémités et si la tête est d’un intérêt manifeste dans certains cas, la queue ne l’est pas moins dans d’autres cas. En fait il y a un net parallélisme entre les deux extrémités et autant la tête de rame est liée aux wagons « de tête » (A, B…), autant l’extrémité opposée est liée aux derniers wagons. Par convention et pour rester dans le cas général, je note le tout dernier wagon dans l’ordre alphabétique présent dans une rame par la lettre S. L’avant-dernier wagon, quand j’en ai besoin, est alors noté R.

Par exemple, prenant une rame quelconque telle que CEBFAD, le « dernier wagon alphabétique » sera S = F (avec R = E). La valeur réelle de S (et de R) sera donc fonction de la longueur de la rame, mais ce codage nous permet de nous en affranchir et d’étudier des situations dans le cas le plus général.

La première de ces situations, celle qui va nous occuper ici, est le cas de rames où S se trouve en queue de rame, celles-ci pouvant alors s’écrire XS (où X est une rame quelconque ne comportant que des wagons de A à R). C’est très joli tout ce blabla formel, mais ça nous conduit où ? Directement à la règle très simple suivante : lorsque dans une rame le wagon S est en queue, ce wagon S ne doit pas être déplacé et doit rester à sa place du début à la fin du tri.

C’est le pendant (ou équivalent) de la règle concernant le wagon A en tête de rame (voir Astuce 2), wagon qui doit alors rester toujours attelé à la loco. Toute solution qui ignore les règles « A en tête » (dite aussi règle Ta) ou « S en queue » (dite aussi règle Qs) ne peut pas être une solution optimale et nécessitera au moins un déplacement de loco supplémentaire. La démonstration sera pour une autre fois…

Cette règle Qs ou « S en queue » a diverses conséquences importantes. La première est que, la rame à trier étant au départ sur la voie 0 et le wagon S ne quittant jamais cette voie, la rame triée finale se retrouvera nécessairement sur cette voie 0. Ce qui implique un nombre pair de coups.

Cela a à son tour une conséquence directe sur la valeur du « minimum absolu » µ (voir Astuce 1). Tel que présenté, ce minimum (µ = 2g+1) est toujours impair. Or le tri d’une rame XS est toujours pair… Pour une telle rame le minimum absolu vaut donc un coup de plus, soit : µ = 2g+2. Exemple très simple avec la rame BAC (je dirais presque un cas d’école) : il s’agit bien d’une rame de type XS avec X = BA et S = C. D’autre part, si vous vous rappelez l’Astuce 1 vous verrez tout de suite que g=1, donc µ=3, mais comme µ ne peut ici être que pair, on ne pourra pas descendre en dessous de µ=4. Et cette rame ne peut effectivement pas être triée en moins de 4 coups. CQFD

Mais on ne va pas en rester là ! Une autre constatation peut être faite sur le tri d’une rame XS quelconque selon que la rame X se trie en un nombre pair ou impair de coups.

Si la rame X se trie en un nombre pair de coups, son tri se termine alors tout naturellement sur la voie 0, donc directement devant la wagon S. La solution pour trier XS est donc rigoureusement identique à celle qui permet de trier X et s’effectue avec le même nombre (pair) de coups. Exemple pratique : tri de la rame CBDAE. Vous aurez immédiatement déterminé ici que X=CBDA et S=E. Or CBDA se trie en 6 coups (vous pouvez vous amuser à le vérifier… ou à me faire confiance). Pour trier CBDAE il suffit d’appliquer sans réfléchir la solution trouvée pour le tri de CBDA. Là aussi vous pouvez le vérifier.

Si la rame X se trie en un nombre impair de coups, alors il existe toujours au moins 2 solutions optimales semblables (même nombre de coups et même nombre de wagons déplacés en tout). Cela se comprend assez facilement : le fait que X se trie en un nombre impair de coups signifie qu’à la fin du tri la rame se retrouve nécessairement sur l’autre voie que celle de départ. Et comme on veut qu’elle se retrouve sur la voie 0 (celle où est resté notre wagon S) il y a deux possibilités équivalentes : soit on trie X qui va se retrouver sur la voie 1 et qui devra donc être ramenée sur la voie 0 ; soit on déplace d’abord la rame X sur la voie 1 puis on la trie de façon à ce que la rame triée se retrouve à la fin directement sur la voie 0.

J’entends quelqu’un réclamer un exemple, alors le voici, reprenant la rame basique (ou cas d’école) BAC. Nous savons, parce que nous l’avons déjà déterminé, qu’elle se trie en 4 coups. Mais comment ? Le wagon C restant fixe et immuable, nous n’avons à nous préoccuper que de la rame X=BA.

Première méthode : on la trie normalement en 3 coups (1 = wagon B de voie 0 à voie 1 ; 2 = retour de la loco sur voie 0 ; 3 = wagon A de voie 0 à voie 1 pour former la rame AB). Il ne reste plus (coup 4) qu’à ramener notre rame AB de la voie 1 à la voie 0, devant le wagon C qui attend patiemment.

Deuxième méthode : on transfère toute la rame X=BA de la voie 0 à la voie 1 puis on effectue le tri à partir de là, toujours en 3 coups, ce qui, avec le transfert initial, nous donne là encore un total de 4 coups. Ce raisonnement, illustré par un cas très simple, reste tout à fait valable quelle que soit la complexité de la rame X.

Deux petites remarques additionnelles pour clore ce chapitre.

La première est que dans le cas où X se trie en un nombre impair n de coups la méthode décrite ci-dessus donnera bien deux solutions en (n+1) coups pour trier XS (et cela pour chaque solution de X : si X se trie selon plusieurs solutions, chacune de ces solutions donnera deux nouvelles solutions pour XS). Mais elle ne donnera pas nécessairement toutes les solutions. Il y a le cas (pas si rare que ça) où il existerait également une ou des solutions pour trier X en (n+1) coups. Si n est impair, (n+1) est pair et on retombe dans la première configuration décrite plus haut, c’est-à-dire que cette ou ces solutions trient également XS en (n+1) coups. Il y a même des cas où une telle solution déplace globalement moins de wagons que les solutions obtenues à partir du tri de X en n coups (n impair). Un peu confus tout ça ? un exemple…

Prenons la rame BDACE. Vous connaissez le truc à présent : X=BDAC et S=E. La rame BDAC se trie en 5 coups que je décrirai, pour abréger, en nombre de wagons déplacés, à savoir : [BDAC] = [2-0+1-2+3]. Les deux solutions pour BDACE sont alors obtenues facilement en rajoutant le déplacement des 4 wagons BDAC/ABCD, soit devant, soit derrière le tri de BDAC, ce qui donne : [4-2+0-1+2-3] et [2-0+1-2+3-4]. Chacune de ces solutions en 6 coups nécessite le déplacement de 12 wagons. Mais BDAC peut aussi se résoudre en 6 coups (au lieu de 5, raison pour laquelle cette solution plus longue est souvent négligée). Il s’agit, toujours sous forme de liste de nombres de wagons déplacés, de [3-1+2-3+0-1] et cette solution, non seulement est parfaitement utilisable telle quelle pour trier BDACE, mais en outre elle ne déplace que 10 wagons (au lieu de 12) : c’est donc visiblement la meilleure solution !

La deuxième remarque est que, tout comme pour la règle « A en tête » nous avions étendu le raisonnement aux cas où « A » est en fait un groupe de deux ou plusieurs wagons (AB, ABC, etc.) le même principe vaut pour la règle « S en queue » lorsque S est pris dans un sens élargi avec des groupes tels que RS, QRS, etc. L’exemple le plus simple est la rame BACDE où X=BA et S=CDE. C’est l’ensemble CDE qui restera donc immobilisé et le tri de la rame complète BACDE sera rigoureusement identique à celui de BAC, vu plus haut. En fait cette extension d’une règle aux groupes de deux ou plusieurs wagons n’a rien de surprenant et suit entièrement les principes qui sont examinés dans l’Astuce 4 sur les groupes joints.

bw

par **Aldayo** 04 Mar 2013, 11:17

Vous avez jusqu'à ce soir pour m'nevoyer vos solutions !!

J'ai n'en est reçu qu'une pour le moment !

par **bogie-wogie** 05 Mar 2013, 01:29

Toujours pas de résultat annoncé ? Pour moi ça va bientôt être :dodo:

Je dois me lever tôt demain matin (tout à l'heure, plutôt...)

Alors pour les impatients, afin qu'ils puissent d'ores et déjà commencer à réfléchir, voici le problème de la semaine :

Il est délibérément choisi pour utiliser ou appliquer les "astuces" décritent plus haut, ces derniers jours. Au vu des commentaires, il n'y en a certainement pas beaucoup qui les ont lues : il est encore temps...

Je préciserai que les trois "astuces" décrites sont utiles. Elles ne vous donneront pas la solution, loin de là (et ça n'aurait alors plus aucun intérêt), mais elles peuvent considérablement vous aider en limitant ou orientant l'étendue de vos recherches pour la solution optimale. Méfiez-vous toutefois : il y a un piège :diable:

(sinon ce serait trop facile). Mais lui aussi est mentionné des les "astuces"... Je n'en dirai pas plus si ce n'est qu'il y a plusieurs solutions et que seule compte la plus écolo (celle déplaçant au total le minimum de wagons).

A vos crayons !

bw

par **Aldayo** 05 Mar 2013, 10:27

Méa coulpa, j'ai encore zappé hier soir (couché tôt) :siffle:

Notre gagnant est donc Jojo37 (en 9 coups) par forfait des autres :evil:

Je vais donc m'attaquer au nouveau problème :mrgreen:

par **bogie-wogie** 05 Mar 2013, 10:44

Un seul participant... mais qui n'a pas démérité ! Un grand :applause:

à Jojo37, donc.
Et c'est à lui que reviendra la lourde tâche de recevoir vos suggestions pour le problème que je vous ai soumis hier.

Une petite dernière remarque à propos de la solution de Jojo37 : je n'ai pas mieux que 9 coups, mais il existe plusieurs solutions et la sienne, avec 31 wagons déplacés au fil de ces 9 coups, n'est pas la plus "écolo". En voici une qui ne déplace que 25 ouagons...

Je dis ça, c'est surtout pour frimer un peu et surtout pour me consoler (venger serait plus approprié !) de m'être fait griller lors du problème précédent :diable:

bw