SMAWK-algoritm

SMAWK -algoritmen är en algoritm för att hitta minimivärdet i varje rad i en implicit definierad helt monoton matris . Den är uppkallad efter initialerna till dess fem uppfinnare, Peter Shor , Shlomo Moran , Alok Aggarwal, Robert Wilber och Maria Klawe .

Inmatning

För ändamålen med denna algoritm definieras en matris som monoton om varje rads minimivärde förekommer i en kolumn som är lika med eller större än kolumnen i föregående rads minimum. Det är helt monotont om samma egenskap är sant för varje submatris (definierad av en godtycklig delmängd av raderna och kolumnerna i den givna matrisen). På motsvarande sätt är en matris helt monoton om det inte finns en 2×2 submatris vars radminima finns i det övre högra och nedre vänstra hörnet. Varje Monge-array är helt monoton, men inte nödvändigtvis vice versa.

För SMAWK-algoritmen bör matrisen som ska sökas definieras som en funktion, och denna funktion ges som input till algoritmen (tillsammans med matrisens dimensioner). Algoritmen utvärderar sedan funktionen när den behöver veta värdet på en viss matriscell. Om denna utvärdering tar O ( 1 ), då, för en matris med r rader och c- kolumner, är körtiden och antalet funktionsutvärderingar båda O ( c (1 + log( r / c ))). Detta är mycket snabbare än O ( rc ) -tiden för en naiv algoritm som utvärderar alla matrisceller.

Metod

Grundidén med algoritmen är att följa en beskärnings- och sökstrategi där problemet som ska lösas reduceras till ett enda rekursivt delproblem av samma typ vars storlek är mindre med en konstant faktor. För att göra det, förbehandlar algoritmen först matrisen för att ta bort några av dess kolumner som inte kan innehålla ett radminimum, med hjälp av en stackbaserad algoritm som liknar den i Graham-skanningen och alla närmaste algoritmer med mindre värden. Efter denna fas av algoritmen kommer antalet återstående kolumner som mest att vara lika med antalet rader. Därefter anropar algoritmen sig själv rekursivt för att hitta radminima för de jämna numrerade raderna i matrisen. Slutligen, genom att söka i kolumnerna mellan positionerna för på varandra följande minima med jämna rader, fyller algoritmen i de återstående minima i de udda raderna.

Ansökningar

De huvudsakliga tillämpningarna av denna metod som presenteras i den ursprungliga artikeln av Aggarwal et al. var i beräkningsgeometri , att hitta den längsta punkten från varje punkt i en konvex polygon och att hitta optimala omslutande polygoner. Efterföljande forskning fann tillämpningar av samma algoritm för att dela upp stycken i rader , förutsägelse av sekundär RNA- struktur, DNA- och proteinsekvensanpassning , konstruktion av prefixkoder och bildtröskelvärde , bland annat .