1. Moderní metody řešení výpočtově velmi těžkých problémů
Rozhodovaci problem: (L, U, E). E-abeceda, U-vstupy, L-“dobre” vstupy
Optimalizacny problem: (Ei, Eo, L, M, cena, ciel)
Ei, Eo : vstupna/vystupna abeceda L: mnozina pripustnych vstupov M: pripustne riesenia pre dany vstup Cena: (x \in L, u \in M(x)) -> cena(x,u) Ciel: minimalizovat/maximalizovat
Konzistentny algoritmus: najde pripustne riesenie
Optimalny: najde pripustne, ktore je optimalne
Batoh: (v1, …, vn, h1, …, hn, V). Podmnoziny P mnoziny \{1, …, n\} tz \sum_{i in P} ⇐ V. Max. \sum hi
Sucty: Batoh s hi=vi
Vrcholove pokrytie: minimalna podmnozina vrcholov, tz kazda hrana ma v tej mnozine vrchol
Vazene vrcholove pokrytie: rozne vrcholy mozu mat roznu cenu
Nezavisla mnozina vrcholov: maximalna podmnozina vrcholov, kde ziadne dva netvoria hranu
Traveling salesman: kompletny neorientovany graf: Hamiltonvsky cyklus s minimalnym suctom dlzok hran
MAX-SAT: maximalizovat pocet splnenych klauzuli formul v CNF
MIN-CUT: rozdelenie vrcholov, tz sucet dlzok hran na reze je minimalny
MAX-CUT
a dalsie…
Celociselne problemy: vstup x1, …, xn kodovany binarne. Zaujimave instancie: Max(x)⇐h(|x|)
Pseudopolynomialny algoritmus: Time_A(x)⇐p(|x|, Max(x))
Preco? Lemma: Nech A je pseudopol. pre U. Potom pre h-zuzenie problemu (h je lub. polynom) existuje polynomialny algoritmus.
- Priklad: Batoh
Zobecnenie pseudopolynomialnych. Chceme najst instancie problemu, kde to ide riesit efektivne.
- Polynomialne k dlzke vstupu, kludne exponencialne k parametru
- Priklad: vrcholove pokrytie
- Parametrizacia strukturou problemu. Nie som si isty, ale mozno: isomorfizmus grafov je NP-tazky. Pre planarne grafy existuje polynomialny algoritmus, ktory rozhoduje izomorfizmus.
- Relativna chyba konzistentneho algoritmu A pre vstup x (e_A(x)>=0)
- Relativna chyba A pre n in Nset
- Aproximativny pomer A pre x (R_A(x)>=1)
- Aproximativny pomer A pre n
- Cim je hodnota aprox pomeru mensia (blizsie k 1), tym lepsie algoritmus pocita
- Delta-aproximativny algoritmus: forall x: R_A(x) ⇐ delta
- f(n)-aproximativny: forall n: R_A(n)⇐f(n)
- Polynomialna aprox schema: Pre kazdy vstup (x,e>0) vypocita A pripustne riesenie pre x s aprox. pomerom (1+e) v polynomiálnom case vzhladom k |x|.
- Uplna pol aprox schema: algoritmus je polynomialny aj vzhladom k e^-1.
- Vrcholove pokrytie: Vezmi nahodnu hranu, pridaj oba jej vrcholy, az pokym nie su hrany. 2-aproximativny. Dokaz: ziadne dve hrany vybrane algoritmom nemaju spolocny vrchol a preto na ich pokrytie potrebujeme aspon ½ |T| vrcholov.
- Pokrytie mnozin: mnozina U a podmnozina S1, …, Sn. Kazda Si vahu wi. Vybrat podmnozinu {1,…,n} tak ze zjednotenie jej mnozin dava U a sucet ich vah je minimalny. Cena: wi/|Si|, za ktoru sa pokryje 1 prvok. Aprox pomer: Harmonicka funkcia na max_i |Si|.
- Vazene vrcholove pokrytie
- Vychadzame z presneho exponencialneho algoritmu. Pomocou dynamickeho programovania generujeme len niektore pripustne riesenia a najlepsie hladame len medzi nimi.
- Linearna ucelova funkcia + sustava linearnych ohraniceni specifikujucich pripustne riesenia
- V Rset, v Zset, v {0,1}. Prve je polynomialny problem, zvysne 2 su NP-uplne problemy.
- Postup
1) Vyjadri optimalizacnu ulohu ako ulohu 0-1 / celocis programovania
2) RELAXACIA: Najdi riesenie alfa nad realnymi cislami
3) z alfy najdi pripustne riesenie povodneho problemu s vysokou kvalitou (mozno az optimalne)
3a – sprav to metodou zaokrohlovania
3b – sprav to pomocou schemy primarnej a dualnej ulohy
- Zaokruhlovanie: easy. Najdi optimalne riesenie nad R, zaokruhli na cele cisla, tak aby bolo pripustnym riesenim
- Primarna a dualna uloha:
1) Uloha v standardnom tvare: vsetky ohranicenia v podobe nerovnosti, vsetky premenne nezaporne (kazda LP uloha sa da previest do ST)
2) Dualna uloha:
Primarna:
min sum_j cjxj
pri sum_j aijxj >= bi
pri xj >=0
Dualna:
max sum_i biyi
pri sum_i aijyi ⇐cj
pri yi >=0
- Schema PaDU:
START : celociselne riesenie prim ulohy, pripustne riesenie dualnej ulohy
ITERACIA: zlepsuj pripustnost riesenia primarnej ulohy a optimalitu dualnej ulohy
KONIEC: splnene podmienky komplementarity alebo riesenie primarnej je pripustne.
- PODMIENKY KOMPLEMENTARITY: x,y pripustne riesenie primarnej a dualnej ulohy LP. Su optimalne prave vtedy, ked cosi plati (cosi, co vieme rychlo spocitat).
- ROZSIRENE PODMIENKY KOMPLEMENTARITY: pre dane alfa, beta cosi splnaju.
- Kedy koncit?
Presny algoritmus: splnene podmienky komplementarity
Aproximativny algoritmus: ak relaxovana uloha ma lepsie optimalne riesenie nez povodna uloha, danym algoritmom ho nenajdeme. Skoncime, ked su splnene rozsirene podmienky komplementatiry. Hodnota dualneho riesenie je dolny odhad pre optimalne riesenie. Aprox pomer je alfa*beta.
- Nechapem o co tam ide.
- Steinerovsky strom: Graf s ohodnotenymi hranami, vrcholy rozdelene na R a S.
Uloha: Najst najlacnejsi strom, ktory obsahuje vsetky R vrcholy (a pripadne nejake S vrcholy)
- Model A, model B
- LV, LV-neviem, MC-1, MC-2, MC-unbounded
- Odhadnut strednu hodnotu R_A
- Garantovat, ze aprox pomer delta sa stane s Pstou aspon 1/2 .
Lokalne vyhladavanie
- Sekvencne prehladavanie pripustnych rieseni. Od aktualneho pripustneho riesenia k dalsiemu.
- Bez garancie kvality najdeneho riesenia
- Priklad: Vrcholove pokrytie: Odstranenie/pridanie vrcholu. Okolie a jeho vzdialenost. Z okolia vyberame najlepsie pripustne riesenie.
- Okolie dostatocne velke, aby sme neuviazli v zlom lokalnom extreme
- Okolie dostatocne male, aby sa dalo efektivne prehladavat
Geneticke algoritmy
- Populacia rieseni sa vyvija v case.
- Velkost kazdej generacie ohranicena prirodzenym cislom N
- V kazdom kroku sa NAHODNE generuje nova generacia zo sucasnej populacie. Operatormi, ktore znicia niektore sucasne riesenia a pridaju nove riesenia
- AKO?
Funkcia kvality ohodnoti kazde sucasne riesenie
Riesenie prechadza do novej generacie s pstou umernou jeho kvalite
Ak do novej generacie preslo menej ako N rieseni, pridaj tam nove riesenie rekombinaciou inych rieseni alebo modifikaciou niektoreho riesenia
Michal Abaffy. Poznámky som robil pre seba, ide o súhrn hlavných pojmov (nie všetky) a nejaké krátke popisy, aby som si pripomenul, o čo tam ide. Možno sa zíde aj niekomu inému. Časť „Klíčové pojmy“ je niekoho iného.