Je leest:

Grijze blob lost wiskundeprobleem op

Grijze blob lost wiskundeprobleem op

Auteur: | 1 april 2013

Informatici van de University of the West of England hebben met behulp van de computer een blob gemaakt, die de kortste route langs steden kan vinden.

Het is de computerdeskundigen gelukt om met behulp van een digitale blob het handelreizigersprobleem op te lossen. Dit is al lange tijd een moeilijke puzzel voor wiskundigen en informatici. Stel je bent een deur-aan-deur-verkoper en je moet zestien steden langs. Je wilt graag weten hoe je deze steden langs moet gaan om zo min mogelijk kilometers af te leggen. De kortste route vinden is niet heel lastig; je kijkt gewoon hoe lang alle verschillende routes zijn en je kiest de kortste. Maar dat berekenen duurt erg lang en hoe meer steden het zijn, hoe langer het duurt. Het liefst zou je een snellere manier willen vinden. Maar dat lukt wiskundigen nu al zo lang niet.

Benaderingen

Omdat een kortste route zo moeilijk te vinden is, werken veel informatici tegenwoordig met computerprogramma’s die benaderingen van de route maken. Daarmee heb je niet de ideale route, maar het verschil met die route is vaak erg klein. In de praktijk zijn de benaderingen daarom heel goed te gebruiken.

Wat is de blob?

De blob is een monster uit een oude science fiction film. Dit monster verteerde alles waarmee het in aanraking kwam. De blob uit dit onderzoek is net eventjes anders. Het is een (in de computer gesimuleerde) grijze slurrie die (opnieuw, in de computer) over een aantal punten (de steden van het handelreizigersprobleem) wordt gelegd. Vervolgens begint de blob te krimpen, net zolang tot het alle punten strak omvat. Deze simulaties zie je in het onderstaande filmpje. De onderzoekers raakten geïnspireerd door slijmzwammen, die zichzelf verspreiden op eenzelfde manier. Dit zijn blobs uit het echte leven.

Ook de grijze blob geeft een benadering van de kortste route. Volgens de onderzoekers verschilde de ‘blobroute’ tussen de vier en negen procent van de kortste route. Dat is helemaal niet verkeerd. Bovendien is deze manier indrukwekkend omdat hij niet werkt zoals de meeste kortste-route-programma’s.

Miniblobjes

De blob bestaat namelijk eigenlijk uit duizenden kleine blobjes. Deze hebben allemaal, individueel, een simpele opdracht meegekregen: beweeg naar het punt toe dat het dichtst bij is én nog niet bezocht is door een ander blobje. Op deze manier, zo bleek, vormt de grijze blob langzaam een mooi specifiek pad langs van te voren aangegeven punten. Het is net als de wave in een voetbalstadion: allemaal mensen doen 1 ding, maar het geheel van de tribunes lijkt als één te bewegen. Dit is mooi te zien in de filmpjes van de simulaties.

De onderzoekers zelf waarderen de eenvoud van hun oplossing. Ook denken ze dat de manier waarop het kortste pad op natuurlijke wijze verschijnt, in plaats van door een vantevoren beschreven programma, topeassingen zou kunnen hebben in andere problemen.

Bron

  • Jeff Jones, Andrew Adamatzky, Computation of the Travelling Salesman Problem by a Shrinking Blob, ArXiv (20 maart 2013) DOI: arXiv:1303.4969
Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 01 april 2013

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.