Pakjesavond is NP-hard

Een route is makkelijk
Het berekenen van de kortste route tussen een vertrekpunt en een bestemming is relatief eenvoudig. Dit gebeurt bijvoorbeeld als je je TomTom gebruikt of als je Google om een route vraagt. Ook als je meerdere plaatsen langs wilt en je weet de volgorde, dan is dat dus niet zo moeilijk: je berekent eerst de route van je vertrekpunt naar je eerste bestemming, dan van je eerste bestemming naar de tweede, enzovoorts.

Een route is moeilijk
Maar het maakt Sinterklaas niet uit op welke volgorde hij langs de huizen gaat, als het maar zo snel mogelijk gaat. Helaas wordt dan het probleem een stuk moeilijker. Het is zelfs een zogenaamd NP-hard probleem: er bestaat waarschijnlijk geen efficiënte oplossing (net als mijn vorige probleem in Wat is snel?). Je vraagt je misschien af ‘Maar met de volgorde erbij is het makkelijk! Kun je ze niet gewoon allemaal proberen?’. Tja, dat kan inderdaad wel, maar hoeveel volgorden zijn er nu eigenlijk?

Gemak
Laten we voor het gemak even aannemen dat Sint de huizen per gemeente afgaat. Er zijn 403 gemeenten in Nederland. Sint begint in de eerste, dit is zijn vertrekpositie. Dan heeft hij nog 402 gemeenten over. Wanneer hij de eerste twee gemeenten heeft bezocht, zijn er nog 401 over, daarna nog 400, etc. Totdat er geen gemeenten meer over zijn. Dit betekent dat er 402 keer 401 keer 400 keer 399… enzovoort veel mogelijkheden zijn.

Explosiegevaar
Als je dit uitrekent, kom je uit op ongeveer 10 tot de macht 874. Dat wil zeggen, dit getal bestaat uit 875 cijfers! Zelfs al kost het berekenen van één optie maar 1 microseconde, en je doet dit op enkele miljarden computers tegelijk, dan is dit nog niet haalbaar: het kost vele malen meer tijd dan de tijd die is verstreken sinds de oerknal (en dat is ongeveer 13.7 miljard jaar). Het aantal opties explodeert naar mate er meer gemeenten zijn. En dan hebben we het nu alleen nog maar over gemeenten, bij huishoudens wordt het helemaal onmogelijk (zo’n 7.6 miljoen in plaats van 403).

De oplossing
Toch is het probleem van Sinterklaas iets makkelijker in de praktijk: het is bijvoorbeeld niet erg efficiënt om de hele tijd tussen Groningen en Zeeland op en neer te gaan. Je kunt geometrie gebruiken om vrij makkelijk een route te vinden die bijna even lang is als de kortste route.

Maar de echte oplossing komt van de hulpsinten en -pieten: die zijn er gelukkig ongeveer evenveel als dat er huishoudens zijn.