Afstandsberegning

Først og fremmest skal du jo have vejdata for alle veje i hele landet! Det tvivler jeg på er gratis, men pyt. dernæst skal du have implementeret en søge algoritme at finde cheapest path (bemærk ikke shortest path, det er jo ikke ligegyldigt om du kører på grusveje eller motorvej). Her vil jeg anbefale Dijkstras algoritme eller en A* algoritme, du googler dem bare. Herefter skal du finde en fornuftig datastruktur til din graf (Vejnettet er grafen), da du ikke har uendelig meget hukommelse (i praksis bør din søge funktion ikke bruge mere ned 8-16 MB) og vejnettet er stort bliver du nød til at have grafen splittet i mindre dele, brug træer her. Og så burde du være i stand til at kode det

Da jeg kan se at du postet det under PHP, antager at du vil kode det i PHP, Jeg mener ikke at PHP er løsningen på det ovenstående, eksekveringstiden i forhold til f.eks. en C/C++ application er alt for lang. her kan du så evt. kode det i C/C++ eller lignende og så lave det som en CGI applikation, så kan PHP jo lege med outputtet bagefter.

God fornøjelse!

skulle det blive for stor en mundfuld kan du evt. bare lave det som opslag i post.nr. (det skal ikke bare være Post Danmark der har glæde af dem ) tabel f.eks:
| |a|b|
|a|1|6|
|b|6|1|

hvor anstanden/prisen for en flytning fra x->y kan slås op.

det er ihvertfald nemt at implementere, ikke helt nøjagtigt, men den procentlige nøjagtig bliver helt god jo større afstanden bliver.

håber du kan bruge noget af det
//Troels

Hej
Det må være muligt at anvende en af de sider der findes til at finde afstande imellem to punkter på et kort. Lovligheden må du selv finde udaf. TSP - problemmer er ikke så komplekse hvis man bruger tid på at løse dem inden for relativ små områder. Her kan anvendes mange gode metoder. f.eks. simpleks- metoden (som er så simpel at de fleste kan lære denne).

Der er noget der hedder GIS du måske kan bruge. f.eks.
http://www.u-gis.dk/
eller bare
http://www.google.dk/search?hl=da&q=GIS&btnG=Google-s%C3%B8gning&meta=cr%3DcountryDK

Hvis du vil bygge din egen tabel op med afstande tror jeg du får for meget at se til. Men ellers kan man låne nogle matrikel kort hos kommunien og lave dine tabler udfra disse lokalt og herefter forbinde alle knuderne og kommunerne.

Men brug GIS. Det virker, men koster lidt.

Med Venlig Hilsen
Janus S. Andersen

Det lyder meget besværligt det i skriver om, så jeg kom på en ny idé:
Er det muligt at tælle antallet af zoner (post-områder) man kommer igennem?
Eksempelvis fra a til g er der 5 zoner.

Tror også jeg skrev om TSP fordi han sagde at man skulle fra A til D gennem punkterne F, G og H. Men selvf. jeg skammer mig ikke Var bare lige pludselig lidt forvirret. Men din Zone løsning lyder som en væsentlig bedre idé. Den er vist også nemmere at implementere, men igen så kommer du til at skulle lave noget dynamisk programmering med en tabel som man så kan slå op i på O(1) tid. Det er meget hurtigt ;D Men lav en tabel over det hele som før nævnt. Det er et stort stykke arbejde, men det er her dynamisk programmering kommer ind i billedet, da du jo bare skal lave en problemløsning der kan inddeles i subproblemer og som man siger subsubproblemer, og du så derved løser det fx. rekursivt. Det er mit bud.
Start med at lave en test tabel, som implementere et reelt delproblem af det hele, og via den kan du så implementere en algoritme der løser dit problem. Du kan så senere, når du har fået det til at virke, udvide din tabel så den passer til hele Danmark.

Jeg har lagt samtlige postnumrer ind i en databse, dog har jeg lidt problemer med at komme videre.

Problemet er når jeg skal fra A - G skal jeg jo nok igennem B F og T, hvordan finder jeg disse "via"-zoner?

hvilket layout har du brugt på din tabel?

mit postnummer forslag kræver ingen søgning i den forstand, kun lidt forarbejde

jeg ville konstuere tabellen med en indekseret kolonne med start postnummer (src), og derefter en kolonne for hvert eneste postnummer (dst). Du kan således når du skal finde afstanden mellem A og G blot fyre kaldet "Select `G` from `tabel` where `src` = 'A'" og hive værdien ud. jeg mener ikke der er mere 1400 postnumre i Danmark, og afstanden kan fint ligge i en 16bit integer (jeg tvivler på at kommatal har så meget at sige i den her sammenhæng), og derved vil tabellen ikke fylde mere end ca. 4MB.

skal du have en "via" funktion summerer du blot afstande sammen, skal afstanden fra A til G over B beregnes kan beregnes ved at sige A til B + B til G.

//Troels

Vil lige prøve at kigge på det når jeg har tid i morgen... takker ellers...

PS der er 1643 postnumrer i Danmark...

Jeg skal for et flyttefirma lave en afstandsberegner der skal bruges til at beregne en pris for en flytning.

Det jeg skal have er en formular hvor man kan indtaste sin gamle adresse og sin nye adresse og få en afstand ud i km.

Jeg har bare ingen idé til hvordan jeg kommer igang med dette, så jeg håber i vil hjælpe.

Jeg har kigget på diverse sider (krak, degulesider og map24.com) uden at kunne få nogen som helst idé...

Jeg vælger helt at lade være med at svare på det her Da det i mine øjne vil blive en meget, meget stor tabel du kommer til at have. Ydermere vil jeg henlede opmærksomheden på TSP, http://en.wikipedia.org/wiki/Traveling_Salesman_Problem
(dog er dette problem, afstandsberegning, ikke helt det samme som TSP, for at sige meget forskelligt fra) Men jeg synes du skal læse lidt om dynamisk programmering, http://en.wikipedia.org/wiki/Dynamic_programming da det nok er her du skal finde en løsning på problemet, eller ihvertfald en del af det.
Jeg tager afstand fra min samligning med TSP, men jeg gør dig alligevel opmærksom på det, da det måske kan åbne dine øje for hvor svært det egentlig er at lave en afstandsberegning med mange permutationer, så det bliver effektivt, billigt og hurtigt.

Hej
Det må være muligt at anvende en af de sider der findes til at finde afstande imellem to punkter på et kort. Lovligheden må du selv finde udaf. TSP - problemmer er ikke så komplekse hvis man bruger tid på at løse dem inden for relativ små områder. Her kan anvendes mange gode metoder. f.eks. simpleks- metoden (som er så simpel at de fleste kan lære denne).

Der er noget der hedder GIS du måske kan bruge. f.eks.
http://www.u-gis.dk/
eller bare
http://www.google.dk/search?hl=da&q=GIS&btnG=Google-s%C3%B8gning&meta=cr%3DcountryDK

Hvis du vil bygge din egen tabel op med afstande tror jeg du får for meget at se til. Men ellers kan man låne nogle matrikel kort hos kommunien og lave dine tabler udfra disse lokalt og herefter forbinde alle knuderne og kommunerne.

Men brug GIS. Det virker, men koster lidt.

Med Venlig Hilsen
Janus S. Andersen

Nu mener jeg heller ikke at dette ligger indunder TSP FOr han skal jo ikke finde den korteste vej osv. Men jeg mener dog stadig at hans tabel vil blive meget stor. Men så igen. Hvad ved jeg. Har jo aldrig arbejdet med et sådant problem før andet end 10 punkter med afstande imellem. Det løste vi godt nok med en sådan tabel. Meget handy.

Martin: Du behøves ikke skamme dig over din analogi til TSP, det er meget aktuelt hvis der skal mere end et via punkt med, i så fald er den eneste forskel at han ikke skal slutte hvor han kom fra. dynamisk programmering er en god ting, Det benytter Dijkstra's algoritme sig også af...

Janus: Jo, jeg havde da forestillet at Krak mere eller mindre frivilligt ville udlevere de data, det skal nok fordeles lidt jævnt ud over en måneds tid, jeg er ikke sikker på at de er helt tilfredse med 1643*1642/2 forespørgsler . Jeg ikke fuldstændig klar over hvad du mener med det sidste forslag med matrikel.

Tabellen kunne også konstrueres hvis bare man kendte afstandene mellem de geografisk tilstødende postnumre for hvert postnummer. Jeg ved ikke om det var noget lignende Janus mente?

kigger vi på noget helt der også er rimelig nemt at implementere, så kunne brugeren (kunden), bare blive præsenteret for et DK kort, klik hvor du bor, klik hvor du vil flytte hen. og afstanden kan så approximeres efter en fugle flugts linje, med undtagelser, du skal f.eks. over broerne for at komme fra Jylland til Sjælland.

//Troels