Razvrščanje programskih enot na magnetni trak

Iz MaFiRaWiki

UVOD:
Podanih je n programskih enot z dolžinami l1,l2,...,ln.
Zapisati jih želimo na magnetni trak v takšnem zaporedju, da bo povprečen čas branja ene progrmaske enote najmanjši.
PREDPOSTAVKE:
Ko končamo brati programsko enoto, moramo brati vse od začetka traku do konca želenega traku.
Trak se pomika s konstantno hitrosotjo c.
Verjetnost, da bo treba brati programsko enoto i, je enaka pri vseh i.
PROBLEM:
Naj bodo programske enote na traku v zaporedju i1,i2,...,in.

l_{i_{1}} l_{i_{2}} ... l_{i_{j}} ... l_{i_{n}}

Da preberemo j-to programsko enoto (programsko enoto ij) moramo prebrati vse pred njo, zato je čas za branje j-te programske enote sorazmeren vsoti l_{i_{1}}+...+l_{i_{j}}:
t_{j}=c \sum_{k=1}^{j}l_{i_{k}}
Naj bo pj verjetnost, da bo zahtevano branje j-te programske enote.
Pričakovani čas za branje ene programske enote je torej:
t'= \sum_{j=1}^{n}(p_{j} \cdot t_{j})
Po predpostavki je p_{j}= \frac{1}{n} za vsak j:
t= \frac{1}{n} \sum_{j=1}^{n}t_{j}= \frac{c}{n} \sum_{j=1}^{n} \sum_{k=1}^{j} l_{i_{k}}
t je povprečen čas za branje ene programske enote
NALOGA:
Poiskati moramo zaporedje i1,i2,...,in, ki minimizaira t.
IDEJA:
Krajše programske enote naj bodo na začetku.
Rešitev je zaporedje i1,i2,...,in, za katerega je:
l_{i_{1}} \leq l_{i_{2}} \leq ... \leq l_{i_{n}}
ZAKLJUČEK:
Algoritem je požrešen, ker k že zapisanim programskim enotam vedno ”požrešno” dodamo najkrajšega med preostalimi.

Osebna orodja