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.
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.
http://www.youtube.com/watch?v=VCMe0gtR58M
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.