Diskussion af shortest-path algoritmer
Daily Rush › Debat › Programmering › Diskussion af shortest-path algoritmer
- Dette indlæg indeholder 10 kommentarer, har 6 deltagere og blev senest opdateret af
qoz for 11 år, 6 måneder siden.
- ForfatterEmne
- 03/07/2009 kl. 19:25#0
Nu har jeg snart set på den beskrivelse længe nok, så i denne tråd skal vi diskutere hvilke shortest-path algoritmer, der er bedst.
Umiddelbart vil jeg sige at bedste bud er A* algoritmen med en fornuftig heuristisk funktion.
Om det i givet fald vil være fx Euclidean distance eller Manhattan distance kommer meget an på den konkrete applikation, så det er svært at sige noget generelt om.
Hvad mener i?
- ForfatterEmne
- ForfatterKommentarer
- 03/07/2009 kl. 21:39 #5
Det var dog et sjovt forsøg på at virke interlektuel.
Så længe du ikke har en konkret problemstilling er diskussionen jo nytteløs….There are 10 types of people. Those who can read binary and those who can't
03/07/2009 kl. 21:41 #6Til dem der ikke aner hvad Analkongen snakker om kan i kigge her på Dijkstra Dijkstras shortest path
There are 10 types of people. Those who can read binary and those who can't
03/07/2009 kl. 23:04 #8Som #5 siger så er der jo intet at diskutere før du stiller et problem op som skal løses.
Men alligevel:
A* er god til f.eks. at finde vej på et landkort, netop fordi landkorts “graf” vil være bygget rimeligt simpelt op, og med en fugleflugtsafstand fra alle punkter til målet som kan bruges som input til algoritmen.
Men problemet kan jo være noget andet hvor grafen er mere eller mindre “fucked up”.
F.eks. noget så simpelt som at køre fra Århus til Oslo. Der vil A* (med fugleflugtsdistance som ekstra input), først drøne til Skagen, og så først senere finde vej hen over Storebælt.
Shortest path algoritmer bruges jo ikke kun til at finde vej på kort. Mange problemer kan omskrives til grafproblemer, og de vil i mange tilfælde give nogle syge grafer hvor A* muligvis vil bruge længere tid på at finde løsningen en andre algoritmer.
Det ligger jo netop i ordet heuristik, at det er “en erfaringsbaseret løsningsmetode”, så så længe du ikke har et reelt problem som skal løses, så kan du ikke sige hvilken algoritme der er bedst.
Hellere komme galt afsted, end slet ikke komme afsted.
03/07/2009 kl. 23:08 #9Men shortest path algoritmer i stil med Dijkstras er vel knap så gode til landkort. Hvis den skulle være det skulle man ikke bruge afstande som vægt, men måske et tal der var en repræsentation af afstand, max. fart, risiko for kø etc.
Tag forbehold for tossede, sarkastiske, dumme, grove, unødvendigt aggressive og fejlagtige forumindlæg og kommentarer. Jeg beklager.
03/07/2009 kl. 23:25 #10#5
Du er for nem at trolle (eller også har du aldrig lagt mærke til beskrivelsen af programmeringsforaet).
#9
Det er såvidt intet i vejen for at repræsentere vægten for en edge som en funktion af forskellige værdier. Dog kunne jeg forestille mig at det er mere udbredt at gemme flere værdier pr. edge i stedet, så det at muligt at finde hurtigste vej, korteste vej, billigste vej, etc.
04/07/2009 kl. 00:31 #13#10
Jo flere værdier du gemmer pr. kant des mere fristende bliver en simpel Belman-Ford. Der har du større fleksibilitet mht. hvilke værdier dine kantvægte kan antage, og den kan regne samtlige datasæt i samme gennemløb. Gøres det kan det dog anbefales at bruge noget energi på at reducere antallet af knuder og kanter i inputtet. F.eks. ved at definere et scope eller definere nogle generiske subsets.P=NP?
04/07/2009 kl. 11:10 #14#0 Hvis du ved hvor du starter og hvor du skal hen, så kan du tilføje bidirectional search (søger både fra start og baglæns fra destination).
04/07/2009 kl. 18:15 #15#13
God pointe mht. Bellman-Ford. Havde faktisk glemt alt om den algoritme
Omkring en mere hierarkisk repræsentation af grafen, så er det jo såvidt også relevant i forbindelse med A*.
Det kunne være interessant at vide hvordan fx Google Maps er skruet sammen. Der er jævnt mange veje i en sti som går fra én verdensdel til en anden. Men man kunne godt forestille sig at de beregner en del ting på forhånd, fx alle “overordnede” stier. Så de derved kan lave tabelopslag på noget af dataen, i stedet for ren pathfindning.
04/07/2009 kl. 18:20 #16#14
Såvidt jeg kan se, så kræver den så meget viden om problemområdet at man ligeså godt kan bruge en A* og lave en passende heuristisk funktion i stedet for.
Men ok, den er jo et godt (eller endda bedre) alternativ i nogle situationer, så god pointe
04/07/2009 kl. 21:20 #20#16
Såvidt jeg forstår det, så kan man også bruge bidirectional på en A* – kører bare 2 searches fra start og slut state.Det kræver, at man har en heuristic der er consistent – der er nogle krav den skal opfylde. Er den consistent, så vil man altid finde optimal solution.
På et tidspunkt vil disse 2 searches mødes (lidt forsimplet sagt) og da man ved at man har consistency, så vil man ha’ fundet en optimal løsning fra hver side, og så kombinerer man dem.
Visuelt kan man se det her..
http://www.massey.ac.nz/~mjjohnso/notes/59302/fig03.17.gifDer er det godt nok ikke A*, men bare en normal brute-force graph search. En A* ville ha’ en retning mod slut state, men bidirectional burde stadig hjælpe lidt.
- ForfatterKommentarer
- Du skal være logget ind for at kommentere på dette indlæg.
























