Algoritme bepaalt hoe je efficiëntst afscheidskussen geeft
Foto: afp
Kunnen algoritmes ook gewoon maatschappelijk nut hebben, zonder dat ze de belangen van commerciële partijen hoeven te dienen? Welzeker, of wat dacht u van professor Benders afscheids­zoenenalgoritme?

Dat algoritme probeert een oplossing te formuleren voor een regelmatig weerkerende en steevast gênante kwestie in het sociale verkeer: hoe zoen je bij het afscheid nemen na een feest of een receptie, het efficiëntst alle genodigden gedag? Of in wiskundige termen: wat is de meest ­efficiënte manier om, gegeven een rechthoekige ruimte met n personen erin, elk paar ­personen elkaar ten afscheid te laten zoenen?

Professor Bender, zo meldt de satirische website Improbable Research, is met de hulp van zijn collega’s Ritwik Bose, Rezaul Chowdhury en Samuel McCauley een eind in de richting van een antwoord opgeschoten. Een weergave van de resultaten is opgenomen in Fun with algorithms, lecture notes in computer science, onder de titel ‘The kissing problem: how to end a gathering when everyone kisses everyone else goodbye.’

Heel ingewikkeld is het niet, blijkt uit dat artikel. Toch niet voor wie weet wat boustrophedon-algoritmes zijn, want die lossen het probleem op. Maar voorlopig enkel voor genodigden die zich in een recht­hoekige feestzaal bevinden.

Dat is een ernstig manco van hun onderzoeksuitkomst, geven Bender en de zijnen toe. ‘Dit artikel behandelt enkel ten afscheid zoenen in rechthoekige ruimtes. Hoe snel een bijeenkomst beëindigd kan worden in een minder sober uitgevoerde ruimte dan een rechthoek, is niet nagegaan. Hoe het zit met veelhoekige ruimtes met rechte dan wel gebogen ­muren, evenmin. En hoe moeten we het ten afscheid zoenen modelleren na afloop van partijtjes waarbij mensen op de tafels klimmen? De complexiteit van het kusprobleem blijft groot.’

Die complexiteit wordt overigens nog opgedreven, meldt de redactie van ­Improbable Research, als je de vraag meeneemt langs welke kant afscheidnemers beginnen te kussen. Meer in het bijzonder: wat gebeurt er als iemand die bij voorkeur eerst het hoofd naar links keert (wat in westerse landen gebruikelijk is), stoot op iemand die eerst het hoofd naar rechts keert (wat in sommige buitenlanden gebruikelijk is). Wie ideeën heeft, mag zich ­melden bij Professor Bender.