FANDOM


36PAA, přednáší Doc. Schmidt

Odkazy Editovat

Stránky na serveru service

Pojmy Editovat

Charakteristika problémuEditovat

  • vstupní proměnné
  • výstupní proměnné
  • konfigurační proměné
  • omezení
  • optimalizační kritérium

(Výstupní proměnné mohou být tytéž jako konfigurační proměnné - to platí pouze pro konstruktivní verze problémů!)

Instance a řešeníEditovat

  • instance - ohodnocení vstupních proměnných - I
  • konfigurace - ohodnocení konfiguračních proměnných - Y
  • řešení - konfigurace, která splňuje omezení
  • optimální řešení - konfigurace, která splňuje omezení a má nejlepší hodnotu optimalizačního kritéria
  • suboptimální řešení - konfigurace, která splňuje omezení a má vyhovující hodnotu optimalizačního kritéria (z hlediska aplikace)

Omezení - R(I,Y)

Kombinatorické problémy Editovat

  • Rozhodovací problém - Existuje Y takové, že R(I,Y)?
  • Konstruktivní problém - Sestrojte nějaké Y takové, že R(I,Y).
  • Enumerační problém - Sestrojte všechna Y taková, že R(I,Y).

Optimalizační problémy Editovat

C(Y) - optimalizační kritérium - cenová funkce

  • Optimalizační rozhodovací problém - Existuje Y takové, že R(I,Y) a C(Y) je lepší než daná konstanta Q?
  • Optimalizační konstruktivní problém - Sestrojte nějaké Y takové, že R(I,Y) a C(Y) je nejlepší možné.
  • Optimalizační enumerační problém - Sestrojte všechna Y taková. že R(I,Y) a C(Y) je nejlepší možné.
  • Optimalizační evaluační problém - Zjistěte nejlepší možné C(Y) takové, že R(I,Y).

Stav algoritmu Editovat

Nechť X={x1, x2, ...,xn} je množnina konfiguračních proměnných a Z={z1, z2, ...,zn} je množnia vnitřních proměnných algoritmu A řešícího I. Pak každé ohodnocení S proměnných X a Z je stav algoritmu.

Stavový prostor Editovat

Nechť S={si} je množnina všech stavů algoritmu A. Nechť Q={qi} je množina operací S->S takových, že qj(si) != si. Pak dvojici (S,Q) nazveme stavovým prostorem algoritmu A řešícího I.

Typy problémů Editovat

SAT = satisfiability - Splnitelnost booleovské formule (wikipedia)


Pokročilé heuristiky Editovat

Simulované ochlazování Editovat

Simulované ochlazování (Simulované žíhání, Simulated Annealing - SA) je jednou z lokálních metod prohledávání stavového prostoru. Od metody nejlepší první se liší tím, že s určitou, stále klesající pravděpodobností, je schopna přijmout i horší stav a tím vyklouznout z lokálního minima.

Metoda simulovaného ochlazování patří mezi stochastické optimalizační algoritmy, které, jak již je zřejmé z názvu samotného algoritmu mají základ ve fyzice, na rozdíl od jiných stochastických optimalizačních algoritmů, které mají většinou svůj základ v biologii.

Ve fyzice žíhání označuje takový proces, při kterém je těleso umístěné do pece vyhřáté na vysokou teplotu a postupným pomalým snižováním teploty se odstraňuji vnitřní defekty tělesa. Při vysoké teplotě je těleso roztopené což znamená, že částice dané látky jsou náhodně uspořádané v prostoru. Při postupném snižování teploty se částice dostávají do rovnovážné polohy, tj. celková energie tělesa se snižuje.

Algoritmus simulovaného ochlazování je na implementaci velmi nenáročný a stejně jako všechny zde použité heuristiky pracuje s pevným počtem iterací při variabilní kvalitě. Tuto heuristiku však lze upravit i tak, aby dávala požadovanou fixní kvalitu při variabilním počtu iterací (výpočetní náročnost) - a to až nekonečného výpočtu.

 tStav Simulované_ochlazování(tStav Výchozí_stav)
 {
   teplota = Výchozí_teplota;
   stav = Výchozí_stav;
   nejlepší_stav = stav;
   
   do {
     do {
       stav = další_state(stav, teplota);
       nejlepší_stav = ten_lepší(nejlepší_stav, stav);
     } while (Délka_vnitřní_smyčky);
     teplota = ochlazení(Koeficient_ochlazování);
   } while (teplota > Koncová_teplota)
   
   return nejlepší_stav;
 }

Algoritmus má několik volitelných parametrů: výchozí stav, výchozí teplotu, koncovou teplotu, koeficient ochlazování a délku vnitřní smyčky. Jako výchozí stav je možné volit výstup z nějaké jednodušší heuristiky (což může např. u již známe kombinované heuristiky zajistit dokázanou maximální chybu) nebo nějaký náhodný stav nebo prázdný batoh.

Ostatní parametry ovlivňují vlastní počet iterací a pravděpodobnost volby riskantních změn do horších stavů.

Viz také

Genetické algoritmy Editovat

FIXME

Viz také

Tabu vyhledávání Editovat

FIXME

Viz také

Problémy a algoritmy v kostceEditovat

ProblémyEditovat

Kombinatorický problém 
je charakterizován
  • vstupními proměnnými (na příkladu s vrtačkou a tišťákem je to seznam děr),
  • výstupními proměnnými (pořadí děr tak, jak se budou vrtat),
  • konfiguračními proměnnými (také pořadí děr),
  • omezením (každou díru vrtat jen jednou, uzavřená cesta),
  • optimalizačním kritériem, je-li třeba (co nejkratší cesta vrtačky).
  • proměnných je konečný počet a mají konečné domény - problém lze tedy vždy vyřešit hrubou silou


Instance problému 
je ohodnocení vstupních proměnných.
Konfigurace 
je ohodnocení konfiguračních proměných.
Řešení instance 
je konfigurace, která splňuje omezení.
Optimální řešení 
je řešení s nejlepší hodnotou optimalizačního kritéria.
Suboptimální řešení 
je řešení s vyhovující hodnotou optimalizačního kritéria. Otázkou je, co je vyhovující hodnota.



Typy kombinatorických problémů a jejich optimalizační verzeEditovat

Čistě kombinatorické problémyEditovat

Notace: I je instance problému, Y je konfigurace, R(I, Y) je omezení (R(I, Y) tedy říká, jestli je Y řešením).

Rozhodovací problém 
Existuje Y takové, že R(I, Y)?
Konstruktivní problém 
Sestrojit nějaké Y takové, že R(I, Y).
Enumerační problém 
Sestrojit všechna Y taková, že R(I, Y).


Optimalizační problémyEditovat

K předchozí notaci ještě přibývá optimalizační kritérium (cenová funkce) C(Y).

Optimalizační rozhodovací problém 
Existuje Y takové, že R(I, Y) a C(Y) je lepší než nějaká konstanta Q?
Optimalizační konstruktivní problém 
Sestrojit nějaké Y takové, že R(I, Y) a C(Y) je nejlepší možné.
Optimalizační enumerační problém 
Sestrojit všechna Y taková, že R(I, Y) a C(Y) je nejlepší možné.
Optimalizační evaluační problém 
Zjistit nejlepší možné C(Y) takové, že R(I, Y).


Složitost problému, algoritmuEditovat

Asymptotická složitost algoritmuEditovat

Nechť f, g: \mathrm{N} \to \mathrm{R}^+

Asymptotická horní mez
f(n) je shora omezena g(n), f(n) = O(g(n)), pokud existuje kladné c takové, že pro všechna n > n_0 platí:

f(n) \leq c\cdot{}g(n).

Asymptotická dolní mez
f(n) = \Omega{}(g(n)) \iff \exists{}c > 0, n_0 \in \mathrm{N}: \forall{}n > n_0{}: f(n) \geq c\cdot{}g(n).
Asymptotický odhad
f(n) = \Theta{}(g(n)) \iff f(n) = O(g(n)) \land f(n) = \Omega{}(g(n)), tzn. c_1{}\cdot{}g(n) \leq f(n) \leq c_2{}\cdot{}g(n).

Složitost problémuEditovat

Složitost problému se určuje jako složitost algoritmu, který ho řeší. Máme-li algoritmus f(n), který řeší problém \Pi, pak je jeho složitost O(f(n)).


Stavový prostorEditovat

Stav 
Nechť X = \{x_1, x_2, \ldots, x_n\} jsou konfigurační proměnné problému \Pi. Nechť Z = \{z_1, z_2, \ldots, z_m\} jsou vnitřní proměnné algoritmu A řešícího instanci I problému \Pi. Pak každé ohodnocení s proměnných X\cup{}Z je stav algoritmu A řešícího I.
Stavový prostor 
Nechť S = \{s_i\} je množina všech stavů algoritmu A řešícího I. Nechť Q = \{q_j\} je množina operací S \to S takových, že q_{j}(s_i) \neq s_i pro všechna s_i, q_j. Pak dvojici (S, Q) nazveme stavovým prostorem algoritmu A řešícího I.


Graf stavového prostoruEditovat

Tah 
Nechť s \in S je (jeden konkrétní) stav a q \in Q operace. Pak aplikace q(s) se nazývá tah.
Graf stavového prostoru 
Nechť (S, Q) je stavový prostor algoritmu řešícího instanci problému. Pak orientovaný graf H = (S, E), kde hrana (s_i, s_j) \in E odpovídá tahu s_j = q(s_i) pro q \in Q se nazývá grafem stavového prostoru algoritmu.

Strategie pohybu stavovým prostoremEditovat

Po stavovém prostoru se pohybujeme transformací aktuálního stavu pomocí dostupných operací na nějaký jiný stav. Tuto transformaci je třeba řídit.

Úplná strategie 
Navštívíme všechny stavy kromě těch, o kterých víme, že nedávají (optimální) řešení.
Systematická strategie 
Úplná strategie, při které navštívíme každý stav nejvýše jednou.


Vlastností systematických strategií je, že jsou v nejhorším případě rovny hrubé síle. To nastane například v případě neexistujícího řešení. Výhodou je, že existuje-li řešení, tyto metody jej naleznou. Navíc naleznou řešení optimální.

Na základě dosud dosažené hodnoty optimalizačního kritéria, splnění omezujících podmínek nebo znalosti optimalizačního kritéria a omezujících podmínek můžeme vyloučit (prořezat) určité oblasti stavového prostoru (větve hledání).


Prohledávací prostorEditovat

Rozšíříme-li stavový prostor tak, že každému prvku nepřísluší jedna konfigurace, ale množina konfigurací, hovoříme o prohledávacím prostoru.

Třídy složitosti problémůEditovat

Na složitost problémů lze nahlížet různými způsoby. Jako únosné lze označit takové problémy, jajichž stavový prostor je polynomiálně velký. Neúnosné jsou pak takové, jejichž stavový prostor je nadpolynomiální. U některých existuje únosně dlouhá cesta stavovým prostorem k řešení, pokud víme, kudy jít. U některých ani to ne.

Více formalismu do celé problematiky se snaží vnést systém tříd problémů. Modelem univerzálního výpočetního stroje je tu Turingův stroj.


Třídy rozhodovacích problémůEditovat

Řešení problému deterministickým Turingovým strojemEditovat

Program M pro deterministický Turingův stroj řeší rozhodovací problém \Pi, jestliže se výpočet zastaví po konečném počtu kroků pro každou instanci problému \Pi.

Program M pro deterministický Turingův stroj řeší rozhodovací problém \Pi v čase t, jestliže se výpočet zastaví po t krocích pro každou instanci problému \Pi.


Třída PEditovat

Rozhodovací problém patří do třídy P jestliže pro něj existuje program pro deterministický Turingův stroj, který jej řeší v čase O(n^k), kde n je velikost instance a k je konečné číslo.


Třídy PSPACE a EXPTIMEEditovat

Pro problém spadající do třídy PSPACE platí, že spotřebuje polynomiální množství pásky. Problém ze třídy EXPTIME je řešen v čase O(2^{P(n)}), kde P(n) je polynom ve velikosti instance n.


Řešení problému nedeterministickým Turingovým strojemEditovat

Program M nedeterministického Turingova stroje řeší rozhodovací problém \Pi v čase t, jestliže se výpočet zastaví po t krocích pro každou instanci I \in \Pi{}_{ANO} problému \Pi, kde \Pi{}_{ANO} je množina instancí problému \Pi takových, které mají výstup ANO.

Jestliže nedeterministický Turingův stroj řeší problém \Pi v čase T(n), pak deterministický Turingův stroj řeší \Pi v čase 2^{O(T(n))}.


Třída NPEditovat

Rozhodovací problém \Pi patří do třídy NP, jestliže pro něj existuje program pro nedeterministický Turingův stroj, který každou instanci I \in \Pi{}_{ANO} problému \Pi řeší v čase O(n^k), kde n je délka vstupních dat a k je konečné číslo.

Rozhodovací problém \Pi patří do třídy NP, jestliže pro každou instanci I \in \Pi{}_{ANO} problému \Pi existuje konfigurace Y taková, že kontrola, zda Y je řešením, patří do P (tzn. že omezující podmínky lze vyhodnotit v polynomiálním čase). V této souvislosti nazýváme Y certifikátem.


Třída co-NPEditovat

Existují i problémy mimo NP. Například rozhodovací problém, zda je graf prost Hamiltonových kružnic, nebo zda je booleovská formule nesplnitelná. Problémem je, že při odpovědi "ano, je nesplnitelná" nemáme žádný certifikát, kterým bychom to doložili. Na takovéto problémy lze pohlížet jako na "protějšky" NP problémů -- označují se co-NP.


Třídy optimalizačních problémůEditovat

Řešení optimalizačního problému Turingovým strojemEditovat

Program M pro deterministický Turingův stroj řeší optimalizační problém \Pi v čase t, jestliže se výpočet zastaví po t krocích pro každou instanci problému \Pi, která má řešení, a na pásce je zapsán výstup instance.

Program M pro deterministický Turingův stroj počítá optimalizační kritérium problému \Pi v čase t, jestliže pro každé řešení každé instance problému \Pi, zapsané na pásce jako vstupní data, se výpočet zastaví po t krocích a na pásce je zapsána hodnota optimalizačního kritéria.


Třída NPOEditovat

Optimalizační problém \Pi patří do třídy NPO, jestliže splňuje následující podmínky:

  • velikost výstupu instance je omezena polynomem ve velikosti instance (tj. výstup lze zapsat v polynomiálním čase),
  • problém, zda daná konfigurace je řešením, patří do P (tj. omezující podmínky lze vyhodnotit v polynomiálním čase),
  • existuje program pro Turingův stroj, který vypočítá hodnotu optimalizačního kritéria pro všechna řešení všech instancí v polynomiálním čase (tj. optimalizační kritérium lze vyhodnotit v polynomiálním čase).


Třída POEditovat

Optimalizační problém \Pi patří do třídy PO, jestliže splňuje následující podmínky:

  • patří do NPO,
  • existuje program pro Turingův stroj, který každou instanci vyřeší v polynomiálním čase.

Příkladem je třeba problém nejkratší cesty v grafu G = (V, E). Velikost výstupu je O(|E|), ověřit omezení trvá O(|E|\log |E|), optimalizační kritérium spočteme v čase O(|E|) a existuje polynomiální algoritmus (Dijkstra).


NP-úplné a NP-těžké problémyEditovat

X-těžký 
Problém \Pi je X-těžký, jestliže se efektivní řešení všech problémů ze třídy X dá zredukovat na efektivní řešení problému \Pi. Efektivním řešením je například řešení v polynomiálním čase nebo řešení s omezenou chybou. Zredukovat na řešení \Pi znamená vyřešit pomocí \Pi.
X-úplný 
Problém \Pi je X úplný, jestliže je X-těžký a sám patří do třídy X.


NPC problémyEditovat

Karpova redukce 
Rozhodovací problém \Pi_1 je Karp-redukovatelný na \Pi_2 (značí se \Pi_1 \propto \Pi_2), jestliže existuje polynomiální program pro deterministický Turingův stroj, který převede každou instanci I_1 problému \Pi_1 na instanci I_2 problému \Pi_2 tak, že výstup obou instancí je shodný.

Karpova redukce je tranzitivní, tedy platí, že (\Pi_1 \propto \Pi_2) \land (\Pi_2 \propto \Pi_3) \Rightarrow \Pi_1 \propto \Pi_3. Zároveň lze pomocí Karpovy redukce vytvářet třídy polynomiální ekvivalence ((\Pi_1 \propto \Pi_2) \land (\Pi_2 \propto \Pi_1) \Rightarrow \Pi_1 a \Pi_2 jsou polynomiálně ekvivalentní).

NP-úplný problém 
Problém \Pi je NP-úplný (NPC, NP-Complete), jestliže \Pi \in \mathrm{NP} a pro všechny problémy \Pi' \in \mathrm{NP} platí, že \Pi' \propto \Pi.

Důsledkem je, že máme-li problém \Pi \in \mathrm{NP} a existuje-li třeba i jedinný \Pi' \in \mathrm{NPC} takový, že \Pi' \propto \Pi, pak z tranzitivity plyne, že \Pi \in \mathrm{NPC} (česky: když najdeme jeden NPC problém, který jde převést na náš problém \Pi, pak musí být náš problém taky NPC, jelikož všechny NP jdou převést na náš problém přes \Pi' ve dvou krocích).

NPC jsou nejtěžší, vzájemně převoditelné, problémy v NP.

Cookova věta 
SAT je NP-úplný.

Velice důležitá věta, která přináší řadu důsledků. Především říká, že NPC není prázdná a otevírá tak cestu k důkazům NP-úplnosti převodem. Jsou známy tisíce NPC problémů, které tvoří třídu ekvivalence. Nezdá se proto, že by třída problémů P byla shodná s NP.

Toho, že SAT je NP-úplný, a předchozího důsledku se využívá k dokazování, že je nějaký problém NP-úplný (\Pi \in \mathrm{NP}, \mathrm{SAT} \propto \Pi \Rightarrow \Pi \in \mathrm{NPC}).


NPH problémyEditovat

Turingova redukce 
Rozhodovací problém \Pi_1 je Turing-redukovatelný na \Pi_2 (značíme třeba \Pi_1 \stackrel{\mathrm{T}}{\propto} \Pi_2, jestliže existuje polynomiální program pro (deterministický) Turingův stroj, který řeší každou instanci I_1 problému \Pi_1 tak, že používá program M_2 pro problém \Pi_2 jako podprogram (jehož trvání považujeme za jeden krok).

Karpova redukce je speciálním případem Turingovy redukce, kdy voláme podprogram pouze jednou a přímo používáme výsledek tohoto podprogramu.

NP-těžký problém 
Problém \Pi je NP-těžký (NPH, NP-Heavy), jestliže pro všechny problémy \Pi' \in \mathrm{NP} platí, že \Pi' \stackrel{\mathrm{T}}{\propto} \Pi.

Z definice NPH problémů mimo jiné plyne to , že \mathrm{NPC} \subset \mathrm{NPH}.


NPI problémyEditovat

NP-intermediate problém 
Existují problémy, pro které ani neumíme nalézt polynomiální algoritmus, ani je převést na SAT. Takové označujeme jako NPI a patří mezi ně například problém izomorfismu grafů (do roku 2004 taky test prvočíselnosti čísel).

AlgoritmyEditovat

Existuje celá řada neúnosných optimalizačních problémů (NPO), které je ale nutno v praxi řešit. Metody řešení lze rozdělit na deterministické a náhodné a kombinované. Mezi deterministiké patří aproximativní (zaručena hodnota chyby v nejhorším případě) a pseudopolynomiální algoritmy, metody náhodné a kombinované zastupují randomizované algoritmy (s danou statistikou charakteristikou chyby v průměrném případě).


Pseudopolynomiální algoritmyEditovat

Pseudopolynomiální algoritmus 
Algoritmus, jehož počet kroků závisí polynomiálně na velikosti instance, ale závisí dále na parametru, který s velikostí instance nesouvisí.


Aproximativní algoritmyEditovat

Aproximativní algoritmy určují tři třídy aproximovatelných problémů. Třídu aproximovatelných problémů APX, třídu libovolně přesně aproximovatelných problémů PTAS a třídu libovolně přesně a rychle aproximovatelných problémů FPTAS.


Hodnocení kvality algoritmuEditovat

Relativní kvalita 
Algoritmus APR má relativní kvalitu R, jestliže


R \geq \max_{\forall I} \left\{
\frac{C(APR(I))}{C(OPT(I))}, \frac{C(OPT(I))}{C(APR(I))}
\right\}
Pro R rovno jedné je algoritmus zaručeně přesný, pro R jdoucí do nekoněčna nedává žádnou záruku přesnosti.

Relativní chyba 
Algoritmus APR má relativní chybu \varepsilon, jestliže


\varepsilon \geq \max_{\forall I} \left\{
\frac{|C(APR(I)) - C(OPT(I))|}{\max \left\{C(OPT(I)), C(APR(I))\right\}}
\right\}
Pro \varepsilon rovno nule je algoritmus zaručeně přesný, pro \varepsilon rovno jedné nedává žádnou záruku přesnosti.


Značení ve vzorcích má tento význam:

  • C(S) je hodnota optimalizačního kritéria řešení S
  • APR(I) je aproximované řešení instance I
  • OPT(I) je optimální řešení instance I


Relativní chyba a relativní kvalita jsou vzájemně převoditelné vztahem 
\varepsilon = 1 - \frac{1}{R}

Třídy aproximačních problémůEditovat

R-aproximativní algoritmus 
Algoritmus APR pro problém \Pi je

R-aproximativní\footnote{stejným způsobem lze použít relativní chybu \varepsilon a mít algoritmus \varepsilon-aproximativní}, jestliže je jeho relativní kvalita R.

R-aproximativní optimalizační problém 
Optimalizační problém \Pi je R-aproximativní, jestliže pro něj existuje R-aproximativní polynomiální algoritmus. Číslo R se nazývá aproximační práh problému \Pi.
APX problém 
Optimalizační problém \Pi patří do třídy problémů APX, jestliže je R-aproximativní pro konečné R.
PTAS 
Algoritmus APR, který pro každé \varepsilon > 0 vyřeší každou instanci problému \Pi s relativní chybou nejvýše \varepsilon v čase polynomiálním v |I| nazýváme polynomiální aproximační schéma problému \Pi (PTAS, Polynomial Time Approximation Scheme).
PTAS problém 
Problém \Pi patří do třídy PTAS, jestliže pro \Pi existuje polynomiální aproximační schéma (patří tam například problém batohu nebo geometrický TSO).
FPTAS 
Polynomiální aproximační schéma APR, jehož čas výpočtu závisí polynomiálně na 1/\varepsilon, nazýváme plně polynomiální aproximační schéma (FPTAS, Fully Polynomial Time Approximation Scheme).
FPTAS problém 
Problém \Pi patří do třídy FPTAS, jestliže pro \Pi existuje plně polynomiální aproximační schéma.


Aproximačně nejtěžší problémyEditovat

Zavedením APX-redukce tak, že zachovává aproximaci (efektivitu) a chápáním sousloví \uv{efektivní řešení} jako aproximovatelné řešení lze využít definic z odstavce~\ref{subsec:npc_nph} na straně~\pageref{subsec:npc_nph} o X-těžkých a X-úplných problémech.

APX redukce 
APX-redukci značíme jako \stackrel{\mathrm{APX}}{\propto} a má následující vlastnosti:
  • \Pi_1 \stackrel{\mathrm{APX}}{\propto} \Pi_2, \Pi_2 \in \mathrm{APX} \Rightarrow \Pi_1 \in \mathrm{APX}
  • \Pi_1 \stackrel{\mathrm{APX}}{\propto} \Pi_2, \Pi_2 \in \mathrm{PTAS} \Rightarrow \Pi_1 \in \mathrm{PTAS}
  • APX redukce je Turingova redukce.
NPO-těžký problém 
Problém \Pi je NPO-těžký, jesliže \forall  \Pi' \in \mathrm{NPO}: \Pi' \stackrel{\mathrm{APX}}{\propto} \Pi.
NPO-úplný problém 
Problém \Pi je NPO-úplný, jestliže je NPO-těžký a \Pi \in \mathrm{NPO}.
APX-těžký problém 
Problém \Pi je APX-těžký, jesliže \forall  \Pi' \in \mathrm{APX}: \Pi' \stackrel{\mathrm{APX}}{\propto} \Pi.
APX-úplný problém 
Problém \Pi je APX-úplný, jestliže je APX-těžký a \Pi \in \mathrm{APX}.


Randomizované algoritmyEditovat

Randomizovaný algoritmus je založen na náhodné volbě a jeho vlastnosti jsou vyjádřeny statisticky. Můžeme je rozdělit do dvou skupin:

Monte Carlo algoritmy 
Dosažený výsledek (optimalizační kritérium) je náhodná proměnná, čas běhu je pro danou instanci pevný.
Las Vegas algoritmy 
Čas běhu je náhodná proměnná, výsledek je vždy správný.


Výhodou randomizovaných algoritmů je strukturní jednoduchost. Očekávaná kvalita výsledku může být lepší než zaručená kvalita aproximativních algoritmů. Nezávislým opakováním lze kvalitu zlepšit. Tím, že budeme randomizované algoritmy kombinovat s deterministickými prvky, dosáhneme nestrannosti při vzorkování libovolného souboru prvků (každý náhodný start stejně pravděpodobný, každý soused vybrán se stejnou pravděpodobností, \ldots).

Randomizované paradigma výpočtu ovšem není silnější než deterministické.


Lokální metodyEditovat

Okolí stavu 
Okolí stavu s \in S je množina stavů, dosažitelných z s aplikací některé operace q \in Q.
k-okolí stavu 
k-okolí stavu s \in S je množina stavů, dosažitelných z s aplikací nejméně jedné a nejvýše k operací q \in Q.
Sousední stav 
Stav s_0 \in S patřící do okolí stavu s \in S se nazývá sousedním stavem (sousedem) stavu s.


Lokální metoda má vždy jen jeden aktuální stav, který zpracovává, přičemž uvažuje sousední stavy z (relativně malého) okolí. Úplné a systematické metody uschovávají každý stav z okolí pro pozdější zpracování. Proto jsou exaktní a proto mohou mít nadpolynomiální složitost.

Konstruktivní heuristika 
Začne z triviální konfigurace a postupnými kroky konstruujeme řešení.
Iterativní heuristika 
Začne z nějakého řešení a to postupně vylepšuje.
Dvojfázové heuristiky 
První fáze slouží k získání řešení (konstruktivně, náhodné řešení), ve truhé fázi iterativní vylepšování.
Jednoduché heuristiky 
  • Pouze nejlepší
  • Prvé zlepšení
  • Heuristiky Kernighan-Lin (mají takové to podlouhlé okolí, projdou například pět stavů a pak se podívají, který z těch pěti byl nejlepší a z něj pokračují)


Lokální heuristiky, které neřeší problém lokálních minim, uváznou hned v prvním takovém. To se projevuje tím, že výsledné řešení silně závisí na startovacím stavu. Existuje několik metod, jak uváznutí řešit. Můžeme


  • zvětšit okolí,
  • startovat z několika různých (náhodných) počátečních řešení,
  • vracet se z větví, které nevedou k řešení (detekujeme slepou uličku),
  • dočasně připustit zhoršení aktuálního stavu (zvyšuje nároky na řízení algoritmu)



Globální metodyEditovat

Při řešení instancí problému globálními metodami si pomáháme dekompozicí instance na podinstance. Výsledné řešení skládáme z jednotlivých řešení podinstancí. Triviální podinstance řešíme hrubou silou. Přirozeným modelem výpočtu je rekurze.

Základní postup tedy vypadá nějak takto: 
I \in \Pi \left\{
	\begin{array}{ccc}
	I_1 \in \Pi & \longrightarrow & Y_1 \\
	I_2 \in \Pi & \longrightarrow & Y_2 \\
	\end{array}
\right\} Y
instanci problému \Pi rozložíme na menší instance problému \Pi a vyřešíme je. Získaná řešení Y_1 a Y_2 pak sloučíme do výsledného řešení Y původní instance problému \Pi.

Podle specifických vlastností lze dekompozice rozdělit do tří skupin.

Přibližná dekompozice 
Pokud jsou Y_1 resp. Y_2 optimálními řešeními instancí I_1 resp. I_2, pak je Y řešením (ne nutně optimálním) instance I. Pokud Y_1, Y_2 neexistují, nevíme nic.
Čistá dekompozice 
Pokud jsou Y_1 resp. Y_2 optimálními řešeními instancí I_1 resp. I_2, pak je Y optimálním řešením instance I. Pokud Y_1, Y_2 neexistují, Y také neexistuje.
Přesná dekompozice 
Taková čistá dekompozice, že každé optimální řešení Y se dá složit z nějakých optimálních řešení Y_1 a Y_2 (ze všech optimálních řešení Y_1, Y_2 se dají složit všechna optimální řešení Y.


Pokud je navíc dekompozice taková, že jedna z dekomponovaných instancí je triviální, hovoříme o redukci (přibližné, čisté, přesné).


Rozděl a panujEditovat

Algoritmy rozděl a panuj jsou založeny na přibližné dekompozici. Opakované řešení dekomponovaných instancí je řídké. Zvláštním případem jsou metody zmenši a panuj, kdy je potřeba řešit jen jednu z dekomponovaných instancí.


Dynamické programováníEditovat

Dynamické programování je čistá dekompozice. Dekomponované instance se dají charakterizovat malým počtem hodnot a řešení dekomponovaných instancí lze těmito hodnotami indexovat. Zároveň se dají dekomponované instance rozdělit do disjunktních tříd (stupňů) tak, že k výpočtu instancí jednoho stupně je třeba jen instancí právě jednoho jiného stupně.

Dynamické programování lze formulovat dvěma způsoby. Rekurzivní způsob vyjde ze zadané instance, stanoví, které podinstance je třeba řešit, až dosáhne triviálních instancí. V praxi se tento způsob nepoužívá.

Dopředná formulace také vyjde ze zadané instance, spočítá všechny složitější podinstance, až dosáhne zadané instance.

Řešení jednotlivých podinstancí se samozřejmě v obou případech zaznamenávají a jsou tak vždy počítány nejvýše jednou.


Složené globální metodyEditovat

Globální metody lze skládat z různých dekompozic. Principem je rekurzivní procedura, v každé úrovni dekompozice se použije nejlepší možná dekompozice. Výsledkem může být nalezené řešení, informace o tom, že řešení neexistuje, ale také to, že nevíme nic. Tam, kde je možné použít více dekompozic stejného druhu, udržujeme seznam těch, které nevedly k výsledku.


Lineární programováníEditovat

Máme dána reálná čísla a_{11} \ldots a_{mn}, b_1 \ldots b_m, c_1 \ldots c_n. Nalezněte reálná čísla x_1, x_2, \ldots{}, x_n tak, aby 
c_1x_1 + c_2x_2 + \ldots + c_nx_n
bylo maximální. Zkráceně aby \boldsymbol{c}^{T}\boldsymbol{x} bylo maximální. Přitom musí být splněna soustava podmínek


\begin{matrix}
a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n & \leq & b_1 \\
a_{21}x_1 + a_{22}x_2 + \ldots + a_{2n}x_n & \leq & b_2 \\
\vdots & & \vdots \\
a_{m1}x_1 + a_{m2}x_2 + \ldots + a_{mn}x_n & \leq & b_m \\
x_1, x_2, \ldots{}, x_n & \geq & 0
\end{matrix}

To lze také zkráceně zapsat jako \begin{matrix}
\boldsymbol{A}\cdot{}\boldsymbol{x} & \leq & \boldsymbol{b} \\
\boldsymbol{x} & \geq & 0
\end{matrix} Do slov přepsáno se jedná o řešení lineárních rovnic, zpravidla s určitým stupněm volnosti, kdy je počet rovnic menší než počet proměnných. Pak se volí některé proměnné jako parametry a dle optimalizačního kritéria se hledá nejlepší řešení (optimum).

Tvary lineárního programováníEditovat

Existuje několik tvarů, ve kterých se s lineárním programováním lze setkat.

Kanonický tvar 

Nelze pochopit (chyba při lexingu): \begin{matrix} \boldsymbol{c}^{T}\boldsymbol{x} & & \textrm{maximální} \\ \boldsymbol{A}\cdot{}\boldsymbol{x} & \leq & \boldsymbol{b} \\ \boldsymbol{x} & \geq & 0 \end{matrix}

Standardní tvar 

Nelze pochopit (chyba při lexingu): \begin{matrix} \boldsymbol{c}^{T}\boldsymbol{x} & & \textrm{maximální} \\ \boldsymbol{A}\cdot{}\boldsymbol{x} & = & \boldsymbol{b} \\ \boldsymbol{x} & \geq & 0 \end{matrix}

Obecný tvar 

Nelze pochopit (chyba při lexingu): \begin{matrix} \boldsymbol{c}^{T}\boldsymbol{x} & & \textrm{maximální} \\ \boldsymbol{A}\cdot{}\boldsymbol{x} & \left\{ \begin{array}{c} \leq \\ = \\ \geq \end{array} \right\} & \boldsymbol{b} \\ \boldsymbol{x} & \left\{ \begin{array}{c} \geq \\ \neq \end{array} \right\} & 0 \end{matrix}


Všechny tři tvary jsou vzájemně ekvivalentní. Standardní a kanonický tvar jsou speciálními případy tvaru obecného. Obecný tvar lze převést jak na kanonický, tak na standardní tvar.

Máme-li v původním obecném tvaru dané \boldsymbol{x} \neq 0, lze zavést dvě nové proměnné \boldsymbol{x}^+ a \boldsymbol{x}^- tak, že \boldsymbol{x} = \boldsymbol{x}^+ + \boldsymbol{x}^- (myšleno po složkách). Pak lze také původní rovnici \boldsymbol{a}_{i}\cdot{}\boldsymbol{x} = b_i pro jeden řádek matice \boldsymbol{A} zapsat jako dvě rovnice \begin{matrix}
\boldsymbol{a}_{i}\cdot{}\boldsymbol{x}^+ & \leq & b_i \\
-\boldsymbol{a}_{i}\cdot{}\boldsymbol{x}^- & \leq & -b_i \\
\end{matrix} které již, stejně jako rovnice pro \boldsymbol{x}^+ \geq 0 a \boldsymbol{x}^- \geq 0, vyhovují kanonickému tvaru.

Podobně lze postupovat i v případě převodu z obecného do standardního tvaru.


Prostor řešeníEditovat

Prostorem řešení je konvexní těleso. Aplikací optimalizačního kritéria získáme svazek nadrovnin (rovin), jehož průnik s tělesem prostoru řešení představuje výsledné řešení problému. Průnikem může být

  • vrchol (bod),
  • hrana (úsečka),
  • stěna (nadrovina, rovina).

Pokud nehledáme všechna řešení, stačí zabývat se jen vrcholy. Na množině vrcholů pak provedeme lokální prohledávání (třeba \uv{pouze nejlepší}). Zbývá dané vrcholy nalézt.

Máme-li n proměnných a jen m rovnic, obsahuje matice \boldsymbol{A} nejméně (n - m) lineárně závislých sloupců. Volbou m lineárně nazávislých sloupců volíme bázi a všechny proměnné, které neodpovídají sloupcům báze položíme rovny nule. Řešením zbylé soustavy rovnic dostaneme bázové řešení.


ŘešímeEditovat

Každému vrcholu odpovídá nějaká báze a každé bázi nějaké bázové řešení. Mějme například sedm proměnných x_1, x_2, \ldots{}, x_7 a čtyři rovnice pro omezující podmínky.

\begin{matrix}
x_1 + x_2 + x_3 + x_4 & = & 4 \\
x_1 + x_5 & = & 2 \\
x_3 + x_6 & = & 3 \\
3x_2 + x_3 + x_7 & = & 6 \\
\end{matrix}

Zvolíme-li si potom jako bázi poslední čtyři sloupce matice \boldsymbol{A}, můžeme položit x_1 = x_2 = x_3 = 0 a dostat tak řešení \boldsymbol{x} = (0, 0, 0, 4, 2, 3, 6).

Tak, teďka tedy máme nějaké řešení (odpovídající nějakému vrcholu který odpovídá nějaké bázi). Cenu tohoto řešení spočítáme\footnote{Proč není v tom vzorečku u ceny index i ale nějaký Bi mi není moc jasný. IMHO je cena stále stejná, takže nevím, proč by to nemělo jít samotným i. - IMHO s i to určitě půjde také. Tím Bi chtěl básník říci, že stačí dělat sumu přes bázi, ptže x_1 = x_2 = x_3 = 0} jako 
z = \sum_{i=1}^{m}x_{i}c_{Bi}
Na další vrchol se posuneme tak, že z báze nějaký sloupec vyhodíme a nahradíme ho jiným. Celé nejlépe tak, že cena výsledného řešení bude vyšší. Postup je docela dobře patrný ze slidů.

Jedna z metod, kterou lze toto dělat, je tzv. simplexová metoda. Složitost se odvozuje od počtu možných bází, kterých je {m \choose n}. Lze ji použít i pro diskrétní problémy, existují ale i metody s polynomiální složitostí.

Celočíselné lineární programováníEditovat

U celočíselného lineárního programování jsou všechny proměnné a koeficienty celočíselné (či ve speciálním případě dvouhodnotové 0/1). Řešení celočíselné úlohy má vždy horší optimalizační kritérium než řešení relaxované úlohy v oboru reálných čísel.


SlovníčekEditovat

Hamiltonova kružnice 
Uzavřená cesta v grafu (posloupnost neopakujících se hran), která obsahuje všechny uzly grafu a žádný v ní není (až na start/cíl) dvakrát.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

V síti Wikia

Náhodná Wiki