Pubcrawl: Forskere beregner korteste vej mellem 24.727 britiske værtshuse

Matematikproblemet 'Den omrejsende handelsmand' er stadig en stor beregningsmæssig udfordring. Efter to års arbejde har britiske forskere løst den hidtil største udgave for veje på et kort.

Der er ét eller andet med øl og dataloger. I hvert fald var det noget af en pubcrawl, fire forskere for to år siden satte sig for at finde den optimale løsning på, da de ville finde den korteste vej mellem 24.727 pubber i Storbritannien, skriver BigThink.

Forskerne, som blandt andet tæller lektor Keld Helsgaun fra Roskilde Universitet, satte sig for at prøve at løse den hidtil største udgave af Travelling Salesman-problemet for et problem baseret på et kort.

Travelling Salesman er et kombinatorisk matematisk problem, som er eksemplificeret ved den omrejsende handelsmand, der skal besøge et antal byer. Målet er at finde den korteste vej mellem alle byerne, men med den betingelse, at man kun besøger hver enkelt by én gang.

Den særlige udfordring er, at det for en vilkårlig udgave af problemet er vanskeligt at bevise, at en bestemt rute er den korteste, uden at prøve alle muligheder.

Der findes et antal algoritmer, der hurtigt kan finde en god kandidat til den optimale løsning, men man skal altså prøve et meget større antal mulige kombinationer, før man kan bekræfte, at løsningen er den bedste.

For den store britiske pubcrawl, der spænder fra Shetlandsøerne i nord til Cornwall i syd, er den optimale korteste rute på 45.495.239 meter baseret på afstande hentet fra Google Maps. Kortet kan ses i sin helhed på projektets hjemmeside.

Forskerne har efterfølgende løst et problem med dobbelt så mange punkter, hvor de har forbundet 49.603 historiske steder i USA med en rute på 350.201.525 meter - eller lidt mindre end gennemsnitsafstanden fra Jorden til Månen.

Pubcrawlen krævede ifølge forskerne udregninger svarende til 305 dage på en enkelt processorkerne. Tilsvarende krævede den amerikanske turistrute udregninger svarende til 178,9 år, men blev udregnet på University of Waterloos klyngecomputer med 310 processorkerner over en periode på otte måneder.

Tips og korrekturforslag til denne historie sendes til tip@version2.dk
Kommentarer (2)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
#2 Jens Krabbe

... i gennemsnit. Er det nok til at gå rusen ud, hvis man kun drikker tynde øl?

Det tager vel 15 minutter at bunde en pint, og 25 minutter at gå den gennemsnitlige afstand mellem pubberne, så 40 minutter per pint.

Med 8 timers søvn har man 16 timer til at gå og drikke i. Det giver 24 pints på en dag i gennemsnit - i London væsentlig flere og Wales en del færre.

Men 1030 dage senere kan med sætte kryds på sin bucket list ud for punktet med at besøge alle pubber i det britiske kongerige.

Cheers!

  • 3
  • 0
Log ind eller Opret konto for at kommentere