Pekařská technika - Bakers technique - Wikipedia

v teoretická informatika, Bakerova technika je metoda navrhování schémata aproximace v polynomiálním čase (PTAS) pro problémy na rovinné grafy. Je pojmenován po Brenda Baker, který to oznámil na konferenci v roce 1983 a publikoval jej v Deník ACM v roce 1994.

Myšlenkou Bakerovy techniky je rozdělit graf na vrstvy, aby bylo možné problém optimálně vyřešit na každé vrstvě, a poté rozumným způsobem kombinovat řešení z každé vrstvy, což povede k proveditelnému řešení. Tato technika poskytla PTAS pro následující problémy: podgraf izomorfismus, maximální nezávislá množina, minimální vrcholový kryt, minimální dominující sada, minimum hrana dominující sada, maximální shoda trojúhelníků a mnoho dalších.

The teorie dvojrozměrnosti z Erik Demaine, Fedor Fomin, Hajiaghayi a Dimitrios Thilikos a jeho odnož zjednodušení rozkladů (Demaine, Hajiaghayi & Kawarabayashi (2005),Demaine, Hajiaghayi & Kawarabayashi (2011) ) zobecňuje a značně rozšiřuje použitelnost Bakerovy techniky pro celou řadu problémů rovinné grafy a obecněji grafy bez pevné vedlejší, jako jsou ohraničené rodové grafy, a také na další třídy grafů, které nejsou uzavřeny za braní nezletilých, jako je 1-rovinné grafy.

Příklad techniky

Příkladem, který použijeme k předvedení Bakerovy techniky, je maximální váha nezávislá sada problém.

Algoritmus

NEZÁVISLÁ SADA (${ displaystyle G}$, ${ displaystyle w}$, ${ displaystyle  epsilon}$) Vyberte libovolný vrchol ${ displaystyle r}$    ${ displaystyle k = 1 /  epsilon}$    najít první úrovně vyhledávání pro ${ displaystyle G}$ zakořeněné v ${ displaystyle r}$ ${ displaystyle { pmod {k}}}$: ${ displaystyle  {V_ {0}, V_ {1},  ldots, V_ {k-1} }}$    pro ${ displaystyle  ell = 0,  ldots, k-1}$        najít komponenty ${ displaystyle G_ {1} ^ { ell}, G_ {2} ^ { ell},  ldots,}$ z ${ displaystyle G}$ po odstranění ${ displaystyle V _ { ell}}$    pro ${ displaystyle i = 1,2,  ldots}$       vypočítat ${ displaystyle S_ {i} ^ { ell}}$, sada nezávislá na maximální hmotnosti ${ displaystyle G_ {i} ^ { ell}}$    ${ displaystyle S ^ { ell} =  pohár _ {i} S_ {i} ^ { ell}}$    nechat ${ displaystyle S ^ { ell ^ {*}}}$ být řešením maximální hmotnosti mezi ${ displaystyle  {S ^ {0}, S ^ {1},  ldots, S ^ {k-1} }}$    vrátit se ${ displaystyle S ^ { ell ^ {*}}}$

Všimněte si, že výše uvedený algoritmus je proveditelný, protože každý ${ displaystyle S ^ { ell}}$ je spojení disjunktních nezávislých množin.

Dynamické programování

Dynamické programování se používá, když pro každou spočítáme množinu nezávislou na maximální hmotnosti ${ displaystyle G_ {i} ^ { ell}}$. Tento dynamický program funguje, protože každý ${ displaystyle G_ {i} ^ { ell}}$ je ${ displaystyle k}$-uteruterární graf. Mnoho problémů NP-Complete lze vyřešit zapnutím dynamického programování ${ displaystyle k}$-uteruterární grafy. Bakerovu techniku ​​lze interpretovat tak, že dané rovinné grafy překrývá podgrafy tohoto typu, pomocí dynamického programování najde řešení pro každý podgraf a slepí řešení.

Reference