Konkurranseanalyse (online algoritme) - Competitive analysis (online algorithm)

Konkurransedyktig analyse er en metode som er oppfunnet for å analysere online algoritmer , der ytelsen til en online algoritme (som må tilfredsstille en uforutsigbar sekvens av forespørsler, fullføre hver forespørsel uten å kunne se fremtiden) sammenlignes med ytelsen til en optimal offline algoritme. som kan se rekkefølgen av forespørsler på forhånd. En algoritme er konkurransedyktig hvis konkurranseforholdet - forholdet mellom ytelsen og ytelsen til den offline-algoritmen - er avgrenset. I motsetning til tradisjonell worst-case-analyse , hvor ytelsen til en algoritme bare måles for "harde" innganger, krever konkurransedyktig analyse at en algoritme fungerer godt både på harde og enkle innganger, hvor "harde" og "enkle" er definert av ytelsen. av den optimale frakoblede algoritmen.

For mange algoritmer er ytelsen ikke bare avhengig av størrelsen på inngangene, men også av deres verdier. For eksempel varierer det å sortere en rekke elementer i vanskeligheter, avhengig av opprinnelig rekkefølge. Slike dataavhengige algoritmer blir analysert for gjennomsnittlig og verste fall. Konkurransedyktig analyse er en måte å gjøre worst case-analyse for online og randomiserte algoritmer , som vanligvis er dataavhengige.

I konkurranseanalyse forestiller man seg en "motstander" som bevisst velger vanskelige data, for å maksimere forholdet mellom kostnaden for algoritmen som studeres og noen optimal algoritme. Når man vurderer en randomisert algoritme, må man ytterligere skille mellom en glemsom motstander , som ikke har kunnskap om de tilfeldige valgene som algoritmen setter mot den, og en adaptiv motstander som har full kunnskap om algoritmens interne tilstand når som helst under utførelsen. . (For en deterministisk algoritme er det ingen forskjell. Enten motstanderen kan ganske enkelt beregne hvilken tilstand algoritmen må ha når som helst i fremtiden, og velge vanskelige data deretter.)

For eksempel velger quicksort- algoritmen ett element, kalt "pivot", det vil si i gjennomsnitt ikke så langt fra sentrumsverdien til dataene som blir sortert. Quicksort skiller deretter dataene i to hauger, hvorav den ene inneholder alle elementer med en verdi som er mindre enn verdien av pivoten, og den andre inneholder resten av elementene. Hvis kviksort velger sving på en eller annen deterministisk måte (for eksempel alltid å velge det første elementet i listen), er det enkelt for en motstander å ordne dataene på forhånd slik at kviksort vil utføre i verste fall. Hvis imidlertid quicksort velger noe tilfeldig element for å være omdreining, kan en motstander uten kunnskap om hvilke tilfeldige tall som kommer opp ikke ordne dataene for å garantere worst-case-utførelsestid for quickort.

Den klassiske on-line problem først analysert med konkurranseanalyse ( Sleator og Tarjan 1985 ) er det listen oppdatering problemet : Gitt en liste over elementer og en sekvens av forespørsler om de forskjellige elementene, minimalisere kostnadene for å få tilgang til en liste hvor elementene nærmere foran på listen koster det mindre å få tilgang. (Vanligvis er kostnadene ved å få tilgang til en vare lik posisjonen i listen.) Etter en tilgang kan listen omorganiseres. De fleste omorganiseringer koster. Den Move-To-Front algoritme flytter bare bedt element til fronten etter tilgang, uten kostnader. De transponere algoritmen bytter den tilgjengeliggjorte elementet med elementet umiddelbart før det, også uten kostnader. Klassiske analysemetoder viste at Transponering er optimal i visse sammenhenger. I praksis presterte Move-To-Front mye bedre. Konkurransedyktig analyse ble brukt for å vise at en motstander kan få Transpose til å fungere vilkårlig dårlig sammenlignet med en optimal algoritme, mens Move-To-Front aldri kan gjøres for å pådra seg mer enn dobbelt så mye kostnaden for en optimal algoritme.

Når det gjelder onlineforespørsler fra en server, brukes konkurransedyktige algoritmer for å overvinne usikkerhet om fremtiden. Det vil si at algoritmen ikke "kjenner" fremtiden, mens den imaginære motstanderen ("konkurrenten") "vet". Tilsvarende ble konkurransedyktige algoritmer utviklet for distribuerte systemer, der algoritmen må reagere på en forespørsel som ankommer et sted, uten å "vite" hva som nettopp har skjedd et eksternt sted. Denne innstillingen ble presentert i ( Awerbuch, Kutten & Peleg 1992 ).

Se også

Referanser

  • Sleator, D .; Tarjan, R. (1985), "Amortized efficiency of list update and paging rules", Communications of the ACM , 28 (2): 202–208, doi : 10.1145 / 2786.2793 .
  • Aspnes, James (1998), "Konkurransedyktig analyse av distribuerte algoritmer", i Fiat, A .; Woeginger, GJ (red.), Online Algorithms: The State of the Art , Lecture Notes in Computer Science, 1442 , s. 118–146, doi : 10.1007 / BFb0029567 .
  • Borodin, A .; El-Yaniv, R. (1998), Online Computation and Competitive Analysis , Cambridge University Press, ISBN   0-521-56392-5 .
  • Awerbuch, B .; Kutten, S .; Peleg, D. (1992), "Competitive Distributed Job Scheduling", ACM STOC, Victoria, BC, Canada .