Uppräkningsalgoritm - Enumeration algorithm

Inom datavetenskap är en uppräkningsalgoritm en algoritm som räknar upp svaren på ett beräkningsproblem . Formellt gäller en sådan algoritm för problem som tar en input och producerar en lista med lösningar, liknande funktionsproblem . För varje ingång måste uppräkningsalgoritmen producera listan över alla lösningar utan dubbletter och sedan stoppa. Utförandet av en uppräkning algoritm mäts i termer av den tid som krävs för att producera de lösningar, antingen i termer av den totala tiden som krävs för att producera alla lösningar, eller i termer av den maximala fördröjningen mellan två på varandra följande lösningar och i form av en förbehandling tid , räknas som tiden innan den första lösningen matades ut. Denna komplexitet kan uttryckas som ingångens storlek, storleken på varje enskild utgång eller den totala storleken på uppsättningen av alla utgångar, på samma sätt som vad som görs med utgångskänsliga algoritmer .

Formella definitioner

Ett uppräkningsproblem definieras som en relation över strängar i ett godtyckligt alfabet : ${\ displaystyle P}$${\ displaystyle R}$ ${\ displaystyle \ Sigma}$

${\ displaystyle R \ subseteq \ Sigma ^ {*} \ times \ Sigma ^ {*}}$

En algoritm löser om algoritmen för varje ingång producerar (möjligen oändlig) sekvens så att den inte har någon duplikat och om och bara om . Algoritmen ska stanna om sekvensen är ändlig. ${\ displaystyle P}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle y}$${\ displaystyle z \ in y}$${\ displaystyle (x, z) \ i R}$${\ displaystyle y}$

Vanliga komplexitetsklasser

Uppräkningsproblem har studerats i samband med beräkningskomplexitetsteori , och flera komplexitetsklasser har införts för sådana problem.

En mycket allmän sådan klass är EnumP , klassen av problem för vilken riktigheten av en möjlig utgång kan kontrolleras i polynomtid i in- och utgången. Formellt måste det för ett sådant problem finnas en algoritm A som tar som inmatning av problemingången x , kandidatutgången y och löser beslutsproblemet om y är en korrekt utgång för ingången x , i polynomtid i x och y . Till exempel innehåller denna klass alla problem som motsvarar att räkna upp vittnen till ett problem i klassen NP .

Andra klasser som har definierats inkluderar följande. När det gäller problem som också finns i EnumP ordnas dessa problem från minst till mest specifika

• Output polynomial , klassen av problem vars fullständiga output kan beräknas på polynomial tid.
• Inkrementell polynomtid , den klass av problem där, för alla i , den jag kan produceras: e utgångskomposanten i polynomisk tid i inmatningsstorleken och i antalet jag .
• Polynomfördröjning , klassen av problem där fördröjningen mellan två på varandra följande utgångar är polynom i ingången (och oberoende av utgången).
• Starkt polynomfördröjning , klassen av problem där förseningen före varje utgång är polynomisk i storleken på denna specifika utgång (och oberoende av ingången eller från de andra utgångarna). Förbehandlingen antas i allmänhet vara polynom.
• Konstant fördröjning , klassen problem där fördröjningen före varje utgång är konstant, dvs oberoende av in- och utgången. Förbehandlingsfasen antas i allmänhet vara polynom i ingången.

Vanliga tekniker

• Backtracking : Det enklaste sättet att räkna upp alla lösningar är genom att systematiskt utforska utrymmet för möjliga resultat ( partitionera det vid varje successivt steg). Att utföra detta kan dock inte ge goda garantier för förseningen, dvs en backtracking-algoritm kan spendera lång tid på att utforska delar av rymden med möjliga resultat som inte ger upphov till en fullständig lösning.
• Ficklampasökning : Denna teknik förbättrar backtracking genom att utforska utrymmet för alla möjliga lösningar men lösa i varje steg problemet om den aktuella partilösningen kan utvidgas till en partiell lösning. Om svaret är nej kan algoritmen omedelbart gå tillbaka och undvika att slösa tid, vilket gör det lättare att visa garantier för fördröjningen mellan två kompletta lösningar. I synnerhet gäller denna teknik väl för självreducerande problem.
• Stängning under uppsatta operationer : Om vi ​​vill räkna upp den ojämna sammansättningen av två uppsättningar kan vi lösa problemet genom att räkna upp den första uppsättningen och sedan den andra uppsättningen. Om unionen inte är enskilt men uppsättningarna kan räknas upp i sorterad ordning kan uppräkningen utföras parallellt på båda uppsättningarna samtidigt som dubbletter i farten elimineras. Om facket inte är enskilt och båda uppsättningarna inte sorteras kan dubbletter elimineras på bekostnad av en högre minnesanvändning, t.ex. genom att använda en hash-tabell . På samma sätt kan den kartesiska produkten av två uppsättningar räknas upp effektivt genom att räkna upp en uppsättning och sammanfoga varje resultat med alla resultat som erhållits när man räknar upp det andra steget.

Exempel på uppräkningsproblem

• Den vertex uppräkning problemet , där vi får en polytop beskrivs som ett system för av linjära olikheter och vi måste räkna upp de hörn hos polytopen.
• Räknar upp de minimala transversalerna i en hypergraf . Detta problem är relaterat till monoton dualisering och är kopplat till många applikationer inom databasteknik och grafteori .
• Räknar upp svaren på en databasfråga , till exempel en konjunktiv fråga eller en fråga uttryckt i monadisk andra ordning . Det har förekommit karakteriseringar i databasteorin om vilka konjunktiva frågor som kan räknas upp med linjär förbehandling och konstant fördröjning.
• Problemet med att räkna upp maximala klick i ett inmatningsdiagram, t.ex. med Bron – Kerbosch-algoritmen
• Listar alla element i strukturer som matroider och greedoids
• Flera problem i grafer, t.ex. att räkna upp oberoende uppsättningar , banor , skärningar etc.
• Att räkna de tillfredsställande tilldelningarna av representationer av booleska funktioner , t.ex. en boolesk formel skriven i konjunktiv normalform eller disjunktiv normalform , ett binärt beslutsdiagram , såsom en OBDD , eller en boolsk krets i begränsade klasser som studerats i kunskapssammanställning , t.ex. NNF .

Anslutning till beräkningsbarhetsteori

Begreppet uppräkningsalgoritmer används också inom beräkningsbarhetsteorin för att definiera vissa höga komplexitetsklasser såsom RE , klassen för alla rekursivt uppräkbara problem. Detta är den klass av uppsättningar för vilka det finns en uppräkningsalgoritm som kommer att producera alla element i uppsättningen: algoritmen kan springa för evigt om uppsättningen är oändlig, men varje lösning måste produceras av algoritmen efter en begränsad tid.

Referenser