Most recent comments
Liveblogg nyttårsaften 2017
Tor, 11 months, 2 weeks
Jogging og blogging
Are, 1 year, 11 months
Liveblogg nyttårsaften 2016
Are, 1 year, 11 months
Reading in dark times
Are, 2 years
Moldejazz 2016
Camilla, 2 years, 4 months
Dørskilt
Karoline, 2 years, 5 months
Halifax
Tor, 2 years, 5 months
Sony Smartwatch 3 review
Tor, 2 years, 6 months
Numerikk, takk
Tor, 2 years, 6 months
Topp tur
Camilla, 2 years, 8 months
50 book challenge
Camilla, 11 months, 2 weeks
Five years ago
Endelig \(\LaTeX\)-støtte
Tor
Controls
Register

Den handelsreisendes problem

Tenk deg at du er en handelsreisende, og at du bor i for eksempel Oslo. Du har en liste med byer du skal besøke, hvorpå du skal returnere til Oslo. Du lever i tiden og forventer effektivitet, og ønsker derfor å finne den korteste ruten som tar deg innom alle byene og tilbake til utgangspunktet. Den enkleste tilnærmingen til dette problemet er naturligvis å lage en liste over alle mulige reiseruter, og deretter regne ut hvor lange de er, og finne den som er kortest. Problemet med denne fremgangsmåten er at med N byer finnes den N! ulike ruter, og dette blir ganske raskt en uhåndterlig størrelse.

For noen år siden ble dette problemet gitt til eksamen i Numerisk fysikk, der det var 15 byer som skulle besøkes. Det var med andre ord 1307674368000 mulige ruter, og bare det å generere listen over de ulike reiserutene med en vanlig datamaskin ville antagelig ta lengre enn hele eksamenstiden. Hvis man ser på problemet med 80 byer begynner antall mulige reiseruter å bli omtrent på størrelse med antall protoner i universet, og det blir raskt værre. Like fullt er det noen som har greid å løse dette problemet med 89500 byer. Det er åpenbart at her må man ty til sleipe triks.

Jeg brukte et par timer på dette problemet for noen dager siden, og jeg skrev et program som finner en tilnærmet løsning for et par tusen byer på bare noen få minutter. Jeg gikk frem som følger:

Først lager programmet en tilfeldig reiserute. Så ser det på to tilfeldige etterfølgende byer på ruten, og bytter rekkefølgen på dem. Hvis dette førte til at ruten ble kortere beholder vi den nye rekkefølgen, hvis ikke bytter vi tilbake. Så gjør man dette ca ti ganger så mange ganger som det er byer, og da begynner det å bli ganske bra. Figuren viser den totale lengden etter hvert skritt i programmet:



Som vi ser later det til at vi nærmer oss en løsning, men med en sleip juksemetode som dette kan man aldri være sikker på når man har den riktige løsningen. Det finnes imidlertid enda sleipere triks, som finner nøyaktige løsninger på rimelig tid. De har jeg imidlertid ikke satt meg inn i, men spesielt interesserte kan lese mer på wikipedia.

-Tor Nordam

Comments

Camilla,  18.03.08 00:29

Det er fint å se at dere fysikere vet hvordan man utnytter potensialet i utropstegn.

Anders K.,  18.03.08 10:47

"N!" ser ut som et skjellsord fra Kalahari.

Torgar,  18.03.08 11:08

Det hadde vært morsomt å testa hvor god en genetisk algoritme ville vært på problemet.

N! - We are the knights who say: factorial of N

Are,  18.03.08 15:51

Du skrev alt det, og så konkluderte du ikke med hvorvidt algoritmen din var log(n), n log(n) eller whatnot? ;)

"Traveling salesman" er forøvrig (ikke overraskende) en gjenganger i algoritmer og datastrukturer i informatikkutdanningen. Algoritmer er forøvrig blant mine svakere fag :) Men jeg synes Lene og/eller Anders bør bidra med en kommentar her.

Kjellove,  18.03.08 15:56

!!!

Hanna Maja,  18.03.08 17:47

Påpeking av skrivefeil er:
a) konstruktiv tilbakemelding, da det tross alt publiseres på verdensveven
eller
b) irriterende, pirkete og sjelden relevant

?

Tor,  18.03.08 19:04

Kommer an på hvilken type skrivefeil. Hvis du vil påpeke at jeg på et punkt skrev «den» i stedet for «det», så er det bare irriterende, for det er bare en skrivefeil. Hvis du vil kommentere at jeg skriver «værre» med æ, er det forsåvidt greit nok, men antagelig håpløst. Hvis du vil si at jeg bruker for få eller for mange komma, kan du alltids gjøre det, men la meg bare nevne med en gang at jeg ikke tror på kommaregler.

Hvis det var en annen feil kan du gjerne påpeke den, ettersom jeg ikke greide å finne den selv.

Og på norsk bruker vi stor bokstav etter kolon.

Jørgen,  18.03.08 19:40

Vi begynner heller ikke setninger med «og». I det muntlig språket gjør man det gjerne, men helst ikke skriftlig. Ei heller er det nødvendig å bryte inn et komma foran et «og». Du tror ikke på kommaregler? Det er vel og bra, men det skulle ha tatt seg ut om alle begynte å bruke komma i stedet for punktum hele tiden. Hver gang du får en trang i magen og har lyst til å skrive både et komma og et «og» kan du spørre deg selv om det ikke kan stå et punktum der i stedet. Om svaret er nei så kan du bare drite i det kommategnet. Disse kommentarene er myntet på elitisten i deg, Tor. Ikke bli lei deg.

Siden jeg er så godt i gang med å raljere kan jeg påpeke at det er dårlig stil å begynne så godt som samtlige setninger med ordet «hvis». Det finnes en rekke gode alternativ, slik som «dersom» og «om». Prøv å variere litt, så skal du merke at du straks føler deg mye bedre.

Kristian,  18.03.08 20:46

Her heiser jeg vimplen, og støtter deg Tor. |>

> Break all rules!

,er et viktig prinsipp.

Når Tor leser så masse som han gjør, og er en så veltrent skribent som han her, da gjelder ikke lengre reglene man lærte på skolen. Man bør være bevisst på hvordan man kommuniserer, men poenget er kun det. Kommunkasjon.

Er det kun Dabladet sine journalister som skal bidra til å utvikle spårket videre? Eller bør sånne som Tor bidra?

Nå er jeg sikkert mye mer radikal enn det Tor mente å være, men det er morsommere.

Jørgen,  18.03.08 22:53

Å bryte reglene er en fin ting. Det kan være særs morsomt og spennende, men det forutsetter at man kan reglene og at bruddene er tilstrekkelig interessante, tror jeg. Som et eksempel kan jeg nevne boken Gudenes fall av Cornelius Jakhelln. Den er proppfull av Ravi-norsk. Med det mener jeg at ord er skrevet slik de uttales i stedet for å bruke ordinær skrivemåte. Det er en anstrengende prøvelse, men boken er godt skrevet og til tider ustyrtelig morsom. Et godt eksempel på at regelbrudd kan være en bra ting.

En annen, litt eldre forfatter som bryter reglene er Tor Åge Bringsværd. Les for eksempel hans bok Den som har begge beina på jorda står stille fra 1974. Om du ikke orker å lese hele foreslår jeg at du gjør følgende: Snik deg inn på et bibliotek. Finn frem til boken. Bla frem til 10. kapitel (ja, med én t). Sett deg ned på gulvet og les frem til side 106. Etter det kan du gå i skranken og låne boken, kjøpe deg en brus eller en kopp kaffe, sette deg på et busstopp og lese mens du venter på bussen. Hvor bussen går er ikke så viktig, bare du leser.

Kristian,  18.03.08 22:52

Takk for referansene.

Men du, jeg mener ikke bare for å være spennende. Jeg mener for å ikke miste språkets evne til å endre seg. De små feilene er de som endrer spraaget. Og når språkrådet innser at veldig mange skriver på en annen måte enn det man lærer på skolen, da må de endre reglene.

Altså: Dette med å begynne setninger med Og er nettopp et sånn eksempel. Det er ikke lov, men noen ganger er det rett. (Forresten er det kanskje lov, men det er ikke saken)

Jørgen,  18.03.08 23:14

Språk endre sg liten tvil. Jei bgnnr setnngr m «og» utn bry mg. skrv no for d føls natrlg r 1 tng, fel på trass no ant. Jei fullt klar ovr a du ikk mnt å utfordr skrvereglne kun for d e spennde, men jei tror ikk d komr no revolusjn m d 1st. Ikk 1 høilytt å ikk 1 stille.

Kristian,  18.03.08 23:20

Greit nok, J-man.

Da er vi ganske enige da.

Bortsett fra at dette med 1st ikke er et gyldig argument for gode samfunnsborgere. For da er det heller ingen vits å stemme eller å ta bussen istedenfor å kjøre bil i tilfeller hvor det sistnevnte er mest praktisk.

Jørgen,  18.03.08 23:33

det er jeg vel enig i, egentlig. om jeg skal stille meg på din side, så har jeg lyst til å argumentere mot tors oppfordring om å ha stor forbokstav etter kolon. hvorfor skal vi i det hele tatt bruke stor forbokstav? det er ingen grunn til å gjøre forskjell på bokstavene. det gir ikke mindre eller en annen mening om jeg skriver kristian fremfor å skrive Kristian, som et eksempel.

Kristian,  19.03.08 08:35

Her har jeg ingen sterke meninber. bortsett fra at små bokstaver er mye mer behagelig å lese, synes jeg.

Jørgen,  19.03.08 11:22

Det er også fremmet en hypotese om at det er raskere å lese "lowe case letter" fremfor " capital letter". Flere tester har så langt gitt forskerne medhold i antagelsen. Så det er nok ikke rart at du finner det mer behagelig å lese små bokstaver.

Tor,  19.03.08 11:24

Oioioi.

Jeg vet at man ikke ska begynne setninger med og, men av og til synes jeg det passer. Og (hehe) jeg vet at jeg bruker en del ord litt for mye, så det tar jeg gjerne i mot tyn for. For eksempel begynner jeg veldig ofte avsnitt med en eller annen konstruksjon som inneholder forøvrig eller imidlertid, og det blir det ikke så bra språk av.

Jeg tror forresten Ravi-norsk er grunnen til at jeg ikke har lest Gudenes fall ennå, så man kan jo diskutere om det er en bra ting eller ikke. Hadde boken vært dårligere om den hadde vært skrevet på en mer standard målform?

Når det gjelder store bokstaver mener jeg ikke noe spesielt, den enesten grunnen til at jeg påpekte det var for å være pirkete når skrivefeil først var temaet.

Kjellove,  19.03.08 13:03

Stor bokstav etter kolon kommer an på hvorvidt en fullstendig setning følger.

«Forøvrig» er for øvrig riksmål.

Jørgen,  19.03.08 13:31

Sammenskrevet form er vel som regel riksmål. Eksempel er «istedet», «ifra», «imellom», «forøvrig», «avgårde», «igår», «ikveld» og «endel».

Når det gjelder Gudenes fall så tror jeg bestemt den hadde vært mindre morsom og på langt nær så interessant om den var skrevet på standardisert bokmål.
Christer,  21.03.08 09:31

Les dagens xkcd-stripe for mer moro med "den handelsreisendes problem". Lurer på om Randall Munroe leser Calcuttagutta for å få inspirasjon?

Ellers vil jeg gjerne si at rettskriving er en fin ting, og at grove feil bør påpekes. Det er behagelig å lese diskusjonene på Calcuttagutta, både på grunn av godt innhold og på grunn av god innpakning (les: språk). Dersom jeg skulle forville meg inn på en "debatt" på sidene til Dagbladet (eller VG, Adresseavisa, Aftenposten) svir det i øynene av og/å-feil, sms-språk og direkte dårlig norsk, så det er godt å ha en motvekt til dette. Jeg er en stor tilhenger av store bokstaver der disse hører hjemme - også når man skriver tekstmeldinger eller prater på nettet. Det er imidlertid ikke alltid at man skal ha stor bokstav etter kolon, f.eks. ved oppramsing. Se forøvrig denne siden.

Selv om jeg i de fleste tilfeller ønsker å lese korrekt språk så er det selvsagt ikke noe i veien for at folk tøyer reglene (eller bryter dem) for å få fram et poeng eller bruke det som et virkemiddel. (Jeg liker for eksempel bøkene til Harald Rosenløw Eeg, med tidvis radikal østlandsnorsk.) Problemet er når folk konsekvent skriver feil av gammel vane, uten noe poeng bak det. Da sklir språket ut. Det samme finner vi delvis i muntlig språk: Det er lenge siden jeg har lagt merke til noen som har korrekt bruk av da/når i dagligtalen. Alt er "når" i dagens muntlige norsk.

Forøvrig håper jeg at alle har en utmerket påske, hvor enn i Norge eller verden dere befinner dere! Selv er jeg i Trondheim, og det er ikke så ille som man skulle tro.

Camilla,  21.03.08 12:36

Jeg blir litt redd og bekymret når det er fysikerne og medieviterne som diskuterer språk og rettskriving.
Jeg føler i grunnen at det burde være mitt område. Eller at Silje og Lena burde kommentere. Men altså.
Jeg har hatt denne diskusjonen en del ganger på engelsk og jeg vil påpeke at Tim, som er lingvist, sier at å insistere på at man ikke skal begynne setninger med "og" (eller andre ord på engelsk, selvsagt, men prinsippet blir det samme) er bare tull og tøys.
Nå er imidlertid ikke han så fryktelig bekymret for at "kj"-lyden er på vei ut, heller, så han er tydelig dekadent. (Men det hadde vært fint om han kunne kaste inn to cent... pence?)

Vegard,  21.03.08 12:37

Jørgen,  21.03.08 17:17

Interessant å se at et så kjedelig tema som "ikke "og" i starten av en setning" er det som får størst oppmerksomhet.

Kjellove,  21.03.08 18:20

This is the sort of bloody nonsense which up with I will not put.

Skybert,  22.03.08 03:55

Måtte være en neger fra Sunnmøre, da.

Kjellove,  22.03.08 11:10

La meg sitere Språkrådet:

Etter kolon har vi liten forbokstav i enkeltord og uttrykk.

Etter kolon har vi liten forbokstav i leddsetning (bisetning, undersetning).

Når vi har ei heilsetning (hovudsetning) etter kolon, bruker vi stor forbokstav.


Men:
Sitat skal vere nøyaktige. Etter kolon kan vi difor få både stor og liten forbokstav.

Disse reglene SKAL følges, og man skal ALDRI avvike fra dem! Er det forstått, for faen?

Vart det bra no?

B,  22.03.08 13:43

Hadde jeg orket skulle jeg nevnt Prim, Markov og muligens Dijkstra.
Men det blir for pretensiøst å "name droppe" computer scientists så jeg lar være.

Tor,  22.03.08 14:09

Det minner meg om den gangen Donald Knuth og jeg var på fisketur.

B,  22.03.08 14:32

For ikke å snakke om den gangen jeg og Edsker Dijkestra tok oppvasken og filosoferte over det faktum at; selv om alle koppene er skittene og ligger i skittent vann blir hver enkelt kopp ren hvis vi skrubber de etter tur og skyller de.
Dermed kan vi overføre det på problemet med å sortere ut nodene med minst vekt til vi sitter med en rute fra start til mål.
Omtrent slik...

Jørgen,  22.03.08 14:54

For ikke å snakke om den gangen jeg trippelpostet en hel masse vås.

B,  23.03.08 01:28

i helvete!!!!!
Opera og mac er ganske mongo!
Håper noen med tilgang kan ordne opp...

[Det er ordnet. M.v.h. admin.]

Jørgen,  22.03.08 18:21

Håper noen med tilgang kan gi Bjørn Inge en medalje...

Kjellove,  22.03.08 18:36

En pappmedalje påført med tusj: «Fin innsats på idrettsdagen!»

Jørgen,  23.03.08 10:59

Nei, nei, nei. Dette ødelegger jo sammenhengen. Jaja...

Are,  23.03.08 12:22

Jeg vet. Det er en bug - eller en slags feature - men det bør i alle fall ryddes opp i. (Kommentarer timestampes på nytt når de redigeres, her burde originaltiden vært beholdt, men kommentaren markert med tidspunkt for siste redigering.) Jeg kom på dette akkurat når jeg trykket "Lagre endringer". Og nå er jeg litt for lat til å logge meg inn og tukle med databasen direkte for å rydde opp i det. Dette for stå som et historiens monument over en av Calcuttaguttas bøgs.

Kjellove,  23.03.08 12:47

Hvem er det du kaller bøg?

Skybert,  23.03.08 15:00

Typisk mac.

Jørgen,  23.03.08 18:14

Ser ut som en mac du, Tangen.

Kjellove,  23.03.08 19:48

Ser mer ut som en O'.

Jørgen,  23.03.08 19:55

iTrond? Eller som den nye versjonen skal hete: iOnd.

Hanna Maja,  28.03.08 18:09

Eh, ja, hvis noen fremdeles lurer på det, var det ordet "værre" som utløste min kommentar. Ikke verre enn det, egentlig.

Skybert,  28.03.08 18:48

iOnd er jÆvlig fet!

Jørgen,  28.03.08 18:51

Bare synd han får virus hele tida.

Jørgen,  28.03.08 18:51

Og det med å få Tor til å skrive "verre" i stedet for "værre" er dødfødt. Jeg har prøvd lenge, uten hell.
Category
Technology
Tags
numerisk fysikk
programmering
Views
3555