Avatar billede evilfish Nybegynder
04. oktober 2002 - 16:51 Der er 20 kommentarer og
1 løsning

At finde ture

Jeg har et lidt stort problem. Jeg er lidt nybegynder til Mysql - Kan finde ud af at hente og sende, til og fra mysql via PHP.

Problemet ligger i at jeg er ved at spille et spil, hvor der er ret mange veje man kan rejse på, og de er svære at huske. Til det er jeg igang med at lave et lille php script som skal kunne regne det ud for mig.

Jeg har lavet en lille table med række værdierne: id, from1, to1

Det jeg har gjort er at lægge disse ind i from1 og to1

Denon - Rience
Rience - Forty
Fory - Takel

Dette er en af rejserne som ligger i hver sin række.

Hvordan får jeg den til at udregne hvordan jeg kommer fra Denon til Takel Fx????

Og hvis der kommer flere ruter, hvordan får jeg den så til at vise den korteste???
Avatar billede chrlilje Nybegynder
04. oktober 2002 - 17:09 #1
Det er en videnskabsgren for sig selv... Operationsanalyse
Der er forskellige metoder, men det er ikke bare sådan lige at løse
Avatar billede evilfish Nybegynder
04. oktober 2002 - 17:10 #2
"men der er ikke bare sådan lige at løse" Det regnede jeg stærkt med at det heller ikke var - Men jeg vil havde lavet det, og jeg giver ikke op før det er lavet...
Avatar billede chrlilje Nybegynder
04. oktober 2002 - 17:32 #3
Kanon. Det lød bare som om at du fiskede efter en hurtig løsning :-)
Når Krak kan, kan vi også. Jeg skal se om jeg kan finde noget på det. Det er et interessant emne.
Avatar billede evilfish Nybegynder
04. oktober 2002 - 18:02 #4
Kanon - Jeg venter spændt på et svar - Det skal lige siges at der kommer mange rækker - Da der er over 5000+ rejse steder, med hver sin vej til 2 eller 3 af de 5000 - Men jeg har fundet et område vi først kan koncentrere os om, Når det fungere, burde resten jo køre som det skal... :)
Avatar billede morw Nybegynder
04. oktober 2002 - 19:14 #5
Er du ved at lave www.rejseplanen.dk v2.0
Avatar billede evilfish Nybegynder
04. oktober 2002 - 19:22 #6
Næsten

Her er et eksempel på hvordan et kort ser ud: www.1vs1.dk/map.gif


Nu er det så at jeg har kortet, så jeg nemt kan finde vej. Men lads os sige vi ikke har. Vi starter i Edicel - Edicel er et system. I hvert system kan man finde en stargate som kan jumpe til de systemer den er connectet til. I dette tilfælde ved jeg, at den stargate der er i Edicel kan jumpe til Guerin og en anden der ikke er tegnet på kortet.

Jeg vil gerne til Pedimor. Når jeg så skriver Edicel som start position og Pedimor som destination, skal min mysql/php script regne ud at jeg skal følje følgende rute:

Edicel - Guerin
Guerin - Codon
Codon - Clauridin
Clauridin - Elegare
Elegare - Rulcamonwe
Rulcamonwe - Pedimor

Dette er kun en MEGET lille del, men hvis det fungere, jamen så skulle det virke overalt.

I min database har jeg 3 værdier: id, fra, til

Hvis jeg koder Codon og Rience's muligheder ser det sådan her ud:

id: fra: til:
1 Codon Rience
2 Codon Clauridin
3 Codon Guerin
4 Rience Codon
5 Rience Gwenennia

Osv. Med alle de andre...
Avatar billede evilfish Nybegynder
04. oktober 2002 - 19:22 #7
Hvis det giver mening
Avatar billede morw Nybegynder
04. oktober 2002 - 19:30 #8
Dit spørgsmål er klart nok. Men det er en ret svær, som jo ikke løses i ren sql, så du får nok mere hjælp i PHP kategorien.

Den skal jo på en måde benytte rekursivitet (hedder det det?) så den løber alle mulige router igennem. Spørgsmålet er ved der skal når den begynder at løbe rundt i en ring og andre sjove ting. Der er godt nok mange ting at tage højde for. Gad godt se kildekoden til rejseplanen.dk
Avatar billede evilfish Nybegynder
04. oktober 2002 - 19:47 #9
Jeg mente nok også jeg skal rode i php - Men lige nu er det sql delen der skal arbejdes på - Så bagefter går vi igang med php - sådan cirka
Avatar billede jangravgaard Nybegynder
05. oktober 2002 - 17:21 #10
det er noget af en opgave du er igang med.....
Jeg har fundet lidt information til dig, som kan kaste lys over hvordan dit problem evt. kan løses. Det er godt skrevet i Java, men ideen er den samme. Det vil nok også være smartere at lave dit script først og så flette din sql ind bagefter, bare min mening :-)

Her har du linket : http://www.cs.usask.ca/research/research_groups/aries/projects/applets/tutorials/searching/DFS/java/index.shtml
Avatar billede evilfish Nybegynder
05. oktober 2002 - 18:13 #11
Desvæære - Det princip er desværre ikke lige planen
Avatar billede morw Nybegynder
05. oktober 2002 - 18:23 #12
Hvad er din plan så lige? Troede ikke du havde en?

Dette kan ikke løses i ren sql. Hoveddelen ligger i ren programmering.
Sikker på at du får den bedste løsning ved først at læse alle sted-relationer ind i et array i php og så ellers loope dem igennem med f.eks. Breadth-First-Search eller Depth-First-Search som jan... henviste til.
Avatar billede morw Nybegynder
05. oktober 2002 - 18:48 #13
Det er faktisk et spændende emne.

Fandt en side der bruger både BFS og DFS.

Det er en webcrawler i php med sourcecode:

http://fravia.2113.ch/phplab/skeleton.php
Avatar billede evilfish Nybegynder
06. oktober 2002 - 10:32 #14
Hmm - Kan lære jeg har en del at lære så - Problemet med jan's link er, at det der sker hvor den søger er god nok. Mit script skal bare finde den aller korteste vej
Avatar billede evilfish Nybegynder
06. oktober 2002 - 10:54 #15
Morv - Dit link er meget interressant...
Avatar billede bispensgipsgebis Nybegynder
06. oktober 2002 - 23:51 #16
Det du taler om evilfish går typisk under betegnelsen "the travel salesman problem". Jeg ved at Keld Helsgaun, der er underviser på datalogisk institut på Roskilde Universitetscenter har specialiseret sig i problemet.

Det viser sig i midlertid, at der ret hurtigt kan komme astronomiske beregninger på tale. Men jeg mindes, at han i sin tid snakkede om at han havde lavet den hurtigste kendte algoritme.

Desværre er sitet ned i øjeblikket, så jeg kan ikke finde nogle konkrete referencer til dig. Men jeg kigger lige igen i morgen, så skulle det være muligt at finde det til dig.

Men du skal vide at det er en ret kompleks problematik.
Avatar billede morw Nybegynder
07. oktober 2002 - 06:44 #17
Det lyder spændende. Vil gerne noget info fra Keld Helsgaun
Avatar billede evilfish Nybegynder
07. oktober 2002 - 07:25 #18
Bisben - Jeg venter i spænding

Jeg har også erhvervet mig kontakt med nogle af programmørerne på noget der hedder yellowpages eller noget. De har vist nok lavet et grafisk kort der viser en vej fra et sted til et andet. Så informationerne vælter ind...
Avatar billede bispensgipsgebis Nybegynder
07. oktober 2002 - 11:08 #19
Her er så en videnskabelig artikel han har skrevet om emnet:
http://www.dat.ruc.dk/~keld/research/LKH/LKH-1.2/DOC/LKH_REPORT.pdf

Hvis I gerne vil se lidt om manden:
http://www.dat.ruc.dk/~keld/

God fornøjelse
Avatar billede morw Nybegynder
07. oktober 2002 - 16:49 #20
Spændende. Der er også nogle slides om grafalgoritmer:

http://www.dat.ruc.dk/~keld/teaching/algoritmik_e99/Slides/
Avatar billede evilfish Nybegynder
28. januar 2003 - 12:52 #21
Lukker tråd
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Computerworld tilbyder specialiserede kurser i database-management

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester