Blob lost handelsreizigerprobleem op

[Drieske]

Blob lost handelsreizigerprobleem op


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.


Simulatie:


Lees meer: http://www.kennislin...undeprobleem-op


Publicatie: http://arxiv.org/abs/1303.4969

[Michel Uphoff]

Image1 1569 keer bekeken

Wat is nu de weg tussen de punten, die grijze blob paden?

Zo ja, dat is toch niet de kortste weg, of zie ik dat verkeerd?

[317070]

Het ziet er meer uit als Kruskal, en Kruskal is erg eenvoudig.

[Kwintendr]

Zo ja, dat is toch niet de kortste weg, of zie ik dat verkeerd?

Het is niet noodzakelijk het kortste pad. Het verschilt 4-9% van het kortste pad.

Wat is nu de weg tussen de punten, die grijze blob paden?

Dat is mij ook niet echt duidelijk. Wat zijn die nummers? Gewoon namen van steden of de volgorde waarin je de steden wil bezoeken?

[Michel Uphoff]

De bezoekvolgorde lijkt mij uitgesloten, dan komt er een idioot lange weg uit. Maar er wordt ook niet aangegeven hoe je de punten exact met elkaar verbindt, er zijn op diverse locaties meerdere wegen mogelijk. Bijvoorbeeld vanaf stad 1, daar kan je diverse keuzes maken.


Vind het niet indrukwekkend, maar misschien zie ik iets over het hoofd.

[317070]

Het artikel verheldert veel, maar al bij al ziet het er mij niet indrukwekkend uit. http://arxiv.org/abs/1303.4969

Volgens mij is het gewoon een fancy way om een hull met minimale inhoud te berekenen. En van die Kruskal lossen ze dan met een erg naïef algoritme travelling salesman op, die tot 9% afwijkt van de optimale oplossing (wat vrij veel is).


Kortom, het is een originele aanpak, maar een compleet waardeloos algoritme.

[Drieske]

Bij het posten had ik het artikel nog niet doorgenomen, wat ik nu een paar reacties te lezen wel eens heb gedaan. Het artikel verheldert veel (zie ook mijn openingspost voor die link). Het toont vooral aan dat de nieuwssites (niet alleen kennislink) veel te spectaculair berichten . Jammer eerlijk gezegd.


Edit: wat 317070 zegt dus

[Bartjes]

Bestaat er ook een scherpe eenduidige omschrijving van het type oplossingen dat acceptabel gevonden wordt?


In principe kan men immers alle mogelijke wegen doorrekenen en dan de kortste kiezen, hoewel dat in de praktijk al snel ondoenlijk wordt. Het lijkt een beetje op het zoeken naar een formule voor het n-de priemgetal. Op basis van uitproberen kan men daar ook wel een formule voor in elkaar zetten, maar de concrete berekening wordt dan eveneens al snel ondoenlijk.


De termen “doenlijk” en “ondoenlijk” zijn echter nogal vaag.

[Xenion]

De termen “doenlijk” en “ondoenlijk” zijn echter nogal vaag.

Daarom dat er dingen als NP-hardness zijn uitgevonden

TSP valt in deze klasse.

[Math-E-Mad-X]

Bestaat er ook een scherpe eenduidige omschrijving van het type oplossingen dat acceptabel gevonden wordt?

Wat je acceptabel noemt hangt natuurlijk helemaal van je toepassing af. voor sommige toepassingen zul je tevreden zijn met een afwijking van 20%, voor andere heb je maximaal 10% nodig, en soms wil je misschien alleen de absoluut kortste weg hebben.

[Bartjes]

In de (zuivere) wiskunde is het wel duidelijk wanneer je een probleem opgelost hebt, vandaar mijn vraag.


Het lijkt nu meer een technisch probleem. Zoiets als hoe maak je een zo zuinig mogelijke auto.

[Math-E-Mad-X]

De allerkortste weg vinden is inderdaad eenvoudig, gewoon alle mogelijkheden één voor één af gaan.


Wat echt spectaculair zou zijn, is als je de kortste weg kunt vinden met een algoritme waarvan de tijd polynomiaal toeneemt met het aantal steden (i.p.v. exponentieel). Men gaat er vanuit dat dit onmogelijk is, maar een bewijs daarvoor is nog nooit gegeven.

[Bartjes]

Wellicht is er een natuurkundig experiment te bedenken waarin de natuur zelf het probleem oplost.


Bijvoorbeeld door lichtstraaltjes op een slimme manier alle mogelijke wegen te laten uitproberen, en er dan voor te zorgen dat de snelste route "het wint". Maar hoe je zoiets precies moet opzetten weet ik niet.

[Xenion]

Wellicht is er een natuurkundig experiment te bedenken waarin de natuur zelf het probleem oplost.

Misschien dat er vanuit die hoek inderdaad interessante ideeën kunnen komen, maar zoals eerder gezegd is dit een NP-hard probleem. Dat betekent dat het als enorm moeilijk beschouwd wordt om de oplossing te vinden, maar het is even moeilijk om te controleren of een voorgestelde oplossing wel effectief de juiste is. Je moet immers de oplossing kennen ter vergelijking.


Dit probleem is al vrij oud en heeft al erg veel aandacht gekregen, het is allesbehalve triviaal.

[Bartjes]

Misschien dat er vanuit die hoek inderdaad interessante ideeën kunnen komen, maar zoals eerder gezegd is dit een NP-hard probleem. Dat betekent dat het als enorm moeilijk beschouwd wordt om de oplossing te vinden, maar het is even moeilijk om te controleren of een voorgestelde oplossing wel effectief de juiste is. Je moet immers de oplossing kennen ter vergelijking.


Dit probleem is al vrij oud en heeft al erg veel aandacht gekregen, het is allesbehalve triviaal.

Vroeger op school hadden we ook een analoge computer. Daarop kon je (differentiaal)vergelijkingen instellen, en het apparaat gaf dan een plaatje van de oplossing. Of de betreffende vergelijking analytisch gesproken makkelijk, moeilijk of onoplosbaar was, maakte niets uit.


Zo stel ik mij ook voor dat de oplossing van het handelsreizigerprobleem zonder haperen uit een proefopstelling moet rollen, zodra we er in slagen een situatie te bedenken waarin de natuur noodzakelijkerwijs het handersreizigerprobleem moet oplossen om te weten wat haar te doen staat.