Rangeer algoritme

[peter1984]

Voor school hebben we een opdracht gekregen om via een simulator (gemaakt door een andere opleiding binnen de school) een treinspoor te maken en op dit spoor een aantal treintjes te laten rijden.

Nu moet het ook mogelijk zijn om een trein te laten rangeren. In ons baanontwerp zijn 4 rangeer sporen en op 3 sporen staan elk 3 wagons (genumerd 1 t/m 9). nu moet er een invoerveld komen waarin je 3 willekeurige cijfers (1 t/m 9) kan invoeren en dan moet de trein de wagons in deze volgorde oppikken.

Voor dit onderdeel bestaat er een algoritme, nu heb ik al vollop gegoogled en heb wel het een en het ander gevonden over het Shunting Yard Algoritme, maar het is me niet echt duidelijk wat het doet.

Kan iemand mij meer vertellen over welke algoritmes er gebruikt kunnen worden voor het rangeren of meer informatie geven over het shunting algoritme.

Alvast hartelijk bedankt.

[Michiel2]

 Hier alvast mijn favoriet:

 "brute-force"-algoritme

 1. Doe een willekeurige rangeerbeweging
 2. Controleer of de huidige situatie overeenkomt met de gewenste eindstand
 3. Ga naar punt 1

 Aangezien een modelbaan toch draait om treintjes heen en weer rijden, zou ik willen argumenteren dat dit het meest efficiente algoritme is; je hebt er namelijk verreweg het meeste plezier van.

[Han Zijlstra]

misschien hier es kijken?
http://www.wymann.info/ShuntingPuzzles/index.html

[Lokpaint]

Pffffffffff...

Niks beters te doen

Bart

[Patrick Smout]

Peter,

Met het "Shunting algorithm" wordt meestal verwezen naar een algoritme van Dijkstra dat gebruikt wordt voor infix notatie om te zetten naar postfix, zoals gebruikt wordt bvb. door een HP zakrekenmachine ( 1 + 2 wordt dan 1 2 + ). Buiten het feit dat het algoritme gebruik maakt van een stack zal dit je niet veel verder helpen.

Is er in de opgave een beperking opgelegd voor het aantal wagons op een rangeerspoor?

Eenvoudigste algoritme dat ik zie is:

1° Bepaal op welk spoor de volgende wagon staat.
2° Verplaats alle wagons die ervoor staan naar andere rangeersporen
3° *** de wagen op
4° Herhaal al de vorige stappen tot de trein samengesteld is.

Algoritme heeft het nadeel dat het niet vooruitkijkt, m.a.w. door het behandelen van 1 wagon en het lukraak verplaatsen naar ander sporen zal je extra rangeerbewegingen introduceren.

Je kan het algoritme makkelijk verbeteren door:

In stap 3 te kijken of er indezelfde rij eventueel de  eerst volgende wagen is die tot de samengestelde trein behoort. In principe kan je dan alle wagens m.u.v. de eerstvolgende gelijk meenemen, en dan de tussenliggende verwijderen (omgekeerde bewerking) door ze neer te zetten op andere sporen.

Vermijd ook dat je wagens wegzet op rangeer sporen waar nog wagens staan die je later moet ophalen of, zeker, dat je de volgorde omkeert door het verzetten van wagens. Kost je extra rangeerbewegingen. Je kan hiervoor scores opstellen per beweging en een totaalscore per rangeerspoor. Het rangeerspoor dat het beste scoort is dan de kandidaat om de wagens aan te nemen.

Verder kan je ook nog de staart van de trein samenstellen op een spoor (van achter naar voor) waar geen wagons meer staan die tot de uiteindelijke trein behoren. Zo heb je als het ware twee deeloplossingen die naar elkaar toegroeien.

Ander algoritme dat voldoet aan de opgave is als volgt (maar minder algemeen) en gaat ervan uit dat er geen beperking is in de lengte.

1° Haal alle wagons op van alle rangeersporen en vorm met alle wagons van alle rangeersporen 1 lange trein
2° Splits nu de trein en verdeel deze over 3 rangeersporen zodat de gewenst wagons (max. 4) als 1e op een rangeerspoor staan.
3° Stel vervolgens de definitieve trein samen door in de juiste volgorde de 1e wagon van elk rangeerspoor te nemen

Variante hierop is

1° Haal alle wagons op van alle rangeersporen behalve diegene die achter de laatste wagon staan die moet behoren tot de definitieve trein en vorm hiermee een lange trein (duidelijk?)
2° Verdeel vervolgens over de rangeersporen zoals hierboven.


mvg,

Patrick Smout

[René]

Is het niet de bedoeling dat je hiervoor zelf iets moet bedenken?

Of worden de problemen in de toekomst ook opgelost met copy/paste?

[Ronald Halma]

Duizel, duizel, duizel......

We zijn toch treintjesbouwers, geen wiskundigen??  :-|  

[Patrick Smout]

En dat is nu net het mooie aan deze hobby ... zo veelzijdig dat eenieder er zijn gading in vindt. 
Overigens zijn (model-)treinen voor veel wiskundigen interessant studiemateriaal omdat je in de treinbewegingen heel wat uitdagingen kan tegenkomen. Wat denk je bvb. van een computer programma voor onderstaande puzzel op te lossen? Of meer algemeen, hoe kan je voorkomen dat treintjes zich *blok*vast rijden? Onderstaande puzzel is voor mensen makkelijk op te lossen, voor een computer ligt dat al heel wat moeilijker. Het routing algoritme in de besturingssoftware van mijn baan kan ondermeer met dit soort problemen overweg zonder dat je manueel eventuele deadlock situaties moet aangeven. Heeft me echter wel heel wat uurtjes gekost om het zover te krijgen maar als je het dan in praktijk ziet werken is het voor mij de slagroom op de taart.



mvg,

Patrick Smout

[peter1984]

He mensen,

Bedankt voor jullie reacties, vooral de link naar de shunting puzzles is nuttig!
En heb je een andere oplossing of meer info dan is dat altijd welkom natuurlijk.