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
Laatste berichten
-
00:49
Ervaringen met "herontdekkingen" 11
-
00:37
Rotatie van het heelal 24
-
21:28
hall effect in vloeistof gebruiken als stromingssensor 6
-
17:59
Gezocht: de/een naam voor een getallenrij met een cauchyrij als partieelsommenrij
-
17:28
Casus uit de praktijk: positief test THC 18
-
17 apr
speciale rel. theorie 4
-
17 apr
Vreemde stank in huis 11
-
17 apr
3 vragen over mijn rooskleurige r.berekening H2netGekoppeldeHBrflowbatterij.
-
17 apr
Interpretatie reactie-energie 3
-
17 apr
Logistic equation (Pierre Verhulst,Belgian Mathematician) 5
-
16 apr
vB 9
-
15 apr
Kunnen quantum Zonnecellen 190% quantum efficiënt zijn 1
-
15 apr
Python: sockets sluiten 4
-
14 apr
Een eenvoudige logische redenering waarom tijd niet kan bestaan 'daarbuiten' 6
-
14 apr
Hoe kun je op quantumwijze getallen vinden in een rij die kleiner zijn dan getal k 3
-
13 apr
Documentenverdwijnen uit onedrive 1
-
12 apr
Behoud van impulsmoment en energie 5
-
12 apr
INLOG STORING / TIPS 4
-
09 apr
[natuurkunde] systeemgrafen 1
-
05 apr
afbuiging licht rond zware objecten via grondbeginselen relativiteitstheorie 490
Nieuwsberichten
-
04 mar
Een nieuw soort magnetisme: altermagnetisme
-
31 okt
AI kan via stem diabetes vaststellen 11
-
21 okt
Einstein krijgt wéér gelijk 45
-
07 feb
witter dan wit 20
-
19 jun
irrigatie en de aardas
Blob lost handelsreizigerprobleem op
Moderator: Astro
-
- Berichten: 10.179
Blob lost handelsreizigerprobleem op
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
-
- Moderator
- Berichten: 8.166
Re: Blob lost handelsreizigerprobleem op
- Image1.jpg (143.78 KiB) 1409 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?
-
- Berichten: 5.609
Re: Blob lost handelsreizigerprobleem op
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-
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-
-
- Berichten: 768
Re: Blob lost handelsreizigerprobleem op
Michel Uphoff schreef: ↑wo 10 apr 2013, 15:34
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.
Michel Uphoff schreef: ↑wo 10 apr 2013, 15:34
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?
Het Wetenschapsforum heeft ook een facebook pagina!
-
- Moderator
- Berichten: 8.166
Re: Blob lost handelsreizigerprobleem op
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.
Vind het niet indrukwekkend, maar misschien zie ik iets over het hoofd.
-
- Berichten: 5.609
Re: Blob lost handelsreizigerprobleem op
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.
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-
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-
-
- Berichten: 10.179
Re: Blob lost handelsreizigerprobleem op
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
. Jammer eerlijk gezegd.Edit: wat 317070 zegt dus
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
Re: Blob lost handelsreizigerprobleem op
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.
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.
-
- Berichten: 2.609
-
- Berichten: 2.906
Re: Blob lost handelsreizigerprobleem op
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 schreef: ↑do 11 apr 2013, 16:26
Bestaat er ook een scherpe eenduidige omschrijving van het type oplossingen dat acceptabel gevonden wordt?
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }
Re: Blob lost handelsreizigerprobleem op
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.
Het lijkt nu meer een technisch probleem. Zoiets als hoe maak je een zo zuinig mogelijke auto.
-
- Berichten: 2.906
Re: Blob lost handelsreizigerprobleem op
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.
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(); }
Re: Blob lost handelsreizigerprobleem op
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.
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.
-
- Berichten: 2.609
Re: Blob lost handelsreizigerprobleem op
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.Bartjes schreef: ↑do 11 apr 2013, 21:42
Wellicht is er een natuurkundig experiment te bedenken waarin de natuur zelf het probleem oplost.
Dit probleem is al vrij oud en heeft al erg veel aandacht gekregen, het is allesbehalve triviaal.
Re: Blob lost handelsreizigerprobleem op
Xenion schreef: ↑do 11 apr 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.
