Mieren zijn in staat om tussen verschillende punten een vervoersnetwerk aan te leggen via de zo kortst mogelijke weg. Van nature lossen ze het wiskundige ‘Steinerboomprobleem’ op, zeggen onderzoekers van de universiteit van Sydney.
De onderzoeksvraag van de wetenschappers uit Sydney luidde: zijn mieren in staat om dit netwerkprobleem op te lossen, zonder leider en zonder kennis van de omgeving? En zo ja, hoe doen ze dat?
Met Argentijnse mieren (Linepithima humile) werden verschillende experimenten gedaan en steeds bleek dat deze insecten in staat waren om de kortste route te vinden. Tanya Latty, een van de onderzoekers: “Een mierenkolonie maakt zo veel mogelijk paden en kiest uiteindelijk voor het efficiëntste netwerk. Een slim algoritme om het beste netwerk te vinden, gebruiken de mieren dus niet. Het is gewoon een kwestie van trial and error.”
De onderzoekers stopten de mieren in een cirkelvormige arena waarin ze drie of vier nesten met elkaar moesten verbinden. De mieren waren in staat om op alle mogelijke manieren van het ene naar een ander nest te lopen. Na twee uur werden de mierenresultaten vergeleken met computer-gegenereerde beelden van het efficiëntste netwerk.
In elke situatie waren er steeds twee oplossingen die resulteerden in het kortste netwerk: de minimaal opspannende boom en de Steinerboom. De minimaal opspannende boom is het kortste pad tussen een stel punten, zónder dat daaraan extra punten worden toegevoegd. In het algemeen is de Steinerboom de werkelijk optimale oplossing: er mogen extra punten, de zogeheten Steinerpunten, worden toegevoegd, waardoor de totale lengte van de wegen meestal nog korter is dan in het geval van de minimaal opspannende boom.
De mieren wisten in het geval van drie punten een vierde punt aan te leggen. Via dat extra punt kan elk punt op de meest efficiënte manier bereikt worden. Hiermee hebben de mieren – zij het in een eenvoudig geval – een oplossing gevonden voor het Steinerboomprobleem.
Argentijnse mieren weten bij goede benadering de Steinerboom te vinden: gegeven drie punten, creëren ze een vierde punt (in het midden) om zodoende alle punten bereikbaar te maken via een zo kort mogelijk pad. Afbeelding: Tanya Latty
De minimaal opspannende boom is relatief makkelijk te vinden, ook als het netwerk uit duizenden punten bestaat; een bekend algoritme dat de minimaal opspannende boom in een graaf vindt, is het algoritme van Kruskal. Dat is anders bij de Steinerboom: wiskundigen kennen geen efficiënt algoritme om het Steinerboomprobleem in zijn algemeenheid op te lossen; het is een zogeheten NP-probleem.
Een Steinerboom met drie punten A, B en C en Steinerpunt S, en een Steinerboom met vier punten A, B, C en D en twee Steinerpunten S1 en S2
De onderzoekers beweren niet dat mieren iets kunnen waartoe computers niet in staat zijn. Het aantal punten in het mierennetwerk is immers klein en een efficiënte werkwijze hebben ze niet: ze proberen gewoon een hoop routes en kiezen uiteindelijk de beste. In de probeersels van de mieren zitten ook veel overbodige paden: omwegen, doodlopende routes enzovoorts. Toen in november vorig jaar een stel biologen beweerde dat bijen het Handelsreizigersprobleem kunnen oplossen, ook een NP-probleem, sloegen ze de plank behoorlijk mis. Die fout maken de mierenonderzoekers gelukkig niet.
Jakob Steiner (1796-1863)
De geschiedenis van het Steinerboomprobleem gaat terug tot de zeventiende eeuw, toen Pierre de Fermat (1601-1665) het volgende probleem beschreef: gegeven drie punten, vind een vierde punt waarvoor geldt dat de som van de afstanden naar die drie punten minimaal is. Evangelista Torricelli (1608-1647) loste dit probleem op; het gezochte punt staat dan ook bekend als het punt van Torricelli.
De Zwitser Jakob Steiner (1796-1863) generaliseerde het probleem van Fermat. In plaats van drie gegeven punten ging hij uit van n punten, en in plaats van het toevoegen van één extra punt, mogen er ook meerdere punten worden toegevoegd. Om de efficiëntste route te vinden die de vier hoekpunten van een vierkant verbindt, moet je niet één, maar twee punten toevoegen.
"
