A megoldás algoritmusai
1. megoldás
Tegyük fel, hogy az első menetben az 1., 2., ..., i. tárgyat égetjük ki. A T égetési időre a következő becslést írhatjuk fel:
T ≥ (az első i tárgy égetési idejének maximuma) + (az (i + 1)., (i + 2)., ..., n. tárgyak optimális elrendezésének égetési ideje).
Meg kell keresnünk azt az i indexet, amire a fenti becslés a legkisebb T értéket adja. A best( i )
függvény fogja kiszámolni az i., (i + 1)., ..., n. tárgy optimális égetési idejét.
Az e[] tömbben tároljuk az égetési időket.
A best() függvény egy ciklusban végigpróbálja, hogy 1, 2, ..., k tárgy elhelyezése esetén milyen optimális égetési idő adódik. Vigyázni kell, hogy nagy indexek esetén kevesebb, mint k tárgy van összesen.
Best(i)
Ha i > n akkor Best := 0
különben
min := -1; max := 0;
v := i + k - 1; Ha v > n akkor v := n
Ciklus j := i-től v-ig
Ha e[j] > max akkor max := e[j]
ido := max + Best(j + 1)
Ha (ido < min) vagy (min = -1) akkor min := ido
Ciklus vége
best := min
Elágazás vége
Eljárás vége
2. megoldás
A feljegyzéses módszer segítségével felgyorsíthatjuk előző megoldásunkat. A múlt órán megismert technikával dolgozunk, egy
cache[] tömbben eltároljuk a már kiszámított
best( i ) értékeket. Ez tényleg gyorsít az algoritmuson, hiszen a
best() függvény sokszor meghívódik ugyanarra az
i paraméterre.
Második lépésben most már azt is szeretnénk tudni, melyik felosztás adja az optimális égetési időt. Ha az i., (i + 1)., ..., n. tárgyak optimális égetésénél első körben az i., (i + 1)., ..., j. tárgyak kerülnek a kemencébe, akkor a
choice[] tömb i. indexű eleme fogja a j értéket tárolni.
Az optimális megoldást az
(1, choice[1]), (choice[1]+1, choice[choice[1]+1]), ...
párok írják le.
Best(i)
Ha cache[i] = 0 akkor
Ha i > n akkor Best := 0
különben
min := -1; max := 0;
v := i + k - 1; Ha v > n akkor v := n
Ciklus j := i-től v-ig
Ha e[j] > max akkor max := e[j]
ido := max + Best(j + 1)
Ha (ido < min) vagy (min = -1) akkor
min := ido
choice[i] := j
Elágazás vége
Ciklus vége
cache[i] := min
Elágazás vége
Elágazás vége
Best := cache[i]
Eljárás vége
Sajnos még nem tökéletes a módszerünk. Ha kiszámoljuk, mennyi memória szükséges a cache[] és choice[] tömbök tárolásához a lehetséges maximális n (10000) esetén, keserű csalódásban lesz részünk. Az égetési idő hosszú egész, a choice elemei egész típusúak kell legyenek, ezért a két tömb alapból lefoglal 60 Kbyte-ot, ami a Pascal lehetőségeinek határát súrolja. Szerencsére a choice[] értékek okosabb kódolásával (abszolút index helyett relatív index) a memóriaigény csökkenthető.
3. megoldás
Tovább tökéletesíthetjük algoritmusunkat, ha észrevesszük, hogy az előző eljárásban a best( ) függvény mindig nagyobb értékű paraméterekkel hívja meg magát rekurzívan. Tehát, ha tároljuk a már kiszámított értékeket, és a maximális indextől indulva csökkenő sorrenben számítjuk ki a
best( i ) értékeket, akkor a rekurzió kiküszöbölhető, egyszerűen egy tömböt kell feltöltenünk.
A best eljárás új változata:
best(i)
min := -1; max := 0
v := i + k - 1; Ha v > n akkor v := n
Ciklus j := i-től v-ig
Ha e[j] > max akkor max := e[j]
ido := max + cache[i+1]
Ha (ido < min) vagy (min = -1)
akkor
min := ido
choice[i] := j;
Elágazás vége
Ciklus vége
cache[i] := min;
Eljárás vége
A főprogram:
cache[n + 1] := 0
Cikus j := N-től 1-ig
best(j)
Ciklus vége
Ki: cache[1]
j := 1
Ki: j, choice[j]
Ciklus amíg choice[j] < n
j := choice[j]+1
Ki: j, choice[j]
Ciklus vége
Megoldások
