Oppregningsalgoritme - Enumeration algorithm

I informatikk er en oppregningsalgoritme en algoritme som teller svarene på et beregningsproblem . Formelt gjelder en slik algoritme for problemer som tar input og produserer en liste over løsninger, på samme måte som funksjonsproblemer . For hver inngang må oppregningsalgoritmen produsere listen over alle løsninger, uten duplikater, og deretter stoppe. Ytelsen til en opplisting algoritme er målt i forhold til den tid som er nødvendig for å produsere løsninger, enten i form av den totale tid som kreves for å produsere alle løsninger, eller i form av den maksimale forsinkelsen mellom to på hverandre følgende oppløsninger og i form av en forbehandling av gangen , regnes som tiden før du sendte ut den første løsningen. Denne kompleksiteten kan uttrykkes i form av størrelsen på inngangen, størrelsen på hver enkelt utgang eller den totale størrelsen på settet med alle utgangene, på samme måte som det som gjøres med utgangssensitive algoritmer .

Formelle definisjoner

Et oppregningsproblem er definert som et forhold over strengene i et vilkårlig alfabet : ${\ displaystyle P}$${\ displaystyle R}$ ${\ displaystyle \ Sigma}$

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

En algoritme løser hvis algoritmen for hver inngang produserer (muligens uendelig) sekvens slik at den ikke har duplikat, og hvis og bare hvis . Algoritmen skal stoppe hvis sekvensen er endelig. ${\ displaystyle P}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle y}$${\ displaystyle z \ in y}$${\ displaystyle (x, z) \ i R}$${\ displaystyle y}$

Vanlige kompleksitetsklasser

Oppregningsproblemer er studert i sammenheng med teorien om beregningskompleksitet , og flere kompleksitetsklasser har blitt introdusert for slike problemer.

En veldig generell slik klasse er EnumP , klassen av problemer hvor riktigheten av en mulig utgang kan kontrolleres i polynomisk tid i inngang og utgang. Formelt, for et slikt problem, må det eksistere en algoritme A som tar som inndata probleminngangen x , kandidatutgangen y , og løser avgjørelsesproblemet om y er riktig utgang for inngangen x , i polynomtid i x og y . For eksempel inneholder denne klassen alle problemer som tilsvarer å oppregne vitnene om et problem i klassen NP .

Andre klasser som er definert inkluderer følgende. I tilfelle problemer som også er i EnumP , ordnes disse problemene fra minst til mest spesifikke

• Output polynomial , klassen av problemer hvis komplette output kan beregnes i polynomial tid.
• Inkrementell polynomtid , klassen av problemer hvor, for alt i , at jeg kan -te utgang fremstilles i polynomtid i inngangsstørrelsen og i antall i .
• Polynomial delay , klassen av problemer der forsinkelsen mellom to påfølgende utganger er polynomial i inngangen (og uavhengig av utgangen).
• Sterk polynomforsinkelse , klassen av problemer der forsinkelsen før hver utgang er polynomisk i størrelsen på denne spesifikke utgangen (og uavhengig av inngangen eller fra de andre utgangene). Forbehandlingen antas vanligvis å være polynom.
• Konstant forsinkelse , klassen av problemer der forsinkelsen før hver utgang er konstant, dvs. uavhengig av inngang og utgang. Forbehandlingsfasen antas vanligvis å være polynomisk i inngangen.

Vanlige teknikker

• Backtracking : Den enkleste måten å telle opp alle løsningene er ved systematisk å utforske rommet for mulige resultater ( partisjonere det i hvert påfølgende trinn). Imidlertid kan det å utføre dette ikke gi gode garantier for forsinkelsen, det vil si at en backtracking-algoritme kan bruke lang tid på å utforske deler av rommet med mulige resultater som ikke gir opphav til en fullstendig løsning.
• Lommelykt-søk : Denne teknikken forbedrer tilbakesporingen ved å utforske rommet til alle mulige løsninger, men løser problemet ved hvert trinn om den nåværende delløsningen kan utvides til en delløsning. Hvis svaret er nei, kan algoritmen umiddelbart gå tilbake og unngå å kaste bort tid, noe som gjør det lettere å vise garantier for forsinkelsen mellom to komplette løsninger. Spesielt gjelder denne teknikken godt for selvreduserende problemer.
• Lukking under settoperasjoner : Hvis vi ønsker å telle opp den sammenhengende foreningen av to sett, kan vi løse problemet ved å telle det første settet og deretter det andre settet. Hvis foreningen ikke er usammenhengende, men settene kan telles opp i sortert rekkefølge , kan opptellingen utføres parallelt på begge settene, mens duplikater fjernes på farten. Hvis unionen ikke er usammenhengende og begge settene ikke er sortert, kan duplikater elimineres på bekostning av høyere minnebruk, for eksempel ved å bruke en hash-tabell . På samme måte kan det kartesiske produktet av to sett telles effektivt ved å telle ett sett og sammenføye hvert resultat med alle oppnådde resultater når man teller det andre trinnet.

Eksempler på oppregningsproblemer

• Det toppunkt opplisting problem , hvor vi får en polytop beskrives som et system av lineære ulikheter og vi må oppsummere de toppunktene av polytopen.
• Oppregner minimale tverrgående bilder av en hypergraf . Dette problemet er knyttet til monotone dualisering og er koblet til mange applikasjoner innen databaseteori og grafteori .
• Å telle svarene på et databasespørsmål , for eksempel et konjunktivt spørsmål eller et spørsmål uttrykt i monadisk andreordens . Det har vært karakteriseringer i databaseteorien om hvilke konjunktive spørsmål som kan telles med lineær forbehandling og konstant forsinkelse.
• Problemet med å oppregne maksimale klikker i et inngangsdiagram, f.eks. Med Bron – Kerbosch-algoritmen
• Viser opp alle elementene i strukturer som matroider og greedoids
• Flere problemer på grafer, for eksempel å telle opp uavhengige sett , baner , kutt osv.
• Oppregning av tilfredsstillende oppgaver for representasjoner av boolske funksjoner , f.eks. En boolsk formel skrevet i konjunktiv normalform eller disjunktiv normalform , et binært avgjørelsesdiagram som en OBDD , eller en boolsk krets i begrensede klasser studert i kunnskapssammensetning , for eksempel NNF .

Tilknytning til beregbarhetsteori

Begrepet oppregningsalgoritmer brukes også innen beregningsberegningsteori for å definere noen høykompleksitetsklasser som RE , klassen til alle rekursivt opptellbare problemer. Dette er klassen av sett som det finnes en oppregningsalgoritme som vil produsere alle elementene i settet: algoritmen kan kjøre for alltid hvis settet er uendelig, men hver løsning må produseres av algoritmen etter en endelig tid.

Referanser