Алгоритми/Претраживање успоном

Метода претраживања успоном је техника која се користи за одређене класе оптимизационих проблема. Идеја је да се крене од суб-оптималног решења проблема (нпр., почети у подножју успона) и затим понављањем побољшавати решење (шетња уз успон) док неки услов не буде максимизован (док се не дође до врха успона).

Метода претраживања успоном

Конструисати суб-оптимално решење које је у сагласности са ограничењима проблема
Узети решење и побољшати га
Понављати други корак док год је даље побољшавање решења могуће/потребно

Један од најпопуларнијих проблема претраживања успоном је проблем протока мреже. Иако проток мреже може звучати специфично, важан је јер има високу експресивну моћ: на пример, многи проблеми са алгоритмима са којима се сусрећемо у пракси се могу сматрати као посебни случајеви протока мреже. Након што смо приказали једноставан пример приступа претраживању успоном за нумерички проблем, приказаћемо проток мреже а затим ћемо дати примере апликација протока мреже.

Њутнов метод налажења корена

Илустрација Њутнове методе: Нула f(x) функције је у x. Видимо да је претпоставка x_n+1 боља претпоставка од x_n ,јер је ближа x. (из Wikipedia)

Њутнов метод налажења корена је алгоритам стар три века, који служи за налажење нумеричких апроксимација коренова функције (то су тачке $x$ где функција $f(x)$ постаје нула), почевши од иницијалне претпоставке. За овај алгоритам је потребно познавати функцију $f(x)$ и њен први извод $f'(x)\,$ . Идеја је следећа: у близини почетне претпоставке $x_{0}$ можемо формирати Тејлоров ред функције:

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

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

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

Који даје добру апроксимацију функције у околини x0. Узимајући само прва два члана израза са десне стране једначине, изједначавајући их са нулом и решавајући по epsilon, добијамо:

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

Које можемо користити за конструкцију бољег решења:

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

Ово ново решење може бити почетни положај за поновну примену ове процедуре. Тако, уопштено, боља апроксимација може се конструисати понављањем следећег израза:

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

Као што је приказано на слици, ово није ништа више него конструкција нуле из тангенте функције у тачки почетне претпоставке. Уопштено, Њутнов метод налажења коренова конвергира квадратно, осим када први извод решења $f'(x)=0\,$ нестане у корену. По аналогији са методом претраживања успоном, Њутнов метод налажења коренова можемо применити не на функцију $f(x)\,$ , већ на њен први извод $f'(x)\,$ , тј. тражимо $x$ тако да је $f'(x)=0\,$ . Ово ће дати екстерне позиције функције, њене максимуме и минимуме. На овај начин, иницијализацијом Њутновог метода довољно близу максимума, пењемо се уз успон.

Пример апликације Њутновог метода

Функција нето тренутне вредности је функција времена, камате и серија токова кеша. Сродна функција је интерна повратна рата. Формула за сваки период је (CF_i x (1+ i/100) ^t, и ово ће да да полиномијалну функцију која представља укупан проток кеша, и која је једнака нули када је камата једнака ИРР. Приликом коришћења Њутновог метода, x је камата, y је укупан проток кеша, и метод ће да користи дериват полиномијалне функције нађе нагиб графика за задату вредност камате (вредност x), који ће дати тачку x_n+1, тј. бољу вредност камате за следећу итерацију, док се не дође до оне вредности x за које је y=0. Осим континуалних функције, метода претраживања успоном се може применити и на дискретне мреже.

Проток мреже

Претпоставимо да имамо усмерен граф (са могућим циклусима) са једним чвором означеним као извор и другим чвором означеним као дестинација или 'лавабо'. Изворни чвор има само излазне ивице. Слично, чвор дестинације има само улазне ивице. Можемо претпоставити да је граф потпуно повезан, без мртвих крајева; нпр. за сваки чвор (осим изворног и крајњег), постоји бар једна ивица која улази у њега и бар једна ивица која излази из њега. Свакој ивици додељујемо „капацитет“, и на почетку разматрамо само капацитете са интегралним вредностима. Следећи граф је у складу са наведеним захтевима:

Замислићемо да имамо серије улаза који стижу на улазни (изворни) чвор, које бисмо волели да пропагирамо ивицама графа до излазног чвора (чвора дестинације). Број јединица које можемо да пренесемо преко једне ивице у неком тренутку мора бити мањи или једнак капацитету те ивице. Можемо да посматрамо чворове као градове и ивице као путеве између њих, и задатак нам је да пошаљемо што већи бриј аутомобила од исзворног града у град дестинацују. Ограничење је то да неким путем не можемо послати више аутомобила него што ја капацитет тог пута. Циљ протока мреже је да се пошаље максималан саобраћај од s до t који свака улица може да поднесе. Како би се организовале саобраћајне руте, можемо направити листу различитих путања од града $s$ до града $t$ . Свака путања има капацитет једнак најмањем капацитету свих ивица које припадају тој путањи; на пример, посматрајмо следећу путању $p$ :

Иако последња ивица путање $p$ има капацитет 8, том ивицом иде само један аутомобил, јер претходна ивица има капацитет 1 (па је та ивица у пуном капацитету). Након коришћења ове путање, можемо да израчунамо резидуални граф тако што ћемо да одудмемо 1 од капацитет сваке ивице:

(Одузимамо 1 од капацитета сваке ивице из путање p јер је капацитет путање $p$ једнак 1.) Можемо рећи да p има проток 1. Формално, проток је додела $f(e)$ вредности скупу ивица графа $G=(V,E)$ таква да важи:

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)

Где је $s$ изворни (улазни) чвор, а $t$ излазни (чвор дестинације) чвор, и $c(e)\geq 0$ је капацитет ивице $e$ . Вредност протока $f$ дефинишемо на следећи начин:

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

Циљ протока мреже је да се нађе f такво да је ${\textrm {Value}}(f)$ максимално. Ово значи да не постоји ни једна друга додела протока која је у складу са ограничењима 1-4 да има већу вредност протока. На примеру саобраћаја ћемо демонстрирати шта значе ова 4 ограничења:

$\forall e\in E:f(e)\in \mathbb {R}$ . Ово правило дефинише проток као реалну функцију ивица. Функција је дефинисана за сваку ивицу графа. Ова функција се може посматрати као просто мапирање. Свака # $\forall (u,v)\in E:f((u,v))=-f((v,u))$ . Ово правило каже да ако има саобраћаја који иде од чвора u до чвора v, онда се саобраћај од v до u сматра његовим негативом. На пример, ако два аутомобила иду од града u до града v, онда -2 аутомобила иду у супротном смеру. Слично, ако 3 аутомобила иду од града u до града v и 2 аутомобила иду од града v до u, ефекат је исти као да један аутомобил иде од града u до града v и ниједан од града v до града u.
$\forall u\in V,u\neq s,t:\sum _{v\in V}f(u,v)=0$ . Ово правило каже да пи мрежни проток, осим за улазни и излази чвор требало да буде неутралан. То значи да никада више аутомобила неће ићи у неки гради него што ће излазити из неког града. Нови аутомобили могу само доћи из улазног чвора и аутомобили се само могу заустављати у излазном чвогу. Слично, шта год потекне из s мора дотећи у t. Приметимо да, уколико неки град има 3 аутомобила који долазе у њега, он може послати 2 аутомобила у јдан град и аутомобил у неки други град. Такође, у неки гради аутомобили могу долазити из више различитих градова ( мада су сви дошли из s).
$\forall e\in E:f(e)\leq c(e)$ .

Форд Фалкероснов алгоритам

Следећи алгоритам рачуна максимални проток за дати граф са ненегативним капацитетима. Једноставно је разумети шта овај алгоритам ради, али није тривијално приказати да се овај алгоритам завршава и да даје оптимално решење.

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

Форд-фалкерсонов алгоритам понавља позиве Breadth-First претрази ( користи редове за чекање да распореди да деца чворова постану тренутни чворови). Breadth-First претрага инкрементира дужину сваке путање +1 тако да прва путања која стигне до дестинације, најкраћа путања, прва напушта ред за чекање. Ово је обрнуто од коришћења стека, који представља Depth-First претрагу и која ће дати било коју путању до дестинације, са проученим потомцима тренутног чвора, али не обавезно и најкраћу.

У једној претрази, путања од извора до дестинације је пронађена. Са свих чворова се склања ознака на почетку нове претраге. Виђени чворови се означавају и не претражују се поново ако се на њих опет наиђе. У неком тренутку, сви чворови до којих се може доћи ће бити распоређени у реду за чекање и неће више бити неозначених чворова до којих се може доћи са последњег чвора из реда за чекање.
Током претраге, распоређени чворови имају запамћену ивицу налазача ( која се састоји од тренутног чвора, пронађеног чвора, тренутног протока и укупног капацитета у смеру од првог ка друго чвору).
Ово омогућава налажење обрнуте путање од чвора дестинације до почетног чвора. Кад је путања нађена, ивице се испитују како би се нашла ивица са најмањим преосталим капацитетом, и ово постаје резултујући проток путање, и тај број се одузима од преосталих капацитета сваке ивице дуж путање. На ивици која представља „уско грло“ путање, са минималним преосталим капацитетом, никакав проток више неће бити могућ у смеру ка напред, али ће и даље бити могућ у смеру ка позади.
Овај процес Breadth-First претраживања путање до излазног чвора, попуњавајући путању до резидуалног капацитета ивице уског грла , се понавља док се не деси да BF претрага не може да нађе путању до излазног чвора ( до чвора се не може доћи јер све секвенце ивица до излазног чвора имају попуњена уска грла). На тај начин се меморија споредних ефеката претходних путања које су нађене снима у пртоцима ивица, и она утиче на наредне претраге.
Важно својство максималног протока је да проток може да се појави у смеру уназад од ивице и резидуални капацитет смера уназад је тренутни проток у смеру унапред. Уобичајено, резидуални капацитет ивице у смеру унапред је проток унапред умањен за почетни капацитет. Интуитивно, ово омогућава више опција за максимизацију протока јер претходно аугментоване путање блокирају краће путање.
На завршетку, алгоритам задржава означена и неозначена стања резултата последње BF pretrage.
Стање најмањег одсецања су два скупа означених и неозначених чворова формираних од последње безуспешне BF претраге која је почела на улазном чвору, а није успела да дође до излазног чвора. Улазни чвор припада једној страни пресека, а излазни чвор припада другој страни пресека. Произвољно, бити „ у пресеку“ значи бити на улазној страни или бити означен чвор. Подсетите се како чвор постаје означен са датом ивицом са протоком и резидуалним капацитетом.

Пример апликације Форд Фалкеросновог минимални проток/минимално одсецање алгоритма

Пример примене Форд-Фалкерсоновог алгоритма су елиминације у сезони бејзбола. Питање је да ли неки тим може да победи у целој сезони ако превазилази неку комбинацију победа осталих тимова. Идеја је да се направи граф протока са тимовима који не могу да превазиђу број укупних победа који циљни тима може максимално да оствари за целу сезону. Постоје чворови игре чије ивице представљају број преосталих мечева између два тима, и сваки чвор игре шаље проток ка два чвора тимова, преко ивица које неће ограничити проток унапред. Чворови тимова примају ивице од свих игара у којима су учествовали. Даље, ивице које шаљу проток са капацитетима који представљају ограничење победа, протичу ка виртуелном циљном чвору. У стању максималног протока, где укупан број победа циљног чвора превазилази неку комбинацију победа осталих тимова, претпоследња depth-first претрага ће одсећи почетни чвор од остатка графа, јер никакав проток ка било ком од чворова игре не би био могућ као резултат претпоследње depth-first претраге (сетите се шта се догађа са протоком, у другом делу алгоритма, након налажења путање). Ово је због тога што кад се тражи максимални проток сваке путање, капацитети ивица игре ће бити максимално исцеђени од стране ивица са ограничењем победе из остатка путање, а било који резидуални капацитет игре значи треба да се одигра још игара, после којих ће барем један тим преузети максималан број победа циљног тима. Ако је чвор тима у минималном одсецању, онда постоји ивица са резидуалним капацитетом која води ка тиму, што, имајући у виду претходна излагања, значи шта? Шта представља сет тимова који се налазе у минималном одсецању (помоћ: размислите о ивици чвора игре)?

Пример максималног бипартитивног упаривања (интерно упаривање)

Овај проблем упаривања не укључује приоритетно пондерисање. Скуп компанија нуди послове који сачињавају један велики скуп, и стажисти се пријављују компанијама за одређене послове. Апликације су ивице са тежинама 1. Како бисмо конвертовали проблем бипартитног упаривања у проблем максималног протока, морамо креирати виртуелне чворове s и t, који имају ивице тежине 1 из s ка свим стажистима, и од свих послова до t. Затим се примањује Форд-Фалкерсонов алгоритам како би се секвенцијално сатурирале ивице са капацитетом 1 из графа, тако што се аугментују пронађене путање. Може да се деси да се дође до средњег стања, где преостали стажисти и послови остану неупарени, али бектрекинг дуж супротних ивица које имају резидуалне капацитете= проток унапред=1, дуж дужих путања које се јављају касније током breadth-first претраге ће негиратипретходне суб-оптималне аугментујуће путање, и обезбеђује даље опције претраге за упаривање, и заустевиће се само онда када се дође до максималног протока или максималног упаривања.