"Schaken is wiskunde (3)" door Hans Meijer

Onderstaand schaakprobleem is het beroemde handelsreizigersprobleem. Een korte uitleg. Laten we veronderstellen dat onze handelsreiziger ergens in Driemanspolder in Zoetermeer woont. Hij heeft een vrouw en een dochter en hij schaakt graag, maar dit terzijde. Elke morgen veert hij op uit zijn bed omdat er een spannende dag vol avonturen op hem wacht. Hij gaat weer op stap om klanten te bezoeken en niets is leuker dan dat. Op een bepaalde dag moet hij twaalf klanten bezoeken en deze blijken stomtoevallig in de hoofdsteden van de Nederlandse provinci?n te wonen. De vraag die hij moet beantwoorden, en waarbij u hem kunt helpen, is hoe hij deze reis het beste kan plannen.

(J.W. Meijer, Cochabamba, 2009)

Onze handelsreiziger, laten we hem voor het gemak Manuel noemen, pakt er zijn schaakbord bij en zet de stelling erop. Hij plaatst zichzelf op veld b4. Ja, inderdaad, hij is niemand minder dan de witte koning. De overige stukken plaatst hij op velden die de twaalf hoofdsteden voor moeten stellen. Groningen is de zwarte toren op g7, Middelburg de witte toren op a2, enzovoort. Hij stelt zich nu de vraag die elke handelsreiziger zich stelt. Via welke route kan hij die dag het beste zijn klanten bezoeken? Uiteraard wil hij 's avonds weer graag bij moeder de vrouw thuis zijn en ook wil hij het liefst zo weinig mogelijk tijd kwijt raken aan reizen. Op die manier heeft hij maximaal de tijd om aan zijn klanten onderzoeksopdrachten te slijten. Nee, die Arthur Miller zag het totaal verkeerd met dat toneelstuk van hem over een handelsreiziger die aan het einde van zijn latijn was. Dit vak is een godsgeschenk. Manuel begint in gedachten lijnen tussen de stukken op het schaakbord te trekken. Zal hij eerst naar a4 of naar d4 gaan? Ook naar a2 of a6 afreizen lijken interessante opties. Al gauw is het in zijn hoofd een wirwar van lijnen maar dan schiet hem iets te binnen. Is dit niet een of ander probleem uit de grafentheorie? Hij loopt naar zijn boekenkast en haalt er het boekje 'Introductory Graph Theory' van Gary Chartrand uit 1977 uit en ja hoor op pagina 67 vindt hij het hoofdstuk 'The Salesman's Problem. An introduction to Hamiltonian Graphs'. Van die Hamilton heeft Manuel wel eens gehoord, hij heeft niet voor niets astrofysica in Groningen gestudeerd, en hij vermoedt dat collega Hamilton dit probleem wel opgelost zal hebben. Dat is mooi denkt hij. Het leven lacht hem toe. Nauwelijks twee maanden geleden heeft hij voor de website van zijn schaakclub nog een column geschreven over 'Schaken en echte wiskunde' en nu ziet hij zijn inzicht in deze materie meteen beloond. In dat stukje ging hij in op paardensprongen op het schaakbord en legde hij, voor al die schakers die weinig meer doen dan posities tellen en geen flauw benul hebben van de echte wiskunde, een link met de grafentheorie. Zijn kennis van de grafentheorie lijkt hem op deze zonnige morgen goed van pas te komen. Er wacht hem echter een koude douche als hij in het boekje leest: 'Ondanks de eenvoud van het handelsreizigersprobleem heeft men er tot nu toe nog geen effici?nte oplossing voor gevonden'. Hij staat er weer alleen voor, maar gelukkig is een handelsreiziger dat gewend. Anders dan anders probeert hij deze keer niet om zelf even in een handomdraai het probleem op te lossen maar sloft hij naar zijn PC en zoekt op het internet naar het 'traveling salesman problem'. Het kan zo maar zijn dat gisteren ergens in Peru of Bolivia een of andere 'wizzkid' dit probleem opgelost heeft en het zou toch jammer zijn als hij het wiel voor de tweede keer uitvond. Al gauw vindt hij dat een Griek met de naam Nicos Christofides er een algoritme voor geschreven heeft. Een Griek? Daar heeft hij het niet zo op. Ooit heeft een Griek met een rating van 1600 hem in Baden-Baden van het bord geveegd en daar heeft die misselijke Eggink zich toen in het clubblad vrolijk over gemaakt in een stukje met als titel 'Zorba strikes back'. Sindsdien wil hij met Grieken liever zo weinig mogelijk te maken hebben. Tot zijn tevredenheid leest hij dat het algoritme van Christofides niet altijd in staat is de meest effici?nte route te vinden. Dat had hij eigenlijk al verwacht. Die Griek lijkt een doodlopende weg.

Hij zou natuurlijk het probleem op kunnen lossen door net als een computer alle oplossingen af te tellen. Gezien de simpele stelling die er op het bord staat lijkt dit goed te doen maar dat zou een bewijs door opsomming zijn en dat is verachtelijke wiskunde. Nee, hij gaat zich natuurlijk niet verlagen naar het niveau van een Broekman of Meijer. Hij kijkt wel mooi uit.

Die Meijer stuurde hem vanuit Paraguay overigens een aardig verhaal. Naar aanleiding van een smeekschrift van Meijer had Manuel hem het bewijs van zijn paardensprong probleem uit zijn column per email toegestuurd. Tijdens zijn vakantie had Meijer in de bus op weg van Asunci?n naar Encarnaci?n het boekje van Chartrand doorgelezen en zijn bewijs doorgrond. Zo kras is die Meijer dus toch nog wel. In Encarnaci?n was Meijer tijdens een avondwandeling met zijn vrouw Gardenia nieuwsgierig bij een raam van een school stil blijven staan om te kijken waar de les over ging. Die bleek tot zijn stomme verbazing over grafentheorie te gaan en op het bord stond Euler's Koningsbergen bruggenprobleem. Een onderwerp dat in 'Schaken en echte wiskunde' ook al even door Manuel aangestipt was. Nu staan Meijer en hij voor de theologische vraag of hier de voorzienigheid Gods in te herkennen is of niet.

Wat het handelsreizigersprobleem betreft kiest Manuel ervoor om het zelf en exact op te lossen. Hij is toch zeker slimmer dan de rest! Net als tijdens zijn schaakpartijen zal hij onderweg de oplossing wel vinden. Hij kust zijn vrouw, stapt in zijn auto en rijdt Driemanspolder uit. Op weg naar de A12 werpt hij een muntje op. Kop is linksaf en munt rechtsaf. De Monte-Carlo methode. Hij stelt zich voor om eens uit te rekenen wat de kans is dat hij zo de optimale oplossing vindt.

1) Een interessante website over het handelsreizigersprobleem is http://www.tsp.gatech.edu