Spelar det verkligen någon roll var tomten bor?

Sambon och jag diskuterade DN:s artikel om var tomten bor – optimalt sett i Kirgizistan, för att bäst hinna till alla barn, enligt Sweco som har räknat. Uträkningen lär ha tagit en halv dag, och utgått från att tomten gör en enda resa med alla julklappar i släden från början, under 24 timmar.

“Swecos uträkning har gjorts genom en analys av var världens barn bor, jordens rotation och demografiska data. Utifrån vissa förenklingar har Kirgizistan blivit den mittpunkt varifrån tomten enklast undviker onödiga transportsträckor.”

Första reflektionen: spelar det verkligen någon större roll var tomten börjar, om han ändå måste besöka alla jordens barn under samma resa? Den sammanlagda resvägen mellan 2,5 miljarder hem måste ju vara väldigt mycket längre än avståndet mellan Rovaniemi och Kirgizistans bergsmassiv (grovt höftat 5000 km) – kan inte tomten nästan lika gärna åka från Rovaniemi till Kirgizistan det första han gör? Fördelar man 5000 km på 2,5 miljarder stopp blir det 2 millimeter per besök; det borde gå på inbromsningsmarginalen. Om tomten dessutom färdas med en hastighet av 5800 km i sekunden (som angett) tar det ju bara drygt en sekund att ta sig mellan Rovaniemi och Kirgizistan.

Andra reflektionen: vänta nu, det här borde vara ett gigantiskt “den handelsresandes problem“. Ska man lösa det exakt tar det lång tid; någonstans kring O(2^(k*n)) tid, det vill säga, tid proportionerligt mot 2^miljard som är ett väääldigt stort tal*. Undrar hur de har approximerat**, på Sweco? Det måste nog till ganska många förenklingar för att få ner problemet till hanterbar storlek (jag gissar på något slags densitetsanalys. Det är nu ytterligare fortsättningskurser i algoritmer och optimering skulle ha kunnat komma till nytta.)

Tredje reflektionen: “Antalet hem betyder att tomten i snitt har 34 mikrosekunder att parkera släden, ho-hoa sig ned genom skorstenen, dela ut klapparna, äta en skvätt gröt och ta sig tillbaka till renarna.” Mm, ja, om han sedan teleporterar sig omedelbart från en plats till nästa. 34 mikrosekunder borde vara med transporttiden inräknat (och ska man vara riktigt jäkla petig ska det dessutom avrundas till 35 mikrosekunder om antalet hem är precis 2,5 miljarder).

Fjärde reflektionen: Borde jag inte ägna min tanketid åt något viktigare än det här? Det är ju uppenbarligen ett orimligt problem…

Andra bloggar om: , , , , ,

UPPDATERAT 1/1 2008, kl 11:13: En hjälpsam kollega som verkligen forskar inom detta generella område skickade en lång mailkommentar full med nyttigheter. Så nu har jag fixat till texten lite; under “andra reflektionen”. Fotnötterna är nya.

*Ska tilläggas här att vi inte vet att NP-fullständiga problem inte kan lösas på polynomiell tid. O(2^(k*n)) är en gissning, för någon positiv konstant k <= 1. Men jag har fått hjälp med den, så den är i alla fall en kvalificerad gissning.

** “om vi nöjer oss med att få en tur som är högst, säg, 0,1 % från den optimala så är TSP inte svårt att lösa alls. Dvs. TSP är lätt för alla praktiska ändamål.” säger min hjälpsamma kollega som har läst igenom den här bloggposten.