Endelig
I køen
Undersøgte kanter

  • Aktuel
  • I køen
  • Endelig
  • Vej
  • Gæt i luftlinje
Et klik på en knude sætter

Mere om A*-søgning

A*-søgning

A*-søgning finder en korteste vej fra en start til et mål, ligesom Dijkstras algoritme, men den ved nogenlunde, hvor målet er. Hver knude får et gæt på den afstand, der er tilbage, den lige linje til målet, og søgningen fortsætter altid fra den knude, der har den laveste afstand indtil nu plus gættet. Klik på en knude for at starte fra den, vælg et mål, og gå trin for trin for at se søgningen styre mod målet og lade hele hjørner af grafen være urørte. Tryk på Afspil for at se søgningen, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst. Klik på en knude for at gøre den til start; skift klikket til Mål, og klik på en anden knude for at gøre den til mål. Tallet på hver kant er dens længde, tallet på hver knude dens afstand indtil nu, og den stiplede linje gættet i luftlinje på den afstand, der er tilbage. Rækken under grafen er køen, laveste score først, med hver knudes score: afstanden indtil nu plus gættet. Ny graf laver en anden graf; vælg, hvor mange knuder og kanter den har. Når brættet er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End springer til starten og slutningen.

Sådan virker det

  1. Klik på en knude for at gøre den til start. Skift klikket til Mål, og klik på en anden knude for at gøre den til mål.
  2. Tryk på Afspil, eller brug Trin og Tilbage for at gå et trin ad gangen. Træk i trinskyderen for at springe hvorhen som helst i søgningen.
  3. Følg scorerne i køen og det stiplede gæt i luftlinje. Til sidst kan du sammenligne de knuder, A* skulle bruge, med Dijkstras algoritme.

Sådan virker A*-søgning

Giv starten afstand 0, og sæt den i en kø. Hver knude i køen har en score: dens afstand indtil nu plus et gæt på den afstand, der er tilbage. Gentag: tag knuden med den laveste score, og gør dens afstand endelig. Er det målet, så stop. Ellers skal du for hver nabo, der ikke er endelig, lægge kantens længde til knudens afstand; er det kortere end naboens afstand indtil nu, så sænk den, husk knuden som vejen dertil, og sæt naboen i køen med dens nye score.

Hvorfor gættet aldrig må være for langt

A* finder en korteste vej, så længe gættet aldrig siger, at målet er længere væk, end det virkelig er: et tilladeligt gæt. Den lige linje er et, for ingen vej mellem to steder er kortere end den lige linje. Et for langt gæt kan få A* til at springe den bedste rute over; et gæt på 0 overalt gør A* til Dijkstras algoritme, som er sikker, men søger i alle retninger. Jo bedre gættet er, jo færre knuder skal A* bruge. I appen er hver kant så lang, som den er tegnet, rundet op, så den lige linje er et sikkert gæt.

Ofte stillede spørgsmål

Hvad er A*-søgning?

En stifindingsalgoritme, der finder en korteste vej fra en start til et mål. Den virker som Dijkstras algoritme, men ordner sin kø efter afstanden indtil nu plus et gæt på den afstand, der er tilbage, så den styrer mod målet i stedet for at brede sig ud i alle retninger.

Hvad er en tilladelig heuristik?

Et gæt på afstanden til målet, der aldrig er længere end den virkelige korteste afstand. Med et tilladeligt gæt finder A* altid en korteste vej. Afstanden i luftlinje på et kort er det klassiske eksempel.

Er A* hurtigere end Dijkstras algoritme?

Som regel, når du skal finde vejen til ét mål og har et godt gæt: A* gør færre knuder endelige, fordi knuder, der ligger væk fra målet, får høje scorer. Med et gæt på 0 gør den præcis det samme som Dijkstras algoritme. Dijkstras algoritme er det bedste valg, når du skal bruge afstandene til alle knuder.

Hvor bruges A*?

I computerspil til at flytte figurer uden om forhindringer, i ruteplanlæggere, i planlægning af robotbevægelser og i programmer, der løser puslespil som 15-spillet, hvor gættet tæller, hvor langt brikkerne er fra deres pladser.

Bliver min graf sendt nogen steder hen?

Nej. Grafen laves og gennemsøges i din browser, og dine seneste indstillinger gemmes i denne browsers lokale lager.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Gå til Editor