Jake de opportunistische Nightcrawler rijdt ‘s nachts rond in de stad. De politie afluisterend wacht Jake tot er een “interessante gebeurtenis” plaatsvindt, zoals een inbraak of een schietpartij. Van zodra dit wordt gesignaleerd snelt hij er naartoe om er videobeelden van op te nemen en deze te verkopen aan de meest biedende nieuwszender.

Jake merkt echter op dat hij steeds te laat aankomt. Hij besluit daarom een aantal mensen aan te nemen die elk strategisch gepositioneerd worden op “wachtposten” in de stad. Er wordt afgesproken dat bij elke melding van een “interessante gebeurtenis” de dichtsbijzijnde er naartoe moet.

De vraag is nu, hoeveel leden moet het Nightcrawler team tellen opdat elk deel van de stad binnen een bepaalde tijdspanne kan bereikt worden?

---

Een stad wordt voorgesteld door een ongerichte gewogen graaf van straten. Hiervoor gebruiken we de klasse UndirectedGraph uit de intussen goed gekende grafenbibliotheek¹ (javadoc²). Hierbij stelt elke top een kruispunt voor en elke boog een straat. De lengte van een straat wordt gegeven door het gewicht van de boog.

Implementeer de interface NightCrawler³ met een klasse genaamd BranchAndBoundCrawler. Zoals de naam suggereert schrijf je een branch-and-bound algoritme om in methode public Set<Set<Node>> minimalCoverage(UndirectedGraph graph, double maximumDistance) alle minimale bedekkingen met gegeven afstand te vinden.

We noemen een verzameling van toppen C een bedekking met afstand d als elke top in de gegeven graaf G op een afstand (in G) kleiner of gelijk aan d ligt. Zo’n bedekking C noemen we minimaal voor G als:

• er geen bedekkingen met afstand d voor G bestaan met minder toppen; en
• er geen bedekkingen met afstand d voor G bestaan waar de som van de (minimale) afstand van elke top in G naar de dichtste top in C kleiner is.

Met behulp van SimpleTest⁴ kan je jouw oplossing lokaal testen.

Bron: Vlaamse Programmeerwedstrijd 2017, categorie Academische Bachelors