Problem C
Labb L2: Konspirationsdetektion

1 Bakgrund

Foliehattarnas Riksförbund har beställt en programvara för att söka efter möjliga konspirationer i sociala nätverk. Ett socialt nätverk i den här uppgiften består av en uppsättning personer, och information om vilka par av personer som är bekanta med varandra.

En konspiration består av ett flertal personer: en mängd konspiratörer samt en spindel i nätet, med följande egenskaper:

• Spindeln i nätet är bekant med alla konspiratörer (men kanske även andra personer som inte är konspiratörer).

• Ingen av konspiratörerna är bekant med någon annan konspiratör (eftersom detta skulle dra misstanke till sig).

• Alla personer som inte redan är konspiratörer eller spindeln i nätet känner någon av konspiratörerna (så att konspirationen har inflytande över hela nätverket).

Databas

Det sociala nätverket du ska söka i kommer vara definierat via följande två predikat.

person(?X)

är sant om X är en person (så “person(X).” kan användas för att lista alla personer i databasen).

knows(?X, ?Y)

är sant om X känner Y. Observera att vi i den här uppgiften betraktar bekantskapsrelationen som symmetrisk – om $X$ känner $Y$ så är $Y$ bekant med $X$ – men i den Prolog-databas som ditt program kommer arbeta med kommer bara en av de två ordningarna vara definierad.

Databasen kommer att definiera ett relativt litet socialt nätverk, det kommer att ha högst $32$ personer.

Exempeldata och testning

Till er hjälp finns en uppsättning exempel-databaser inlagda i ert git-repo för labben, i katalogen “examples/”. I README.md-filen i ert git-repo finns detaljerade instruktioner om hur ni kan provköra med exempeldatabaserna samt hur man använder trace, om ni inte redan gjort detta.

2 Uppgift

1. Skriv ett predikat spider(?X) som är sant om X kan vara spindeln i nätet i en konspiration. När predikatet anropas med en okänd ska det generera varje möjlig spindel i nätet. Det spelar ingen roll i vilken ordning de genereras, men samma person ska inte genereras flera gånger (se exempel-databasen “example2.pl”).

2. Konstruera en egen exempel-databas för problemet där ert program tar väsentlig tid på sig (säg, mer än $10$ sekunder). Ert exempel får inte vara för stort – högst $500$ personer (vilket ju är mycket större än de $32$ personer som används i Kattis-testfallen), och ju mindre desto bättre.

Vid redovisning ska ni även kunna förklara hur sökningen efter lösningar fungerar i ert program (t.ex. på er egenkonstruerade databas), med hjälp av trace.

3 Vägledning

En bra början är att skriva predikat för de olika del-egenskaperna vi är intresserade av, t.ex.:

• Ett predikat som kollar om två personer känner varandra (dvs om antingen knows(X,Y) eller knows(Y,X) är sant.

• Ett predikat som givet en lista med personer kollar om det finns någon person utanför listan som inte känner någon i listan.

• Etc

Givet dessa kan en första lösning på problemet ha följande struktur, enligt “generate-and-test”-metoden.

1. Låt $s$ vara en person och $K$ en lista med (andra) personer.

2. Testa om $K$ kan vara konspiratörerna med $s$ som spindeln i nätet.

Utöver predikaten för att verifiera de önskade egenskaperna behöver du alltså skriva ett predikat som genererar alla möjliga delmängder av personer, ungefär på samma sätt som vi i exemplet från föreläsningen med permutations-sortering har ett predikat som genererar alla permutationer av en lista.

Du kan skicka in denna lösning till Kattis för att se hur långt den klarar sig. Du borde då klara ca de 20 första testfallen i Kattis (och sedan få Time Limit Exceeded), om du inte gör det så är det antagligen något som du gjort konstigt som vore värt att fixa innan du går vidare med en mer komplicerad lösning.

Hur ska vi ändra lösningen så att den blir snabbare? Istället för att generera hela listan $K$ och sedan testa om den uppfyller villkoren för att vara konspiratörerna kan man kontrollera vissa av villkoren medans listan genereras. På det sättet kommer man tidigt i genereringen upptäcka att en partiell lista av konspiratörer inte kommer leda till en lösning, och därmed slippa ägna tid åt att utforska den. Följande är ett bra sätt att uföra genereringen som ska vara tillräckligt snabbt för att klara testfallen på Kattis:

1. I varje steg har vi en lista $K$ med personer som vi valt ut som konspiratörer hittills, och en lista $P$ med personer som är ytterligare potentiella konspiratörer. Initialt är $K$ tom, och $P$ alla personer som känner $s$ (personen som vi försöker identifiera som spindel).

   Så länge $P$ inte är tom har vi två möjliga sätt att (rekursivt) gå vidare: vi tar ut den första personen $x$ i $P$:

   Fall 1:

   $x$ ska vara en konspiratör. Vi skapar en ny lista $K’$ genom att lägga till $x$ till listan $K$, och en ny lista $P’$ genom att ta bort $x$, och alla personer som känner $x$, ur $P$ (eftersom inga av dessa längre kan vara konspiratörer).

   Fall 2:

   $x$ ska inte vara en konspiratör. Vi låter då $K’ = K$, och skapar en ny lista $P’$ genom att ta bort $x$ ur $P$.

   I båda fallen fortsätter vi sedan rekursivt med de nya listorna $K’$ och $P’$.

   När listan $P$ är tom har vi genererat färdigt $K$ och kontrollerar huruvida det är en lösning.

2. I varje steg kontrollerar vi att alla personer i databasen som inte är med i $K$ eller $P$ känner minst en person i minst en av listorna $K$ och $P$. Om det finns en person som inte är med i $K$ eller $P$ och inte heller känner någon i $K$ eller $P$ så kommer den här grenen av sökningen inte att leda till någon lösning (Fundera på varför! På redovisningen ska du kunna förklara detta), och vi kan därför avbryta.

För att få din lösning att fungera kommer du att behöva förstå hur Prolog letar efter en lösning. Prologs trace-verktyg är mycket användbart för detta – om du inte redan använde det till labb L1 så ska du använda det nu. Den första exempel-databasen har lite instruktioner för hur man kan använda trace.