From Daan
Jump to: navigation, search

Vakvoorstel (pilot) “Mysteries of Hard and Easy Problems” (“MyHeap”)

Idee

Dus je hebt je case uit Heuristieken opgelost. Kinderspel. Hoe goed werken je algoritmes eigenlijk op andere huizenverdelingen, poortconfiguraties, zaalinrichtingen of tegelsets? Of nog algemener: hoe goed werken je algoritmes eigenlijk op ALLE probleeminstanties, en wat is het performanceverschil tussen de probleeminstanties onder die algoritmes ?


MyHEAP gaat door waar Heuristieken ophoudt. In plaats de het analyseren van algoritmes, gaan we de probleeminstanties analyseren, en proberen te ontdekken wat problemen makkelijker of moeilijker maakt. Is een probleem zo moeilijk als het beste algoritme? Of is probleemmoeilijkheid een intrinsieke eigenschap van het object zelf?


We genereren eerst honderd probleeminstanties per parametersetting (bijvoorbeeld: aantal huizen, of aantal nets), lossen ze op met de algoritmes en we gaan de oplossingen met elkaar vergelijken. Dan veranderen we parametersetting een stap en doen we de hele cycle nog een keer. En dan nog een keer. Honderd cycles van honderd experimenten in totaal, en we analyseren de resultaten. Zit er iets in de parametriseringen dat de kwaliteit van de oplossing voorspelt of juist niet? Is er een functioneel verband? En verschilt dat per algoritme? Daar gaan we iets over proberen te zeggen, aan de hand van flinke bakken zelfgegenereerde data. We’re getting serious now. This is heuristisch on steroids. This is MyHeap.


Ingangseisen?

Je hebt heuristieken afgerond met een 8 of hoger. Je hebt tenminste drie algoritmes (of drie varianten) uitgeprogrammeerd en een case opgelost.