In de 2e practicumopgave bouwen we voort op de eerste. Opnieuw gaan we zaken naar Hamiltonkrings; deze keer gaan we echter gebruik maken van SAT solvers, in plaats van zelf depth-first search te implementeren. Hieronder worden de verschillende stappen beschreven die je dient te nemen.

Downloaden en installeren solvers

We gaan gebruik maken van een Python interface naar verschillende solvers, genaamd Numberjack. In eerste instantie gaan we ons beperken tot het gebruik van de MiniSat solver, die bij Numberjack meegeleverd wordt.

Volg hiertoe de volgende stappen.

1. Ga naar http://numberjack.ucc.ie/download
2. Download de ZIP file en unzip deze.
3. Ga de folder in en type make local_install (onder Windows moet Cygwin geinstalleerd zijn)
4. Let goed op de laatste regels; deze lezen: Remember to add the following lines to your .profile or .bashrc: ...
   Numberjack is na het bovenstaande commando wel geinstalleerd, maar Python kan het nog niet vinden. Hiertoe moet een omgevingsvariabele gedefinieerd worden. Als bash de shell is die je gebruikt, kun je dit eenmalig instellen door
   export PYTHONPATH=~/numberjack/Numberjack.0.1.10-11-24/local_lib:$PYTHONPATH
   in te typen. (Je moet de path wel instellen naar de plaats waar je Numberjack geinstalleerd had.)
5. Probeer een voorbeeld programma in te typen en uit te voeren:

   from Numberjack import *
   import MiniSat
   
   a,b,c = (Variable() for val in range(3))
   model = Model( ( (a==True) | ( b==False ) ) & ( (b==True) | ( a==False ) ) & (c==True) ) 
   solver = model.load('MiniSat')
   
   print solver.solve()
   print solver.printStatistics()
   print a,b,c
   
   

Zoeken naar Hamiltonpaths and Hamiltonkrings door middel van SAT solvers

De taak in deze opgave is om een CNF formulering van het Hamiltonkring probleem en het Hamilton path probleemmm te vinden. In het bijzonder moet je er rekening mee houden dat een Hamiltonkring:

• alle knopen bezoekt
• alle knopen precies 1 keer bezoekt
• samenhangend is (er kunnen geen twee kringen zijn die samen precies alle knopen 1 keer bezoeken)
• terugkeert waar hij begint

Een Hamiltonpath hoeft niet terug te keren waar deze begint. Om deze formulering te vinden moet je vragen beantwoorden zoals:

• Wat stellen de atomen/variabelen in de CNF formule voor?
• Wat stellen de verschillende clauses voor?

De Hamiltonpath code moet geimplementeerd worden als een functie in de Python code van het eerste practicum.

Houd er bij het inleveren rekening mee dat ook de leesbaarheid van je code beoordeeld zal worden: het is belangrijk dat je commentaar op neemt, waar nuttig, en namen voor je variabelen kiest die informatief zijn. Functies moeten overzichtelijk zijn en niet te lang.

Test je code in eerste instantie uit op kleine voorbeelden.

Evaluatie van de code

Na afloop van de vorige stap heb je twee algoritmen voor het zoeken naar Hamiltonkrings; gebruik je code om enkele experimenten te doen, en maak hier een kort verslag van (niet meer dan 4 pagina's).

In de eerste serie experimenten gebruik je de random graafgenerator van de eerste opgave. Herinner je dat deze generator twee parameters heeft:

• het aantal knopen
• de kans op een tak tussen knopen

Genereer eerst een aantal willekeurige grafen voor verschillende parameters en pas je Hamiltonkring algoritmen toe om een beeld te krijgen van de rekentijd van je algoritmes op de grafen. Doe vervolgens het volgende:

• kies een vast aantal knopen, en een bereik van tak-kans waarden. Run je algoritme voor elke keuze van aantal knopen en tak-kans tenminste 10 keer. Maak grafieken waarbij op de x-as de kans gegeven is, en op de y-as het aantal keer dat een Hamilton kring gevonden is. Komt het verband overeen met wat je zou verwachten? Maak daarnaast grafieken waarbij de op de x-as de kans gegeven is, en op de y-as de rekentijd die je beide algoritmen vragen. Had je dit verwacht?
• herhaal de vorige grafieken, maar deze keer voor een vaste tak-kans en een variabel aantal knopen op de x-as. Kies een tak-kans in de buurt van 0.5.

Ga tenslotte naar deze website en download de eer.txt file waarin je een graaf vindt van aangrenzende regionen in Europa. Beperk je in eerste instantie tot de Nederlandse provincies. Is er een Hamilton kring voor het bezoeken van alle Nederlandse provincies?

Inleveren

Lever zowel de code als een kort verslag in. De deadline is 19 oktober.