Online algoritmus - Online algorithm

Ve výpočetní technice je online algoritmus takový, který dokáže zpracovávat jeho vstup kousek po kousku sériovým způsobem, tj. V pořadí, ve kterém je vstup přiváděn do algoritmu , aniž by měl k dispozici celý vstup od začátku.

Naproti tomu offline algoritmus má od začátku všechna data problému a je vyžadován k výstupu odpovědi, která řeší problém po ruce. V operačním výzkumu se oblast, ve které se online algoritmy vyvíjejí, nazývá online optimalizace .

Jako příklad, zvažovat třídění algoritmy výběru sort a insertion sort : výběr opakovaně sort vybere minimální prvek z netříděného zbytku a umístí ji na přední straně, který vyžaduje přístup k celému vstupu; jedná se tedy o offline algoritmus. Na druhou stranu třídění vkládání považuje jeden vstupní prvek za iteraci a vytváří částečné řešení bez ohledu na budoucí prvky. Třídění vkládání je tedy online algoritmus.

Pamatujte, že konečný výsledek řazení je optimální, tj. Správně seřazený seznam. U mnoha problémů se online algoritmy nemohou shodovat s výkonem offline algoritmů. Pokud je poměr mezi výkonem online algoritmu a optimálním offline algoritmem omezen, nazývá se online algoritmus konkurenční .

Ne každý offline algoritmus má účinný online protějšek.

Definice

Protože nezná celý vstup, je online algoritmus nucen činit rozhodnutí, která se později mohou ukázat jako ne optimální, a studium online algoritmů se zaměřilo na kvalitu rozhodování, která je v tomto nastavení možná. Konkurenční analýza formalizuje tuto myšlenku porovnáním relativního výkonu online a offline algoritmu pro stejnou instanci problému. Konkrétně je konkurenční poměr algoritmu definován jako nejhorší poměr jeho nákladů dělený optimální cenou přes všechny možné vstupy. Konkurenční poměr online problému je nejlepší konkurenční poměr dosažený online algoritmem. Intuitivně konkurenční poměr algoritmu poskytuje měřítko kvality řešení produkovaných tímto algoritmem, zatímco konkurenční poměr problému ukazuje důležitost znalosti budoucnosti tohoto problému.

Jiné výklady

Další pohledy na online vstupy do algoritmů viz

Příklady

Některé online algoritmy :

Problémy online

Problém ilustrující koncepty online algoritmů je Canadian Traveller Problem . Cílem tohoto problému je minimalizovat náklady na dosažení cíle ve váženém grafu, kde jsou některé hrany nespolehlivé a mohly být z grafu odstraněny. To, že hrana byla odstraněna ( selhala ), se však cestujícímu odhalí, až když dosáhne jednoho z koncových bodů hrany. Nejhorším případem tohoto problému je jednoduše to, že všechny nespolehlivé hrany selžou a problém se sníží na obvyklý problém s nejkratší cestou . Alternativní analýzu problému lze provést pomocí konkurenční analýzy. U této metody analýzy offline algoritmus předem ví, které hrany selžou, a cílem je minimalizovat poměr mezi výkonem online a offline algoritmu. Tento problém je dokončen na PSPACE .

Existuje mnoho formálních problémů, které nabízejí více než jeden online algoritmus jako řešení:

Viz také

Reference

externí odkazy