Razveji in omeji

Tehnika Razveji in omeji

- za optimizacijske probleme, npr. minimizacijske

- iščemo neko rešitev x=(x1,x2,...,xn), ki ima najmanjšo ceno: c(x) = min c(y); y je dopustna rešitev

Denimo, da smo v drevesu prišli do nekega xi-1. Torej imamo delno rešitev x1,x2,...,xi-1, ki ima vrednost c(x1,x2,...,xi-1).

Recimo, da vemo, da je vrednost (še neznane) optimalne rešitve manjše ali enako M.

Kako bi to lahko sploh vedeli?

- Če smo že prej našli neko rešitev y1,y2,...,yn lahko tedaj rečemo da M=c(y1,y2,...,yn). Tako vemo, da minimalna rešitev ne bo večja od M.

- Sedaj pogledamo, koliko bi vsak od kandidatov za xi prispeval k ceni c(x1,x2,...,xi-1).

Če se za nekega kandidata ki izkaže, da je M<c(x1,x2,...,xi-1,ki), potem ki gotovo NE vodi k optimalni rešitvi, zato ki opustimo.

Vrednost M potem lahko izboljšamo vsakokrat ko pridemo do nove rešitve!

Zakaj razveji (branch)?

Sestopanje (čisto) je pregledovanje iskalnega drevesa v GLOBINO.

Pri Razveji in omeji (BB) pa lahko pregledujemo tudi v ŠIRINO.

Ko BB doseže neko vozlišče, njegove naslednike (kandidate za nadaljevanje) postavi na seznam čakajočih kandidatov S.

S pa lahko implementiramo kot sklad, vrsto, ...