lørdag, januar 23, 2021

Diskussion af shortest-path algoritmer

Daily Rush Debat Programmering Diskussion af shortest-path algoritmer

  • Forfatter
    Emne
  • #0

    analkongen
    Bruger
    178 indlæg
    Offline

    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?

Viser 10 kommentarer - 1 til 10 (af 10 i alt)
  • Forfatter
    Kommentarer
  • #5

    Xion
    Bruger
    948 indlæg
    Offline

    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

    #6

    Xion
    Bruger
    948 indlæg
    Offline

    Til 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

    #8

    gnavpot
    Bruger
    2.494 indlæg
    Offline

    Som #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.

    #9

    Happyfeet
    Bruger
    1.436 indlæg
    Offline

    Men 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.

    #10

    analkongen
    Bruger
    178 indlæg
    Offline

    #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.

    #13

    Kolben
    Bruger
    18.939 indlæg
    Offline

    #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?

    #14

    qoz
    Bruger
    2.775 indlæg
    Offline

    #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).

    http://en.wikipedia.org/wiki/Bidirectional_search

    #15

    analkongen
    Bruger
    178 indlæg
    Offline

    #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.

    #16

    analkongen
    Bruger
    178 indlæg
    Offline

    #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

    #20

    qoz
    Bruger
    2.775 indlæg
    Offline

    #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.gif

    Der 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.

Viser 10 kommentarer - 1 til 10 (af 10 i alt)
  • Du skal være logget ind for at kommentere på dette indlæg.