Over breinen, handelsreizigers en combinatorische explosies

Het brein heeft met zo’n 100.000.000.000 neuronen een enorme rekenkracht. Door slim gebruik te maken van deze rekenkracht hebben wij, mensen, allerlei vaardigheden. Zo kunnen we talen leren, de wereld in 3D zien, grappen waarderen, en rondvliegende ballen opvangen. Dit is best knap. Deze vaardigheden kunnen bijvoorbeeld nog steeds niet nagebootst worden in robots.

map3Foto door Julian Tramper

Toch heeft ook het brein beperkte rekenkracht. Die beperkingen worden duidelijk op het moment dat wetenschappers wiskunde gaan gebruiken om de rekenkracht van het brein te beschrijven. Sommige berekeningen zijn namelijk zelfs voor een brein te moeilijk, ongeacht hoeveel je ook zou trainen of hoe lang je ook zou mogen nadenken.

Handelsreizigersprobleem
Neem bijvoorbeeld een schijnbaar eenvoudige puzzel genaamd het handelsreizigersprobleem. Een handelsreiziger wil de goedkoopste route reizen tussen een aantal steden. Dat lijkt niet zo heel moeilijk, maar het aantal routes dat de handelsreiziger kan reizen groeit exponentieel als een functie van het aantal steden. Voor 10 steden zijn er meer dan duizend mogelijke routes, en voor 50 steden zijn er al meer routes dan neuronen in het brein. Deze zogeheten combinatorische explosie groeit dus je hersenpan uit, en het vinden van de goedkoopste route betekent zoeken naar een naald in een hooiberg.

Hoe is het handelsreizigersprobleem nu relevant voor hersenonderzoek? Niemand denkt toch dat het brein handelsreizigersproblemen oplost? Dat zou je denken, ja. Toch zijn er meerdere theorieën over het soort berekeningen dat het brein in fracties van seconden doet. Bijvoorbeeld de manier waarop we waarnemen, of beslissingen maken om bijvoorbeeld binnen een fractie van een seconde een toegeworpen bal te vangen. De rekenkracht die hiervoor nodig is is zo groot, dat het handelsreizigersprobleem een fluitje van een cent zou moeten zijn, maar toch is dat niet zo.

Paradox
Dit leidt tot een paradox. Er is geen enkele manier om snel alle opties in de totale combinatorische explosie van het handelsreizigersprobleem te doorzoeken. Hoe kan het dan dat het brein een dergelijke berekening wel snel zou kunnen doen? De conclusie moet zijn dat de theorieën gewoon te veel mogelijkheden hebben. Daardoor kunnen ze in feite ook berekeningen veronderstellen die je de hersenpan uitrijzen.

Door meer gebruik te maken van de wiskunde achter combinatorische explosies kunnen we de rekenkracht van het brein, en haar beperkingen, beter in kaart brengen.

Vorige week gaf ik een workshop over dit thema op de Nationale Wiskunde Dagen. Zelf meer geïnteresseerd geraakt in wiskunde en het brein door dit verhaal? Je kunt hier meer over het onderwerp lezen.

Meer informatie
Artikel over Wiskunde en het Brein

Dit blog is geschreven door Iris van Rooij. Iris van Rooij is assistant professor aan het Donders Instituut waar ze de groep Computational Cognitive Science leidt, Ze doceert ook een Mastervak over het onderwerp van deze workshop bij opleiding Artificial IntelligenceDaarnaast houdt ze er van om combinatorisch explosieve spelletjes te spelen, zoals deze en deze.

1 thought on “Over breinen, handelsreizigers en combinatorische explosies

  1. Beetje pedant, maar strikt genomen weten we niet of het handelsreizigersprobleem niet snel op te lossen is. (Of heb je een bewijs van P ? NP in de la liggen?)

Laat een antwoord achter aan Bas Reactie annuleren

Het e-mailadres wordt niet gepubliceerd. Vereiste velden zijn gemarkeerd met *

Categories