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 , kde je určitá míra velikosti vstupu (například počet vrcholy v graf ), je parametr popisující složitost vstupu (například šířka stromu grafu), je konstanta, na které nezávisí nebo , a 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 takhle 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 1020 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 část vázaného času, Downey & Fellows (1999) také omezit 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 . Řešení dává hodnotu klam přibližně 129. Nicméně část časově ohraničené lze z toho zjednodušit, čímž získáme ohraničení formy 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 jako je tento, lze vyřešit přímo z nichž Niedermeier odvozuje hodnotu klam přibližně 165. Následný výzkum vyvinul parametrizované algoritmy krytí vrcholů s [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
- ^ A b Niedermeier, Rolf (1998), „Some prospects for efficient fixed parameter algorithms“, in Rovan, Branislav (ed.), SOFSEM'98: Teorie a praxe informatiky, Přednášky v informatice, 1521, Springer, str. 168–185.
- ^ Downey, R. G.; Fellows, M. R. (1999), Parametrizovaná složitost„Monografie v informatice, Springer, s. 13–14, doi:10.1007/978-1-4612-0515-9, ISBN 0-387-94883-X, PAN 1656112.
- ^ Niedermeier (1998) používá hodnotu klam a byla zveřejněna dříve než Downey & Fellows (1999), ale dává koncept Downeymu a kolegům.
- ^ Chen, Jianer; Kanj, Iyad A .; Xia, Ge (2006), „Vylepšené parametrizované horní hranice pro vrcholový kryt“, MFCS 2006: Mathematical Foundations of Computer Science, Přednášky v informatice, 4162, Springer, str. 238–249, doi:10.1007/11821069_21, PAN 2298181.
- ^ Fellows, Michael R.; McCartin, Catherine; Rosamond, Frances A .; Stege, Ulrike (2000), „Koordinovaná jádra a katalytické redukce: vylepšený algoritmus FPT pro maximální velikost stromu a další problémy“, FST-TCS 2000: Základy softwarové technologie a teoretické informatiky, Poznámky k přednášce ve Výpočtu. Sci., 1974, Springer, Berlín, s. 240–251, doi:10.1007/3-540-44450-5_19, PAN 1850108.
- ^ Binkele-Raible, Daniel; Fernau, Henning (2014), „Parametrizovaná analýza měření a dobývání pro nalezení a k-leaf spanning tree in the unirected graph ", Diskrétní matematika a teoretická informatika, 16 (1): 179–200, PAN 3188035.