Trafikanten.no, hvordan er deres side laget?

[salah]

Trafikanten.no er et av de sidene jeg ofte besøker før jeg farter ut på tur, og hver eneste gang er jeg like fascinert over det systemet de har, og alt for mye av turen går jo til å tenke over hvordan de har greid å lage dette systemet.

 

For eksempel, de har jo sikkert alle buss/tog/trikk/t-bane-stopper innlagt på en database. Det er jo helt greit i seg selv, men for eksempel, la oss si jeg skal fra Oslo S til Lillehammer. Hvordan greier da dette systemet å finne ut at dette toget ikke går lengre enn til X stasjon og at jeg må bytte til X (hvor X er f. eks. buss eller en annen tog)?

 

Og hvordan er tidsberegningen? For eksempel klarer jo systemet deres å finne ut ca. antall minutter hele turen tar meg fra, hvordan har de målt det?

 

Hadde vært utrolig bra med lenker til noen artikler, dokumentasjon, forklaringer her, eller eksempler.

[nets]

Tipper de kobler opp alle databasene til alle de største kolektivtransportselskapene og har avanserte script og aplikasjoner som får alt dette til å sammarbeide i et gigantisk system med oppdateringer og ruteendringer og gud vet ikke hva de må ha inkludert i databasene. Ganske imponerende egentlig

[BrorBsd]

Trafikanten.no og liknende vei / tid kalkulerende systemer er utrolig fascinerende! Mener å tro at de inneholder en del heftige algoritmer for å kalkulere raskeste rute, dette uten å måtte beregne alle tenkelige kombinasjoner (du reiser ikke om drammen når du skal fra Oslo til Lillehammer).

 

Selve posisjonerings algoritme for et tog burde være ganske greit, Oslo S, +20 Bærum, +30 Asker. Hvordan datastrukturen på slike systemer er, tør jeg ikke gjette på. Tøft er det nå uansett

[Manfred]

Datastrukturen er garantert basert på grafer. En type "avanserte trær".

[roac]

Datastrukturen er garantert basert på grafer. En type "avanserte trær".

9499453[/snapback]

Kan bare stille meg bak dette. Og som "alltid" så er dette noe som ikke akkurat er lett håndterlig, og tidvis gir interessante resultater, som f eks forslag om å dra via Gardermoen når du skal mellom to steder i Oslo

[Manfred]

Hehe. Grafer er absolutt ikke enkelt, men pokker så fascinerende. Det som er mest fascinerende er egentlig hvor lite kode som skal til for å gjøre mye jobb, så lenge det er god gjennomtenkt

[BrorBsd]

Hehe. Grafer er absolutt ikke enkelt, men pokker så fascinerende. Det som er mest fascinerende er egentlig hvor lite kode som skal til for å gjøre mye jobb, så lenge det er god gjennomtenkt

9511037[/snapback]

Har gått og grubla litt siden sist

 

Hva er det du egentlig legger i grafer?

 

Ser for meg et system der en registrere punkter (stasjoner) og legger opp bussruter, gåruter, trikkeruter osv. mellom punktene. Dermed kan en "tegne sammenhengene streker" mellom avreise og ankomst punkt.

 

I mitt hode ser en veldig forenklet struktur slik ut:

Stasjon (StasjonsID, Navn)

Rute (RuteID, Navn, ReiseType)

RuteStep (RuteID, FraStasjonsID, TilStasjonsID, RuteSteg, TidBruk, DivDetaljer+++)

 

En kan selvfølgelig kalkulere opp alle avstander i ruta; eks: StasjonB->StasjonE = 12 minutter og en differanse fra starttidspunktet.

 

Har aldri beveget meg inn rekursiv funksjonalitet i sql, er det noen annen måte og angripe dette på?

 

Min logikk skriker rekursjon, er det noen annen mer fornuftig måte å løse dette på? Er dette en oppgave som en kan eller bør bruke en database til?

[roac]

Du begynner å nærme deg. Det er bare "en million hindre i veien her". Gitt f eks at du skal fra Tøyen til Jernbanetorget. Det går både tog (hvis ikke stasjonen er lagt ned), t-bane og buss. Og som om ikke det er nok, det går ikke mindre enn seks t-banelinker. Du vet ikke ut i fra utganspunktet hvilke linjer som ender opp der du skal. Og som om ikke det er nok, hvordan håndterer du bytte? Tenk deg at du skal fra Grünerløkka til Smestad. Du har en rekke muligheter. Du kan ta trikk eller buss ned til sentrum. Bare her har du mange valg. Du kan gå av på Gunerius, Jernbanetorget eller Stortovet for å nevne noen. Alle stedene går det en rekke transportmidler videre, for ikke å snakke om at du ved Gunerius er i gangavstand (enda et "transportmiddel" til bussterminalen). Du har i det hele tatt et nettverk av muligheter til å bevege deg fra en holdeplass til en annen, og grafene representerer alle disse mulightene. Problemet er å lage en god nok algoritme for å sette sammen disse bruddstykkene på en så god måte som mulig, slik at du som bruker av trafikanten får opp den enkleste ruten. Det er svært fasinerende

 

Edit: For mer informasjon om dette i SQL anbefales Joe Celko's Trees and Hierarchies in SQL for Smarties på det varmeste.

Endret 17. september 2007 av roac

[BrorBsd]

Roac takker for svaret, legger boken til i lista over bøker som jeg har lyst til å lese Har en hel del ting jeg kunne tenke meg å bruke denne slags funksjonalitet til.

[Manfred]

Det er en type emne som tar ltit tid å komme inn i, men når du har fått en sprekk i skallet så vil jeg tro du får en "aha-opplevelse" Lykke til.

[ashore]

På nettsiden nedenfor finner du forelesningsnotater til kurset "INF2220 - Algoritmer og datastrukturer" på UiO.

 

http://www.uio.no/studier/emner/matnat/ifi...isningsplan.xml

 

Der kan du finne grunnleggende innføring i grafer (og trær).

[BrorBsd]

På nettsiden nedenfor finner du forelesningsnotater til kurset "INF2220 - Algoritmer og datastrukturer" på UiO.

 

http://www.uio.no/studier/emner/matnat/ifi...isningsplan.xml

 

Der kan du finne grunnleggende innføring i grafer (og trær).

9641464[/snapback]

 

Takker for link, dette skal leses

[roac]

I den sammenheng kan det nevnes at læreboka er (eller i hvert fall var) Algorithms and Data Structures ... av Mark Allan Weiss. Boken finnes i flere utgaver, for forskjellige programmeringsspråk. Ved UiO er/var det Java-utgaven som ble benyttet.