Algoritmi/Pretraživanje usponom

Metoda pretraživanja usponom je tehnika koja se koristi za određene klase optimizacionih problema. Ideja je da se krene od sub-optimalnog rešenja problema (npr., početi u podnožju uspona) i zatim ponavljanjem poboljšavati rešenje (šetnja uz uspon) dok neki uslov ne bude maksimizovan (dok se ne dođe do vrha uspona).

Metoda pretraživanja usponom

Konstruisati sub-optimalno rešenje koje je u saglasnosti sa ograničenjima problema
Uzeti rešenje i poboljšati ga
Ponavljati drugi korak dok god je dalje poboljšavanje rešenja moguće/potrebno

Jedan od najpopularnijih problema pretraživanja usponom je problem protoka mreže. Iako protok mreže može zvučati specifično, važan je jer ima visoku ekspresivnu moć: na primer, mnogi problemi sa algoritmima sa kojima se susrećemo u praksi se mogu smatrati kao posebni slučajevi protoka mreže. Nakon što smo prikazali jednostavan primer pristupa pretraživanju usponom za numerički problem, prikazaćemo protok mreže a zatim ćemo dati primere aplikacija protoka mreže.

Njutnov metod nalaženja korena

Ilustracija Njutnove metode: Nula f(x) funkcije je u x. Vidimo da je pretpostavka x_n+1 bolja pretpostavka od x_n ,jer je bliža x. (iz Wikipedia)

Njutnov metod nalaženja korena je algoritam star tri veka, koji služi za nalaženje numeričkih aproksimacija korenova funkcije (to su tačke $x$ gde funkcija $f(x)$ postaje nula), počevši od inicijalne pretpostavke. Za ovaj algoritam je potrebno poznavati funkciju $f(x)$ i njen prvi izvod $f'(x)\,$ . Ideja je sledeća: u blizini početne pretpostavke $x_{0}$ možemo formirati Tejlorov red funkcije:

f(x)=f(x_{0}+\epsilon )\,

\approx f(x_{0})+\epsilon f'(x_{0})

+{\frac {\epsilon ^{2}}{2}}f''(x_{0})+...

Koji daje dobru aproksimaciju funkcije u okolini x0. Uzimajući samo prva dva člana izraza sa desne strane jednačine, izjednačavajući ih sa nulom i rešavajući po epsilon, dobijamo:

\epsilon =-{\frac {f(x_{0})}{f'(x_{0})}}

Koje možemo koristiti za konstrukciju boljeg rešenja:

x_{1}=x_{0}+\epsilon =x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}.

Ovo novo rešenje može biti početni položaj za ponovnu primenu ove procedure. Tako, uopšteno, bolja aproksimacija može se konstruisati ponavljanjem sledećeg izraza:

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.

Kao što je prikazano na slici, ovo nije ništa više nego konstrukcija nule iz tangente funkcije u tački početne pretpostavke. Uopšteno, Njutnov metod nalaženja korenova konvergira kvadratno, osim kada prvi izvod rešenja $f'(x)=0\,$ nestane u korenu. Po analogiji sa metodom pretraživanja usponom, Njutnov metod nalaženja korenova možemo primeniti ne na funkciju $f(x)\,$ , već na njen prvi izvod $f'(x)\,$ , tj. tražimo $x$ tako da je $f'(x)=0\,$ . Ovo će dati eksterne pozicije funkcije, njene maksimume i minimume. Na ovaj način, inicijalizacijom Njutnovog metoda dovoljno blizu maksimuma, penjemo se uz uspon.

Primer aplikacije Njutnovog metoda

Funkcija neto trenutne vrednosti je funkcija vremena, kamate i serija tokova keša. Srodna funkcija je interna povratna rata. Formula za svaki period je (CF_i x (1+ i/100) ^t, i ovo će da da polinomijalnu funkciju koja predstavlja ukupan protok keša, i koja je jednaka nuli kada je kamata jednaka IRR. Prilikom korišćenja Njutnovog metoda, x je kamata, y je ukupan protok keša, i metod će da koristi derivat polinomijalne funkcije nađe nagib grafika za zadatu vrednost kamate (vrednost x), koji će dati tačku x_n+1, tj. bolju vrednost kamate za sledeću iteraciju, dok se ne dođe do one vrednosti x za koje je y=0. Osim kontinualnih funkcije, metoda pretraživanja usponom se može primeniti i na diskretne mreže.

Protok mreže

Pretpostavimo da imamo usmeren graf (sa mogućim ciklusima) sa jednim čvorom označenim kao izvor i drugim čvorom označenim kao destinacija ili 'lavabo'. Izvorni čvor ima samo izlazne ivice. Slično, čvor destinacije ima samo ulazne ivice. Možemo pretpostaviti da je graf potpuno povezan, bez mrtvih krajeva; npr. za svaki čvor (osim izvornog i krajnjeg), postoji bar jedna ivica koja ulazi u njega i bar jedna ivica koja izlazi iz njega. Svakoj ivici dodeljujemo „kapacitet“, i na početku razmatramo samo kapacitete sa integralnim vrednostima. Sledeći graf je u skladu sa navedenim zahtevima:

Zamislićemo da imamo serije ulaza koji stižu na ulazni (izvorni) čvor, koje bismo voleli da propagiramo ivicama grafa do izlaznog čvora (čvora destinacije). Broj jedinica koje možemo da prenesemo preko jedne ivice u nekom trenutku mora biti manji ili jednak kapacitetu te ivice. Možemo da posmatramo čvorove kao gradove i ivice kao puteve između njih, i zadatak nam je da pošaljemo što veći brij automobila od iszvornog grada u grad destinacuju. Ograničenje je to da nekim putem ne možemo poslati više automobila nego što ja kapacitet tog puta. Cilj protoka mreže je da se pošalje maksimalan saobraćaj od s do t koji svaka ulica može da podnese. Kako bi se organizovale saobraćajne rute, možemo napraviti listu različitih putanja od grada $s$ do grada $t$ . Svaka putanja ima kapacitet jednak najmanjem kapacitetu svih ivica koje pripadaju toj putanji; na primer, posmatrajmo sledeću putanju $p$ :

Iako poslednja ivica putanje $p$ ima kapacitet 8, tom ivicom ide samo jedan automobil, jer prethodna ivica ima kapacitet 1 (pa je ta ivica u punom kapacitetu). Nakon korišćenja ove putanje, možemo da izračunamo rezidualni graf tako što ćemo da odudmemo 1 od kapacitet svake ivice:

(Oduzimamo 1 od kapaciteta svake ivice iz putanje p jer je kapacitet putanje $p$ jednak 1.) Možemo reći da p ima protok 1. Formalno, protok je dodela $f(e)$ vrednosti skupu ivica grafa $G=(V,E)$ takva da važi:

1.

\forall e\in E:f(e)\in \mathbb {R}

2.

\forall (u,v)\in E:f((u,v))=-f((v,u))

3.

\forall u\in V,u\neq s,t:\sum _{v\in V}f(u,v)=0

4.

\forall e\in E:f(e)\leq c(e)

Gde je $s$ izvorni (ulazni) čvor, a $t$ izlazni (čvor destinacije) čvor, i $c(e)\geq 0$ je kapacitet ivice $e$ . Vrednost protoka $f$ definišemo na sledeći način:

{\textrm {Value}}(f)=\sum _{v\in V}f((s,v))

Cilj protoka mreže je da se nađe f takvo da je ${\textrm {Value}}(f)$ maksimalno. Ovo znači da ne postoji ni jedna druga dodela protoka koja je u skladu sa ograničenjima 1-4 da ima veću vrednost protoka. Na primeru saobraćaja ćemo demonstrirati šta znače ova 4 ograničenja:

$\forall e\in E:f(e)\in \mathbb {R}$ . Ovo pravilo definiše protok kao realnu funkciju ivica. Funkcija je definisana za svaku ivicu grafa. Ova funkcija se može posmatrati kao prosto mapiranje. Svaka # $\forall (u,v)\in E:f((u,v))=-f((v,u))$ . Ovo pravilo kaže da ako ima saobraćaja koji ide od čvora u do čvora v, onda se saobraćaj od v do u smatra njegovim negativom. Na primer, ako dva automobila idu od grada u do grada v, onda -2 automobila idu u suprotnom smeru. Slično, ako 3 automobila idu od grada u do grada v i 2 automobila idu od grada v do u, efekat je isti kao da jedan automobil ide od grada u do grada v i nijedan od grada v do grada u.
$\forall u\in V,u\neq s,t:\sum _{v\in V}f(u,v)=0$ . Ovo pravilo kaže da pi mrežni protok, osim za ulazni i izlazi čvor trebalo da bude neutralan. To znači da nikada više automobila neće ići u neki gradi nego što će izlaziti iz nekog grada. Novi automobili mogu samo doći iz ulaznog čvora i automobili se samo mogu zaustavljati u izlaznom čvogu. Slično, šta god potekne iz s mora doteći u t. Primetimo da, ukoliko neki grad ima 3 automobila koji dolaze u njega, on može poslati 2 automobila u jdan grad i automobil u neki drugi grad. Takođe, u neki gradi automobili mogu dolaziti iz više različitih gradova ( mada su svi došli iz s).
$\forall e\in E:f(e)\leq c(e)$ .

Ford Falkerosnov algoritam

Sledeći algoritam računa maksimalni protok za dati graf sa nenegativnim kapacitetima. Jednostavno je razumeti šta ovaj algoritam radi, ali nije trivijalno prikazati da se ovaj algoritam završava i da daje optimalno rešenje.

function net-flow(graph (V, E), node s, node t, cost c): flow
  initialize f(e) := 0 for all e in E
  loop while not done
    for all e in E:                         // рачуна капацитет остатка
      let cf(e) := c(e) - f(e)
    repeat
    
    let Gf := (V, {e : e in E and cf(e) > 0})

    find a path p from s to t in Gf         // нпр., користите прво-у-дубину
    if no path p exists: signal done

    let path-capacities := map(p, cf)       // путања је скуп грана
    let m := min-val-of(path-capacities)    // најмањи остатак капацитета p
    for all (u, v) in p:                    // одржавати ограничења протока
      f((u, v)) := f((u, v)) + m
      f((v, u)) := f((v, u)) - m
    repeat
  repeat
end

Ford-falkersonov algoritam ponavlja pozive Breadth-First pretrazi ( koristi redove za čekanje da rasporedi da deca čvorova postanu trenutni čvorovi). Breadth-First pretraga inkrementira dužinu svake putanje +1 tako da prva putanja koja stigne do destinacije, najkraća putanja, prva napušta red za čekanje. Ovo je obrnuto od korišćenja steka, koji predstavlja Depth-First pretragu i koja će dati bilo koju putanju do destinacije, sa proučenim potomcima trenutnog čvora, ali ne obavezno i najkraću.

U jednoj pretrazi, putanja od izvora do destinacije je pronađena. Sa svih čvorova se sklanja oznaka na početku nove pretrage. Viđeni čvorovi se označavaju i ne pretražuju se ponovo ako se na njih opet naiđe. U nekom trenutku, svi čvorovi do kojih se može doći će biti raspoređeni u redu za čekanje i neće više biti neoznačenih čvorova do kojih se može doći sa poslednjeg čvora iz reda za čekanje.
Tokom pretrage, raspoređeni čvorovi imaju zapamćenu ivicu nalazača ( koja se sastoji od trenutnog čvora, pronađenog čvora, trenutnog protoka i ukupnog kapaciteta u smeru od prvog ka drugo čvoru).
Ovo omogućava nalaženje obrnute putanje od čvora destinacije do početnog čvora. Kad je putanja nađena, ivice se ispituju kako bi se našla ivica sa najmanjim preostalim kapacitetom, i ovo postaje rezultujući protok putanje, i taj broj se oduzima od preostalih kapaciteta svake ivice duž putanje. Na ivici koja predstavlja „usko grlo“ putanje, sa minimalnim preostalim kapacitetom, nikakav protok više neće biti moguć u smeru ka napred, ali će i dalje biti moguć u smeru ka pozadi.
Ovaj proces Breadth-First pretraživanja putanje do izlaznog čvora, popunjavajući putanju do rezidualnog kapaciteta ivice uskog grla , se ponavlja dok se ne desi da BF pretraga ne može da nađe putanju do izlaznog čvora ( do čvora se ne može doći jer sve sekvence ivica do izlaznog čvora imaju popunjena uska grla). Na taj način se memorija sporednih efekata prethodnih putanja koje su nađene snima u prtocima ivica, i ona utiče na naredne pretrage.
Važno svojstvo maksimalnog protoka je da protok može da se pojavi u smeru unazad od ivice i rezidualni kapacitet smera unazad je trenutni protok u smeru unapred. Uobičajeno, rezidualni kapacitet ivice u smeru unapred je protok unapred umanjen za početni kapacitet. Intuitivno, ovo omogućava više opcija za maksimizaciju protoka jer prethodno augmentovane putanje blokiraju kraće putanje.
Na završetku, algoritam zadržava označena i neoznačena stanja rezultata poslednje BF pretrage.
Stanje najmanjeg odsecanja su dva skupa označenih i neoznačenih čvorova formiranih od poslednje bezuspešne BF pretrage koja je počela na ulaznom čvoru, a nije uspela da dođe do izlaznog čvora. Ulazni čvor pripada jednoj strani preseka, a izlazni čvor pripada drugoj strani preseka. Proizvoljno, biti „ u preseku“ znači biti na ulaznoj strani ili biti označen čvor. Podsetite se kako čvor postaje označen sa datom ivicom sa protokom i rezidualnim kapacitetom.

Primer aplikacije Ford Falkerosnovog minimalni protok/minimalno odsecanje algoritma

Primer primene Ford-Falkersonovog algoritma su eliminacije u sezoni bejzbola. Pitanje je da li neki tim može da pobedi u celoj sezoni ako prevazilazi neku kombinaciju pobeda ostalih timova. Ideja je da se napravi graf protoka sa timovima koji ne mogu da prevaziđu broj ukupnih pobeda koji ciljni tima može maksimalno da ostvari za celu sezonu. Postoje čvorovi igre čije ivice predstavljaju broj preostalih mečeva između dva tima, i svaki čvor igre šalje protok ka dva čvora timova, preko ivica koje neće ograničiti protok unapred. Čvorovi timova primaju ivice od svih igara u kojima su učestvovali. Dalje, ivice koje šalju protok sa kapacitetima koji predstavljaju ograničenje pobeda, protiču ka virtuelnom ciljnom čvoru. U stanju maksimalnog protoka, gde ukupan broj pobeda ciljnog čvora prevazilazi neku kombinaciju pobeda ostalih timova, pretposlednja depth-first pretraga će odseći početni čvor od ostatka grafa, jer nikakav protok ka bilo kom od čvorova igre ne bi bio moguć kao rezultat pretposlednje depth-first pretrage (setite se šta se događa sa protokom, u drugom delu algoritma, nakon nalaženja putanje). Ovo je zbog toga što kad se traži maksimalni protok svake putanje, kapaciteti ivica igre će biti maksimalno isceđeni od strane ivica sa ograničenjem pobede iz ostatka putanje, a bilo koji rezidualni kapacitet igre znači treba da se odigra još igara, posle kojih će barem jedan tim preuzeti maksimalan broj pobeda ciljnog tima. Ako je čvor tima u minimalnom odsecanju, onda postoji ivica sa rezidualnim kapacitetom koja vodi ka timu, što, imajući u vidu prethodna izlaganja, znači šta? Šta predstavlja set timova koji se nalaze u minimalnom odsecanju (pomoć: razmislite o ivici čvora igre)?

Primer maksimalnog bipartitivnog uparivanja (interno uparivanje)

Ovaj problem uparivanja ne uključuje prioritetno ponderisanje. Skup kompanija nudi poslove koji sačinjavaju jedan veliki skup, i stažisti se prijavljuju kompanijama za određene poslove. Aplikacije su ivice sa težinama 1. Kako bismo konvertovali problem bipartitnog uparivanja u problem maksimalnog protoka, moramo kreirati virtuelne čvorove s i t, koji imaju ivice težine 1 iz s ka svim stažistima, i od svih poslova do t. Zatim se primanjuje Ford-Falkersonov algoritam kako bi se sekvencijalno saturirale ivice sa kapacitetom 1 iz grafa, tako što se augmentuju pronađene putanje. Može da se desi da se dođe do srednjeg stanja, gde preostali stažisti i poslovi ostanu neupareni, ali bektreking duž suprotnih ivica koje imaju rezidualne kapacitete= protok unapred=1, duž dužih putanja koje se javljaju kasnije tokom breadth-first pretrage će negiratiprethodne sub-optimalne augmentujuće putanje, i obezbeđuje dalje opcije pretrage za uparivanje, i zausteviće se samo onda kada se dođe do maksimalnog protoka ili maksimalnog uparivanja.