In de Ban van de Cirkel: Een nieuwe heuristiek voor circle-packing
Cirkels fascineren. Formules op een papyrusrol uit het tweede millennium voor Christus doen hun uiterste best om voor de eerste keer in de geschiedenis de oppervlakte van een cirkel te berekenen. Wanneer aliens de aarde bezoeken, dan is de boodschap bij uitstek die ze voor ons achterlaten een eenvoudige maar o-zo mysterieuze cirkel. Waarom laten ze geen vierkant achter? Of een barcode? Waarom spendeert de arme Egyptische papyrusschrijver zijn tijd aan het benaderen van pi en niet aan verfrissend bad in de Nijl? Dat mijn thesis antwoord geeft op één van die uiterst filosofische vragen, durf ik niet te beweren, maar ik hoop dat het stellen van die vragen wel één ding bewijst: mensen zijn gefascineerd door cirkels, en ze willen er al sinds het begin der tijden alles over weten. Geloof het of niet, maar informatica-studenten zijn ook mensen, en dus hoef ik het onderwerp van mijn thesis niet verder te verantwoorden: het virtueel puzzelen van kleine cirkels in één grote cirkel.
Stel, je hebt een cirkelvormig stuk land dat je wil laten begrazen door zoveel mogelijk geiten. Er is echter één probleem: die geiten kunnen elkaar niet uitstaan. Als het graasgebied van een geit overlapt met dat van een ander, dan komt er boel van. Je hebt gelukkig ook een aantal piketten en touwen van verschillende lengte. Het circle-packing probleem, waarover mijn thesis gaat, kan je in feite als volgt samenvatten: waar moet ik de pikketten in de grond slaan om zoveel mogelijk geiten gelukkig te maken, zonder dat hun territoria – eveneens cirkelvormig want begrensd door de lengte van het touw - overlappen.
Zelfs de meest agrarisch aangelegde lezers hebben wellicht hun vragen bij de relevantie van deze analogie, maar vervang die geiten misschien even door zendmasten en je ziet het licht. Hoe kan ik zendmasten – die hun signaal uitzenden in elke richting en dus een cirkelvormig bereik hebben – op zo’n manier plaatsen dat er een minimum aan gebieden is waar geen ontvangst is? Een algoritme dat een dergelijk probleem oplost kan een bedrijf miljoenen besparen, en menige tiener-romance in stand houden. Blijkbaar kan je circle-packing zelfs gebruiken om origami figuren van ongelooflijke complexiteit te bouwen (zoek maar eens op: black forest cuckoo clock origami).
Er zijn al verschillende pogingen gebeurd om het circle-packing probleem op te lossen, maar mijn thesis pakt het op een heel andere manier aan. Bijna al het voorgaande onderzoek ging ervan uit dat je de positie van alle cirkels tegelijk moet berekenen. Dat je het probleem in één enkele stap moet oplossen dus. Op die manier kan je heel nauwkeurig je cirkels samen puzzelen, met erg weinig verspilde plaats, maar deze manier van werken heeft één groot nadeel: het vraagt enorm veel rekenkracht om de posities van al die cirkels in één keer te berekenen. Elke cirkel hangt van elke andere cirkel af, en omdat je ze allemaal tegelijk probeert te plaatsen, schiet de processing power en rekentijd die je nodig hebt enorm de hoogte in. Vergelijk het met een puzzel die je probeert op te lossen door alle stukken tegelijkertijd in elkaar te passen, zonder er eerst eentje te leggen en dan nog eentje en daarop verder te bouwen. (Voorbeeld ter illustratie: met een dergelijk klassiek algoritme duurt het wel tot 24 uur om 30 cirkels samen te puzzelen. Niet zo efficiënt als je meer dan 30 geitjes hebt.)
Daar brengt mijn oplossing dus verandering in, en als je de titel van mijn thesis onder de loep legt, heb je de clue al door: Een nieuwe constructieve heuristiek voor het circle-packing probleem. Mijn methode om het circle-packing probleem op te lossen is “constructief”, wat wilt zeggen dat je het probleem aanpakt zoals elk zes jaar oud kind een legpuzzel oplost: stukje per stukje. Eerst plaatst het algoritme de drie grootste cirkels knus tegen elkaar. Daarna gaat het op zoek naar de grootst mogelijke cirkel die tussen die drie eerste cirkels past. Past er geen enkele, dan wordt de nieuwe cirkel aan de buitenkant geplaatst. Dan kijkt het algoritme of het een cirkel kan plaatsen in het nieuwe gat dat ontstaan is door de vierde cirkel te plaatsen. Past er geen, dan wordt nummer vijf aan de buitenkant geplaatst. En zo verder, tot je in een mum van tijd een enorme hoeveelheid cirkels bij elkaar gepuzzeld hebt. Als je de cijfers van daarnet nog in je hoofd hebt (24 uur voor 30 cirkels), dan geef ik nu even een tegenvoorbeeld: mijn methode doet over 1000 cirkels slechts 1 seconde, en de kwaliteit van de oplossingen is gelijkaardig (gemiddeld minder dan 6% slechter).
Dat cirkels ondertussen al hun geheimen hebben prijsgegeven, durf ik niet beweren, maar ik hoop dat mijn thesis ten minste een nieuwe manier aanreikt om na te denken over een abstract probleem dat misschien wel erg onverwachte toepassingen kan hebben. Hoe ver van de echte wereld een wiskundig vraagstuk ook lijkt te staan, er is altijd wel een geitenboer of een zendmastenbouwer die er mee aan de slag kan.
