Springen naar inhoud

- - - - -

Blob lost handelsreizigerprobleem op


  • Log in om te kunnen reageren

#1

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 10 april 2013 - 13:13

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

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

Publicatie: http://arxiv.org/abs/1303.4969
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Michel Uphoff

    Michel Uphoff


  • >5k berichten
  • 5384 berichten
  • Moderator

Geplaatst op 10 april 2013 - 14:34

Image1.jpg

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?
Motus inter corpora relativus tantum est.

#3

317070

    317070


  • >5k berichten
  • 5567 berichten
  • Moderator

Geplaatst op 10 april 2013 - 21:28

Het ziet er meer uit als Kruskal, en Kruskal is erg eenvoudig.
What it all comes down to, is that I haven't got it all figured out just yet
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-

#4

Kwintendr

    Kwintendr


  • >250 berichten
  • 768 berichten
  • VIP

Geplaatst op 11 april 2013 - 09:21

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?

Veranderd door Kwintendr, 11 april 2013 - 09:22

Het Wetenschapsforum heeft ook een facebook pagina!

#5

Michel Uphoff

    Michel Uphoff


  • >5k berichten
  • 5384 berichten
  • Moderator

Geplaatst op 11 april 2013 - 13:33

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.
Motus inter corpora relativus tantum est.

#6

317070

    317070


  • >5k berichten
  • 5567 berichten
  • Moderator

Geplaatst op 11 april 2013 - 14:22

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.
What it all comes down to, is that I haven't got it all figured out just yet
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-

#7

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 11 april 2013 - 14:33

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 :P
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

#8

*_gast_Bartjes_*

  • Gast

Geplaatst op 11 april 2013 - 15:26

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.

#9

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 11 april 2013 - 16:28

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

Daarom dat er dingen als NP-hardness zijn uitgevonden ;)
TSP valt in deze klasse.

#10

Math-E-Mad-X

    Math-E-Mad-X


  • >1k berichten
  • 2383 berichten
  • Ervaren gebruiker

Geplaatst op 11 april 2013 - 16:37

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.
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }

#11

*_gast_Bartjes_*

  • Gast

Geplaatst op 11 april 2013 - 17:04

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.

Veranderd door Bartjes, 11 april 2013 - 17:06


#12

Math-E-Mad-X

    Math-E-Mad-X


  • >1k berichten
  • 2383 berichten
  • Ervaren gebruiker

Geplaatst op 11 april 2013 - 19:37

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.
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }

#13

*_gast_Bartjes_*

  • Gast

Geplaatst op 11 april 2013 - 20:42

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.

#14

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 11 april 2013 - 21:24

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.

#15

*_gast_Bartjes_*

  • Gast

Geplaatst op 11 april 2013 - 22:24

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.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures