A Vasút feladat megoldása
a 21. és 22. szakkör résztvevőinek és tanárainak ötletei alapján
Speciális ötletek
A feladat elemzése során hasznos megállapításokat tehetünk.
Részsorozatok
Ha vesszük a B vágányon lévő (bejövő) vagonokat, és néhányat elhagyunk közülük, akkor a maradék vagonok az eredeti vagonok egy részsorozatát alkotják. Megállapítható, hogy:
- Ha a bejövő vagonok között szerepel az 2 3 4 1 részsorozatként, akkor nem lehet őket rendezni.
- Ha a bejövő vagonok között szerepel a 3 2 4 3 1 4 2 részsorozatként, akkor nem lehet őket rendezni.
- Nyitott kérdés: ha nem szerepel az előbbi két részsorozat, akkor biztosan lehet-e a vagonokat jól rendezni?
Más heurisztikák
Gyakran egyéretlmű, hogy a következő vagont melyik vágányról melyik vágányra kell irányítani, vagy legalábbis kizárhatóak olyan vagonmozgatások, amiket megtéve lehetetlenné válik a rendezés befejezése.
Ilyen meggondolások használatával lehetséges, hogy készíthető olyan megoldás a feladathoz, ami egészen kevés vagon-mozgatás kombinációjának végignézésével eldönti, hogy rendezhető-e egy vagonsorozat.
Egy nem működő ötlet
A vagonokat sorban vesszük a B vágányon. A rendezés során, ha bármelyik vagonról (B,C vagy D vágányon) kiderül, hogy mehet az A vágányra, mert nincs már nála kisebb sorszámú a B vágányon, akkor azonnal átmozgatjuk az A-ra. Egyébként pedig C-re vagy D-re mozgatjuk a B-n lévő következő vagont:
- 1. eset: Ha C végén és D végén is kisebb számmal jelölt vagon van, mint a B végén, akkor feladjuk, és kijelentjük, hogy ezeket a vagonokat nem lehet rendezni.
- 2. eset: Ha C és D közül pontosan az egyiken van csak nemkisebb számú vagon, mint a B végén, akkor B-ről erre a vágányra mozgatunk.
- 3. eset: Ha lehet választani C és D közül, akkor oda mozgatunk, amelyiknek a végén nagyobb számmal jelölt vagon van.
A 3. eset kezelésével van a probléma, ugyanis C és D vágányoknak csak a legelső vagonjait vettük figyelembe, pedig a többi is számít. Különösen ha az első vagonok száma megegyezik. Ellenpélda: TODO.
Általános ötlet: dinamikus programozás
Jelölések
A vasútállomás egy állapotát a vágányokon lévő vagonok felsorolásával fogjuk leírni. Pl.:
| 1. állapot | 2. állapot | 3. állapot | 4. állapot | 5. állapot | 6. állapot | 7. állapot |
| A:
B: 1 2 3 2 4
C:
D: |
A: 1
B: 2 3 2 4
C:
D: |
A: 2 1
B: 3 2 4
C:
D: |
A: 2 1
B: 2 4
C: 3
D: |
A: 2 2 1
B: 4
C: 3
D: |
A: 3 2 2 1
B: 4
C:
D: |
A: 4 3 2 2 1
B:
C:
D: |
A táblázat első oszlopa a feladat első példabemenetét mutatja. Minden betű egy vágányt jelképez. A betű utáni számsorozat a vágányon lévő vagonokat sorolja fel, balról jobbra az első vagontól. Így mindig a balszélső vagont lehet elvenni és a balszélre lehet új vagont helyezni.
Kezdetben tehát a B. vágányon vannak a vagonok, és ezeket kell sorbarendezve átjuttatni az A. vágányra, méghozzá növekvő sorrendben berakva őket. Így a bevezetett jelölés szerint ezek a vagonok csökkenő sorrendben fognak látszani.
A táblázat további oszlopai a vagonok rendezésének a lépéseit mutatják.
Vagonok a C és D vágányokon
Könnyű belátni, hogy a C és D vágányokra csak nemcsökkenő sorrendben érdemes rakni a vagonokat. Ellenkező esetben nem tudunk majd róluk jó sorrendben átpakolni az A-ra. Például:
| Innen lehetséges a befejezés | Innen nem lehetséges a befejezés |
| A:
B:
C: 1 1 1 2 2 3 3 3 4 4
D: |
A:
B:
C: 1 1 2 2 3 1 3 3 4 4
D: |
A feladat tömörítése
Vegyük észre, hogy a feladat megoldásának a szempontjából az egymást követő azonos számmal jelölt vagonok egy vagonnak vehetők. Az ilyen vagonokat ugyanis mindig együtt érdemes mozgatni, pontosabban nem nyerhetünk vele, ha szétrakjuk őket több helyre. Például a következő táblázatban az X és Y állapotok azonosak a feladat befejezhetőségét tekintve:
| X állapot | Y állapot |
| A: 1 1 1
B: 2 2 2 2 2 4
C: 3 3 3 4 4 4
D: 2 2 2 |
A: 1
B: 2 4
C: 3 4
D: 2 |
Továbbá az is igaz, hogy az A vágányon lévő vagonok közül csak az elsőnek a száma számít, az utána következőkkel már semmit sem kell csinálni, és nincs befolyásuk semmire. Például az X és Y állapotok a következő esetben is azonosak a befejezhetőséget tekintve:
| X állapot | Y állapot |
| A: 2 3 3 3 4 4 4
B: 2 4
C:
D: |
A: 2
B: 2 4
C:
D: |
Az állomás állapota
Az előző két bekezdés észrevételei lehetővé teszik, hogy az állomáson lévő vagonok elhelyezkedését, tömören jellemezzük, de úgy, hogy nem vész el információ a feladat megoldhatóságáról. Tehát, az állomás állapota a következő változókkal jellemezhető:
- A: 1..4 szám, az A vágány elején lévő vagon száma
- C[i] ($1 \leq i \leq 4$) található-e i. számmal jelölt vagon a C vágányon. C tehát négy boolean típusú változó tömbje. Ez a négy boolean már elég jellemzést ad a C vágányról, hiszen kocsik csak nemcsökkenő sorrendben lehetnek, az ismétlődések pedig nem számítanak.
- D[i] ($1 \leq i \leq 4$) található-e i. számmal jelölt vagon a D vágányon, C[i]-hez hasonlóan.
Dinamikus programozás alapú megoldás 1.
A hatékony megoldás kulcsa az, hogy az állapot, és a B vágányon következő vagonok ismeretében eldönthető, hogy rendezhetők-e a vagonok.
Rendezhető(A, C, D, B) =
Ha B Üres Akkor
Rendezhető := Igaz;
Különben
Rendezhető := Hamis;
Ciklus Amíg (végig nem próbáltuk az összes esetet)
A2, C2, D2 := következő lehetséges új állomás állapot, amit úgy kapunk,
hogy B[1]-et átmozgatjuk A, C és D vágányok valamelyikére
előtte/utána C-ről és/vagy D-ről is mozgathatunk vagonokat A-ra
Ha Rendezhető(A2, C2, D2, B[2..n]) Akkor
Rendezhető := Igaz;
Ciklus vége
Elágazás Vége
Az összes eset végigpróbálása természetesen nem egyszerű, később még visszatérünk rá. (A Egy állapotból következő állapotok meghatározása fejezetben.)
Egyelőre tegyük fel, hogy ez már megvan, és dolgozzuk ki a program főbb struktúráját.
Néhány technikai módosítással láthatóvá válik, hogyan alkalmazhatjuk a DP-t.
- A
B paraméter helyett alkalmazzunk egy pos paramétert, ami azt adja meg, hogy hányadik pozíciójánál tartunk a B tömbnek.
C és D tömböket tároljuk egy-egy 4 bites számban, ahol az i. bit a tömb i-edik elemének felel meg.
Így a Rendezhető függvényt a következő módon írhatjuk újra:
Rendezhető(A, C, D, pos) =
Ha Pos > M Akkor
Rendezhető := Igaz;
Különben
Rendezhető := Hamis;
Ciklus Amíg (végig nem próbáltuk az összes esetet)
A2, C2, D2 := ...
Ha Rendezhető(A2, C2, D2, Pos+1) Akkor
Rendezhető := Igaz;
Ciklus vége
Elágazás Vége
Így a rekurzió gyorsítására felvehetünk egy r[A][C][D][pos] négydimenziós tömböt, ami a Rendezhető függvény már kiszámolt értékeit tárolja.
Rendezhető(A, C, D, pos) =
Ha r[A][C][D][pos] még nincs kitöltve
Lefut a függvény az előbbiekben vázolt módon
r[A][C][D][pos] := Rendezhető;
Elágazás Vége
Rendezhető := r[A][C][D][pos];
Mivel az r tömbnek minden elemét csak egyszer töltjük ki, ezért a fenti algoritmus futásideje r méretével becsülhető: $4 \cdot 16 \cdot 16 \cdot 1000 $ A memóriaigény viszont csökkenthető, ha észrevesszük, hogy az r[*][*][*][pos] típusú elemek kizárólag csak az r[*][*][*][pos+1] típusú elemektől függenek. Kitölthető tehát ez a tömb balról jobbra is, és ráadásul pos-t tekintve mindig csak két egymást követő szeletére lesz szükségünk, elég csak őket a memóriában tartani.
Másik megoldás, a DP alapötletéből kiindulva
Alapfelépítés
Képzeljük el, hogy miközben vesszük sorra a B vágányon lévő vagonokat, követjük az állomás összes lehetséges állapotát. Úgy is vehetjük, hogy van egy halmazunk, ami azokat a lehetséges állapotokat tárolja, amik B eddig végignézett vagonjainak a rendezése után lehetségesek. Pontosabban, korlátozzuk a halmazban tárolható állapotokat azokra, amik nem triviálisan rosszak (pl.: A = 3, C[1] = true), vagyis még lehetséges belőlük a befejezés.
Kezdetben az állapotok halmaza egyelemű, és csak az üres (A = 1, C[i] = D[i] = false) állapotot tartalmazza. Amikor vesszük a B-ből a következő vagont, akkor minden a halmazban lévő állapotra meghatározzuk, hogy ennek a vagonnak a behelyezésével (és mellette más bentlévő vagonok esetleges áthelyezésével) milyen új nem-rossz állapotokba juthatunk. Ha ezzel elkészültünk, akkor kiürítjuk a halmazt, és belehelyezzük az összes újonnan meghatározott állapotot. Így ha az utolsó vagon feldolgozása után legalább egy állapot maradt a halmazban, akkor megoldható a rendezés. Ha pedig üres halmazhoz jutottunk, akkor nem.
Az állapotok halmazát tárolhatjuk egy r-hez hasonló tömbben: halmaz[A][C][D]. Pontosabben kettőre lesz szűkség:
Megold()
halmaz1[*][*][*] := Hamis;
halmaz1[1][0][0] := Igaz;
Ciklus i:= 1-től M-ig
halmaz2[*][*][*] := false;
Ciklus A:= 1-től 4-ig:
Ciklus C:= 0-től 15-ig:
Ciklus D:= 0-től 15-ig:
Ha halmaz1[A][C][D] Akkor:
Következők(A, C, D, B[i]);
Csere(halmaz1, halmaz2);
Ciklus Vége
A Következők(A, C, D, vagon) tehát a halmaz2-ben fogja bejelölni az elérhető állapotokat, tahát halmaz2-nek globális változónak kell lennie.
Egy állapotból következő állapotok meghatározása
Minden lehetséges átmenet leírható két lépésben: (TODO: biztosan?)
- lépés: az összes X számmal, és X-nél kisebb számmal jelölt vagon bemozgatása A-ba ($X \in \{1,2,3,4\}$)
- lépés: a soron következő vagon bemozgatása az Y vágányra ($Y \in \{A, C, D\}$)
Tehát X és Y függvényében ez legfeljebb 12 lehetséges mozgatást jelent. Azért legfeljebb, mert kaphatunk eredményül rossz állapotokat is.
Következők(A, C, D, vagon)
Ciklus X := A-től 4-ig:
A := X;
C[X] := false; D[X] := false;
Ha vagon >= A Akkor:
halmaz2[vagon][C][D] := Igaz;
Ha vagon <= legkisebb(C) Akkor:
halmaz2[A][ C+(vagon bitje) ][D] := Igaz;
Ha vagon <= legkisebb(D) Akkor:
halmaz2[A][C][ D+(vagon bitje) ] := Igaz;
Elágazás Vége
Ciklus Vége
Eljárás Vége
Legkisebb(Vágány)
Ciklus Amíg (i < 4) és (Vágány[i] = Hamis)
i:= i + 1;
Ciklus Vége
Legkisebb := i;
Eljárás Vége
Egy ehhez hasonló függvény használható a feladat dinamikus programozásos megoldásához is.
Eredmény
Ha az utolsó iteráció után van Igaz érték a halmaz1 tömbben, akkor a válasz IGEN, mert csak olyan állapotokat vettünk fel, amik nem tartalmaznak eleve ellentmondást, ilyenekből pedig befejezhető a rendezés. Ha nincs Igaz érték a halmazban, akkor a válasz NEM.
További lehetséges optimalizáiók
A megadott tesztadatokkal a programunk elég gyors lesz, de azért lehet még gyorsítani rajta...
- C és D tömbökben elég csak három boolean tárolása, hiszen 1-es vagonokat úgy sem akarunk a C vagy D vágányokon tárolni.
- C és D szimmetriájának a kihasználása.
Forráskódok
