Algoritmene A* og Dijkstra er grunnleggende i banefinding og graf traversal. De brukes mye i navigasjonssystemer, robotikk og nettverksrute. Å forstå deres matematiske grunnlag hjelper til å optimalisere deres ytelse og anvendelse.

Grafrepresentasjon

Begge algoritmene opererer på grafer, som består av noder (vertier) og kanter. Kanter kan ha vekter som representerer kostnader, avstander eller ganger. Grafen kan rettes eller ikke-direkteres, og vektene er vanligvis ikke-negative.

Kostnadsfunksjoner og heuristiske

Kjernen i disse algoritmene innebærer å beregne kostnadene for å nå hver node. Dijkstras algoritme bruker den kumulative kostnaden fra startnoden, mens A* legger til et heuristisk estimat av de resterende kostnadene til målet. Den heuristiske må være tillatt, noe som betyr at det aldri overvurderer den sanne kostnaden.

Matematisk formulering

La G = (V, E) være en graf med virvelløse V og kanter E. Hver kant (u, v) har en vekt w(u, v). Målet er å finne den korteste banen fra startnode s til målnode t.

Dijkstras algoritme oppdaterer avstanden d(v) for hver vertex v, initialisert som d(s) = 0 og d(v) = ⁇ for v ⁇ s. Det iterativt velger vertex med den minste d(v), og deretter slapper av sine nabokanter.

A* modifiserer dette ved å inkludere en heuristisk h(v) som anslår kostnadene fra v til t. Prioritetsfunksjonen blir f(v) = d(v) + h(v). Algoritmen utvider noder basert på den laveste f(v).

Algoritmeeffektivitet

Effektiviteten avhenger av datastrukturer som brukes. Dijkstras algoritme har en tidskompleksitet av O( ⁇ E ⁇ + ⁇ V ⁇ log ⁇ V ⁇ ) med en prioritert kø. A * kan være raskere hvis heuristikken er veldesignet, redusere antall noder utvidet.

  • Graf med ikke-negativ vekt
  • Engstelig heurisme for A*
  • Prioritet kø for nodevalg
  • Avslapping av kanter for å oppdatere kostnader