‘Kleine hersentjes lossen complex wiskundig probleem op’, kopt een persbericht van Royal Holloway, University of London. Gerefereerd wordt aan het Handelsreizigersprobleem, dat inderdaad een uiterst complex probleem in de wiskunde is: tot nu toe heeft geen mens dit probleem bevredigend kunnen oplossen, de huidige rekenkracht van computers ten spijt. Bijen zouden ons nu hebben verslaan, volgens biologen van de Londense universiteiten Queen Mary en de reeds genoemde Royal Holloway. De onderzoekers Mathieu Lihoreau, Lars Chittka en Nigel Raine publiceerden hun bevindingen in The American Naturalist. Het nieuws werd gretig opgepikt, ook door kwaliteitsmedia als The Guardian.

Kleine handelsreizigers

Wat presteren die bijen nu eigenlijk? Ze zijn in staat om telkens de kortste weg te kiezen tussen bloemen — bravo. Het Handelsreizigersprobleem uit de complexiteitstheorie gaat over de vraag wat de kortste route is tussen alle steden in een bepaald gebied. Er wordt vanuit gegaan dat de handelsreiziger beschikt over een afstandtabel en dus voor elk tweetal te bezoeken steden de onderlinge afstand weet. Het is zijn bedoeling om een route langs de steden te bepalen waarbij hij zo min mogelijk kilometers aflegt.

Bijen zijn dus eigenlijk kleine handelsreizigers: ze hebben zich aangeleerd om de kortste route tussen bloemen te vliegen. Deze insecten hebben blijkbaar van nature een effectieve oplossing voor het Handelsreizigersprobleem, aldus de onderzoekers. Volgens Nigel Raine van Royal Holloway is het opmerkelijk dat bijen dit probleem oplossen, omdat het brein van een bij ‘de grootte heeft van een graszaadje’. Raine maakte een weide van kunstbloemen om erachter te komen wat het vlieggedrag van de bij is. Het bleek dat na het verkennen van de locatie, de bijen al gauw de kortste route volgden.

Het handelsreizigersprobleem

Een handelsreiziger moet een bepaald aantal steden bezoeken en aan het eind weer terugkeren bij zijn vertrekpunt. Hij wil dat zo doen, dat elke stad precies één keer aan bod komt en bovendien moet de totaal af te leggen afstand zo klein mogelijk zijn. Tot op heden is er geen ideale oplossingsmethode gevonden voor dit Handelsreizigersprobleem. De handelsreiziger zou natuurlijk alle mogelijke circuits kunnen uitproberen, maar dat zijn er veel te veel: zelfs de snelste computers zouden daar miljarden jaren voor nodig hebben!

Daarom zijn er handige rekentrucs verzonnen waarbij niet alle mogelijkheden hoeven worden nagegaan. Met zo’n truc kon men in 1954 de kortste rondreis berekenen langs de toen nog 48 staatshoofdsteden in de VS. In 1980 berekende men een handelsreis langs 120 West-Duitse steden, inclusief Berlijn, en in 1987 een wereldreis langs 666 plaatsen verspreid over alle continenten, inclusief de Noord- en Zuidpool. Het huidige rekenrecord (uit 2004) voor het Handelsreizigersprobleem staat op 24.978 plaatsen, verdeeld over heel Zweden. De totale lengte daarbij is zo’n 72.500 kilometer en men heeft bewezen dat een korter circuit niet bestaat. In de figuur zie je deze route (in rood); klik op het plaatje voor een vergroting.

Deze oplossingen hebben betrekking op een specifiek netwerk van steden. Hoe je het Handelsreizigersprobleem in het algemeen oplost, is nog steeds een vraag waar wiskundigen hun tanden op stuk bijten.

Appels en peren

Hoe interessant het onderzoek naar het gedrag van bijen ook mag zijn – biologen moeten daar vooral mee doorgaan —, en hoe waardevol het onder de aandacht brengen van een groot open vraagstuk uit de wiskunde bij een breed publiek ook is, om de prestatie van de bijen te vergelijken met de oplossing van het Handelsreizigersprobleem is ridicuul. Voor het Handelsreizigersprobleem kennen we geen geen efficiënte manier om dit probleem in zijn algemeenheid te kunnen oplossen; in vakjargon: het probleem is NP-volledig. Met oneliners als ‘Computers zijn jaren bezig, maar de bij heeft razendsnel een oplossing’ worden twee zaken bij elkaar geharkt die niks met elkaar te maken hebben. Hoe weten we zeker dat die bijen in een netwerk van een paar duizend bloemen werkelijk de allerkortste route vinden en niet bij benadering de kortste route? En al zou het daadwerkelijk de kortste route zijn die de bijen vonden, hoe weten we dan dat de oplossing van de bijen ook optimaal is als we één bloem aan hun netwerk toevoegen?

Goede, snelle benaderingen van het Handelsreizigersprobleem bestaan al lang. Een efficiënte manier om een netwerk van een miljoen steden te doorzoeken, dat met grote kans leidt tot het vinden van een oplossing die 2 à 3 procent afwijkt van de optimale oplossing, is voor computers geen probleem meer. Maar in de wiskunde gaat het niet om een ‘ongeveer-oplossing’. Er is maar één werkelijk optimale oplossing en juist daarin zijn wiskundigen geïnteresseerd. Dat biologen andere interesses hebben, is prima, maar dan past wel het gezegde ‘Schoenmaker, blijf bij je leest’.