Algoritmus SMAWK - SMAWK algorithm
SMAWK algoritmus je algoritmus pro zjištění minimální hodnoty v každé řadě implicitně definované zcela monotónní matrici . Je pojmenován podle iniciál svých pěti vynálezců, Petera Shora , Shlomo Morana , Aloka Aggarwala, Roberta Wilbera a Marie Klawe .
Vstup
Pro účely tohoto algoritmu je matice definována jako monotónní, pokud se minimální hodnota každého řádku vyskytuje ve sloupci, který je stejný nebo větší než sloupec minima předchozího řádku. Je zcela monotónní, pokud platí stejná vlastnost pro každou submatici (definovanou libovolnou podmnožinou řádků a sloupců dané matice). Ekvivalentně je matice zcela monotónní, pokud neexistuje submatice 2 × 2, jejíž minima řádků jsou v pravém horním a levém dolním rohu. Každé pole Monge je zcela monotónní, ale ne nutně naopak.
U algoritmu SMAWK by měla být matice, která má být prohledána, definována jako funkce a tato funkce je uvedena jako vstup do algoritmu (spolu s rozměry matice). Algoritmus poté vyhodnotí funkci, kdykoli potřebuje znát hodnotu konkrétní buňky matice. Pokud toto vyhodnocení trvá O ( 1 ), pak pro matici s řádky r a sloupci c je doba běhu a počet vyhodnocení funkce oba O ( c (1 + log ( r / c ))). To je mnohem rychlejší než doba O ( r c ) naivního algoritmu, který vyhodnocuje všechny buňky matice.
Metoda
Základní myšlenkou algoritmu je řídit se švestkovou a vyhledávací strategií, ve které je problém, který má být vyřešen, redukován na jediný rekurzivní dílčí problém stejného typu, jehož velikost je menší o konstantní faktor. K tomu algoritmus nejprve předzpracuje matici, aby odstranil některé její sloupce, které nemohou obsahovat minimum řádku, pomocí algoritmu založeného na zásobníku podobného algoritmu v Grahamově skenování a všech nejbližších algoritmech menších hodnot . Po této fázi algoritmu se počet zbývajících sloupců bude maximálně rovnat počtu řádků. Dále se algoritmus volá rekurzivně, aby našel minima řádků sudých řádků matice. Nakonec prohledáním sloupců mezi pozicemi po sobě jdoucích minim sudé řady algoritmus vyplní zbývající minima v lichých řádcích.
Aplikace
Hlavní aplikace této metody představené v původním příspěvku Aggarwal et al. byly ve výpočetní geometrii , při hledání nejvzdálenějšího bodu z každého bodu konvexního polygonu a při hledání optimálních uzavíracích polygonů. Následný výzkum našel mimo jiné aplikace stejného algoritmu při dělení odstavců na řádky , predikci sekundární struktury RNA , zarovnání sekvence DNA a proteinů , konstrukci kódů předpony a prahování obrazu .