DFS-släktingar och SAT-problem

Grafteori är ju ett stort och trevligt område, så jag tänkte beskriva några algoritmer till. Jag delar upp dem i två grupper, användbara och komplicerade, det här är de användbara hoppas jag.

1. Topologisk sortering

Vi börjar med något enkelt. Lite av detta togs upp på Spelteori men det förtjänar en egen beskrivning. Problemet uppkommer t.ex. då man har en massa saker att göra, men för att kunna göra en viss sak kanske man måste ha gjort ett antal andra saker innan, och frågan är i vilken ordning man ska göra sakerna. Eller om man ser det grafteoretiskt, givet en riktad, acyklisk graf (DAG), ordna noderna i en rad så att alla bågar går från vänster till höger.

Topologisk sortering av denna graf kan ge t.ex. BDECFHGA eller CBDEHGAF

Oftast räcker det med denna intuitiva lösning:

Spara hur många bågar A[v] som leder in till varje nod, d.v.s. ingraden för varje nod.
repeat
   Välj en nod v med A[v] = 0.
   För varje båge från v till en annan nod u, minska A[u] med 1.
until alla valda

Att det alltid finns en nod v med A[v] = 0 följer av att grafen är och förblir acyklisk under hela processen. Om A-värdena helt enkelt sparas i en array som söks igenom varje gång blir komplexiteten O(V^2). Om man dessutom använder en kö för att lägga 0-noderna i blir den O(E), vilket är optimalt.

Men å andra sidan kan följande O(E)-algoritm vara enklare att skriva:

Kör DFS på grafen och låt en "tidsräknare" öka med 1 varje gång en ny nod hittas. Spara för varje nod räknarens värde (sluttid) när noden lämnas, d.v.s. när du har sökt igenom allting nedanför noden och backtrackar för att gå tillbaka uppåt. Om noderna sorteras efter minskande sluttid så är detta en topologisk sortering. Beviset finns i Introduction to Algorithms (CLRS). I praktiken behöver man inte spara sluttiden utan man kan direkt placera noderna baklänges i en resultat-array allteftersom de är färdigbehandlade.

Med DFS menas här att man försöker starta rekursionen från alla möjliga noder (i valfri ordning), men att man aldrig besöker en nod som man redan har varit på. Räknaren ska alltså inte nollställas när en ny rekursion påbörjas. Anledningen att man måste starta från varje nod är att man inte kan förutsätta att alla noder går att nå var man än börjar. Detsamma kan också gälla i en oriktad graf om denna inte är sammanhängande, och då ger en sådan här multistarts-DFS de olika sammanhängande komponenterna i grafen, en för varje påbörjad rekursion.

2. Strongly connected components

I en sammanhängande komponent i en oriktad graf finns det minst en väg mellan varje par av noder. Man inför nu något liknande i en riktad graf, nämligen starkt sammanhängande komponenter , men kravet är nu att det mellan varje par av noder finns vägar i båda riktningarna. Exempel ges i figuren nedan.

En riktad graf (t.v.) och dess starkt sammanhängande komponenter i komponentgraf en (t.h.)

Att ta fram de starkt sammanhängande komponenterna kan precis som topologisk sortering göras på flera sätt. Jag skriver här den lite magiska algoritm som ges i CLRS.

1. Kör DFS på grafen och spara sluttiderna för varje nod (se topologisk sortering)
2. Kör DFS på grafen igen men med bågarnas riktning omvänd och starta rekursionen från noderna sorterade i en speciell ordning, nämligen efter minskande sluttider från 1. Varje rekursionsstart ger nu upphov till en starkt sammanhängande komponent. Källkod i C.

Uppdelningen i starkt sammanhängande koponenter kan ibland användas som en del av en annan algoritm. I vissa problem kan man nämligen strunta i hur bågarna går inuti en komponent och bara intressera sig för bågarna som går mellan olika komponenter. Dessa bågar tillsammans med komponenterna som noder bildar en ny, mindre graf, den s.k. komponentgrafen. Notera att komponentgrafen är acyklisk per definition.

Ett problem där uppdelningen kan vara användbar är 2-SAT. För att förklara detta måste jag först göra en kort utvikning och förklara vad det allmäna satisfierbarhetsproblemet SAT innebär.

3. Satisfierbarhetsproblem (SAT)

Antag att du har n booleanska variabler som var och en kan ha värdet sant eller falskt. Du får nu en logisk formel innehållande variablerna samt NOT (!), AND, OR och paranteser. Den fråga du ska besvara är om det är möjligt att tilldela variablerna sådana värden så att hela formeln blir satisfierad (d.v.s. får värdet sant). T.ex. är formeln

(x AND y) AND (!x OR !z) AND (z OR !y OR x)

satisfierbar eftersom du kan sätta x=sant, y=sant och z=falskt. Däremot är formeln

(x OR y) AND z AND (!z OR (!x AND !y))

inte satisfierbar. Det visar sig att problemet är NP-komplett, d.v.s. det finns antagligen inget sätt att lösa problemet som är fundamentalt bättre än att testa alla olika tilldelningar. Med hjälp av logik kan man visa att hur formeln än ser ut så går det att skriva en helt ekvivalent formel som har formen

(A₁₁ OR A₁₂ OR A₁₃) AND (A₂₁ OR A₂₂ OR A₂₃) AND .... AND (A_k1 OR A _k2 OR A_k3)

d.v.s. k paranteser åtdskilda med AND, vardera innehållande 3 literals åtskilda med OR, där varje literal kan vara antingen en variabel x, y .. eller en negerad variabel !x, !y ...Denna form kallas 3-CNF och problemet att kontrollera satisfierbarhet kan vi kalla 3-SAT. Eftersom varje formel kan skrivas i 3-CNF, måste naturligtvis även 3-SAT vara NP-komplett (annars skulle vi kunna lösa SAT polynomiskt genom att gå över till 3-CNF).

3-SAT är ett mycket väl studerat problem. Bl.a. kan man visa att om man gör en randomiserad algoritm som helt enkelt utgår från en slumpmässig tilldelning och sedan upprepande 3n gånger väljer en slumpmässig variabel i en parantes som inte är satisifierad och ändrar dess värde, och efter dessa 3n gånger börjar om med en ny tilldelning (Schöning's algoritm) så blir den förväntade exekveringstiden O(1,333^n) vilket är mycket bättre än den naiva sökningen som har O(2^n). Dessutom finns det naturligtvis många algoritmer som i praktiken är bättre. Dock är skillnaderna såpass små att 3-SAT är ganska ointressant som tävlingsuppgift.

Om vi däremot begränsar oss till 2 literals i varje parantes, så blir problemet plötsligt lösligt på linjär tid, O(n+k). Ett typexempel på detta problem, 2-SAT, är Excursion från BOI 2001, där varje person mostavarar en parantes och varje stad en variabel. 2-SAT kan lösas på olika sätt, t.ex. ger en sorts matchningsalgoritm rätt svar. Men det effektivaste och snyggaste är följande:

1. Antag att en av paranteserna är (x OR y). Rent logiskt så är detta uttryck ekvivalent med att om x inte är sant så måste y vara sant och om y inte är sant så måste x vara sant, d.v.s. !x ==> y, !y ==> x . Skapa nu en riktad graf där vi låter var och en av de 2n literals (x, !x, y, y! ...) representeras av en nod och varje parentes av två bågar där bågens riktning anger en implikation t.ex. !x ==> y. Med denna representation innebär problemet att välja en nod från varje nodpar (x, !x ) i grafen, där en båge från A till B innebär att om A väljs så måste också B väljas.
2. Gör en uppdelning av denna graf i starkt sammanhängande komponenter. Notera att om A och B tillhör samma komponent så måste antingen båda eller ingen av dem väljas. Om x och !x tillhör samma komponent så är formeln naturligtvis inte satisfierbar, glöm inte detta fall. Annars är problemet nu att välja ett antal komponenter så att en nod från varje nodpar kommer med samt att de kvarvarande bågarna i komponentgrafen lyds.
3. Gör en topologisk sortering av komponenterna.
4. Gå igenom komponenterna bakifrån (d.v.s. med början från den komponent som har utgrad 0). För varje komponent C, kolla om den har "förkastats" tidigare, annars välj den, d.v.s. låt alla literals i C vara sanna. Du har nämligen redan gått igenom det som topologiskt ligger efter C och där fanns tydligen ingen konflikt. När du väljer C måste du samtidigt förkasta alla komponenter D₁, D₂... som innehåller negationen till någon literal i C, och dessutom deras "förfäder" d.v.s. alla komponenter som har en väg till (implicerar) D_i.
5. Om du lyckas välja n literals så är formeln satisfierbar, annars inte.

Tävlingsuppgifter

Problem	Tävlingens hemsida	Hjälp och kommentarer
Excursion	BOI 2001
Network of Schools	IOI 1996
Manhattan	SM 2000
Rare Order XOR Following Orders	Problem Set Archive

Tillbaka