Intelligente klodder blijkt goed in berekenen kortste route

Een intelligente klodder blijkt erg goed in het snel berekenen van de kortste route langs een aantal punten, een wiskundig probleem. Dit ontdekten Jeff Jones en Andrew Adamatzky van de University of the West of England. Ze publiceerden hun stuk op de website ArXiv.

Het is deze schimmel, de Physarum, die de insiratie vormde voor de onderzoekers Beeld thinkstock

De blob geeft een oplossing van het zogenoemde handelreizigersprobleem. Dit is een berucht probleem uit de informatica en de wiskunde. Het gaat over een denkbeeldige handselsreiziger, die een aantal steden langs moet met zijn waar.

Hij wil dit zo snel mogelijk doen en zoekt daarom de kortste route langs alle steden. Het vinden van die route is het probleem. Want het blijkt dat je álle mogelijk routes moet berekenen voordat je kan aanwijzen wat de kortste is. En dat kost veel tijd.

Daarom gebruiken informatici steeds vaker benaderingen van de kortste route. Ook deze blob geeft zo'n benadering, maar in tegenstelling tot veel andere computerprogramma's ontstaat deze oplossing op 'natuurlijke' wijze.

Daarmee bedoelen de onderzoekers dat ze niet de hele blob hebben geprogrammeerd om een kortste route te vinden. In plaats daarvan bestaat de blob uit heel veel kleine blobjes.

De onderzoekers hebben deze blobjes simpele instructies gegeven: ga naar jouw dichtstbijzijnde stad die nog niet bezocht is. De stipjes beginnen allemaal tegelijk te bewegen. Daardoor lijkt het alsof de blob één organisme is, terwijl het dus eigenlijk uit duizenden individuen bestaat. Zodra alle steden zijn bezocht, stoppen de stipjes ook meteen met bewegen. Dit is in de video goed te zien. Het resultaat is een verrassend goede benadering van de kortste route.

In het beste geval was de route 4 procent langer en in het slechtste geval negen procent langer dan de kortste route. Dat is goed genoeg om in de praktijk bruikbaar te kunnen zijn.

Meer over

Wilt u belangrijke informatie delen met de Volkskrant?

Tip hier onze journalisten


Op alle verhalen van de Volkskrant rust uiteraard copyright. Linken kan altijd, eventueel met de intro van het stuk erboven.
Wil je tekst overnemen of een video(fragment), foto of illustratie gebruiken, mail dan naar copyright @volkskrant.nl.
© 2019 DPG Media B.V. - alle rechten voorbehouden