Hodnota Klam - Klam value

V parametrizovaná složitost z algoritmy, hodnota klam parametrizovaného algoritmu je číslo, které ohraničuje hodnoty parametrů, u nichž lze rozumně očekávat, že algoritmus bude praktický.^[1] Algoritmus s vyšší hodnotou klam lze použít pro širší rozsah hodnot parametrů než jiný algoritmus s nižší hodnotou klam. Hodnota klam byla nejprve definována pomocí Downey a Kolegové  (1999 ),^[2][3] a od té doby ho používají další výzkumní pracovníci v parametrizované složitosti, a to jak ke způsobu vzájemného porovnání různých algoritmů, tak ke stanovení cílů pro budoucí vylepšení algoritmu.

Definice

Algoritmus se říká, že je fixovatelný s pevnými parametry, pokud počet elementárních operací, které provádí, má vazbu na formu ${ displaystyle O (n ^ {c}) + f (k)}$, kde ${ displaystyle n}$ je určitá míra velikosti vstupu (například počet vrcholy v graf ), ${ displaystyle k}$ je parametr popisující složitost vstupu (například šířka stromu grafu), ${ displaystyle c}$ je konstanta, na které nezávisí ${ displaystyle n}$ nebo ${ displaystyle k}$, a ${ displaystyle f}$ je vypočítatelná funkce.

Vzhledem k časové vazbě této formy je hodnota klam algoritmu (nebo přesněji časové vazby) definována jako největší hodnota ${ displaystyle k}$ takhle ${ displaystyle f (k)}$ nepřekračuje „určitou rozumnou absolutní vazbu na maximální počet kroků libovolného výpočtu“.^[1] Přesněji obojí Downey & Fellows (1999) a Niedermeier (1998) použijte číslo 10²⁰ protože toto vázané, a toto bylo následováno pozdějšími vědci. Chcete-li zabránit uměle zlepšovat hodnotu klam algoritmu tím, že více do jeho složitosti ${ displaystyle O (n ^ {c})}$ část vázaného času, Downey & Fellows (1999) také omezit ${ displaystyle c}$ být maximálně tři, platné pro mnoho známých zpracovatelných algoritmů s pevnými parametry.

Příklady

Niedermeier (1998) uvádí příklad vrcholový kryt, s jeho přirozeným parametrem (počet vrcholů v krytu). V té době měl nejznámější parametrizovaný časový limit ${ displaystyle f (k) = O (k ^ {2} 1,3248 ^ {k})}$. Řešení ${ displaystyle k ^ {2} 1,3248 ^ {k} = 10 ^ {20}}$ dává hodnotu klam přibližně 129. Nicméně ${ displaystyle k ^ {2}}$ část časově ohraničené lze z toho zjednodušit, čímž získáme ohraničení formy ${ displaystyle O (1,3248 ^ {k})}$ s větším konstantním faktorem skrytým v O-notaci a větší základnou exponentu skrytého v jeho přibližné desítkové hodnotě. pro jednoduchou exponenciální vazbu ${ displaystyle f (k) = c ^ {k}}$jako je tento, lze vyřešit přímo ${ displaystyle k = 20 / log _ {10} c}$ z nichž Niedermeier odvozuje hodnotu klam přibližně 165. Následný výzkum vyvinul parametrizované algoritmy krytí vrcholů s ${ displaystyle f (k) = O (1,2738 ^ {k})}$^[4] dává hodnotu klam přibližně 190. To znamená, že z této analýzy lze usoudit, že instance vrcholového krytu s velikostí krytu větší než 190 jsou mimo dosah tohoto algoritmu, ale instance, jejichž velikost krytu je dostatečně hluboko pod touto mezí, pravděpodobně budou řešitelný.

Dalším příkladem problému, ve kterém byla hodnota klam výslovně použita jako cíl pro budoucí výzkum, je problém s maximálním rozsahem listů, ve kterém je cílem najít a kostra grafu s co největším počtem uzlů listů (parametrizováno počtem listů). Fellows a kol. (2000) vyvinout algoritmus pro tento problém, který porovnávají pomocí hodnoty klam s předchozí prací na stejném problému: předchozí algoritmy měly hodnoty klam 1 a 5 a jejich hodnota klam byla 16.^[5] Navrhují však také, že by mělo být možné poskytnout vylepšené algoritmy pro tento problém s hodnotou klam alespoň 50. Ačkoli to zůstává otevřené, několik pozdějších článků postupně zlepšilo hodnotu klam tohoto problému na 37.^[6]

Reference