Å bestemme den raskeste ruten mellom to punkter er et sentralt problem i mange bruksområder: fra satellittnavigasjon til nettverksadministrasjon, fra logistikk til videospill, opp til nettkartene som vi vanligvis konsulterer. På grunnlag av disse søknadene ligger matematiske modellerkalt graferOg algoritmer i stand til å identifisere den optimale ruten. Blant disse er en av de viktigsteDijkstras algoritmesom lar deg effektivt beregne den korteste veien mellom et startpunkt og en destinasjon. De fleste av navigasjonssystemene vi bruker hver dag er basert på dette prinsippet.
Det optimale ruteproblemet
For å representere problemet bruker vi en matematisk enhet kalt kurvesom består av noder (eller hjørner), som representerer viktige punkter som kryss, byer eller enheter, og fra buersom i stedet beskriver forbindelsene mellom disse nodene. Hver bue er assosiert med en vekt; vi har ofte en tendens til å tolke denne vekten som reisetiden, men det er faktisk et mer generelt begrep, nemlig koste.
Vekten til en bane, som er et sett med buer og noder, kan referere til flere størrelser:
- Avstand fysikk
- Tid Av reise
- Forbruk av drivstoff
- Bompenger eller økonomiske kostnader
- Nivå på sikkerhet eller risiko
I reelle problemer virker ikke disse faktorene separat, men i kombinert måte. Begrepet er derfor introdusert i teoretiske applikasjoner generalisert kostnadeller en syntetisk mengde som integrerer flere variabler i en enkelt parameter. Den generaliserte kostnaden har ikke nødvendigvis en fysisk måleenhet: det er en «normalisert» størrelse som gjør at forskjellige elementer kan sammenlignes med hverandre. Med andre ord, en enkelt indikator er konstruert som representerer den generelle oppførselen til systemet.
For eksempel, en navigator kan kombinere reisetid, trafikkforhold og energiforbruk. Problemet blir da finne veien som minimerer den totale generaliserte kostnadenikke nødvendigvis tiden.
Hvordan Dijkstras algoritme fungerer
Dijkstras algoritme er en prosedyre som starter fra en innledende node og identifiserte en siste nodefinn minst kostnadsvei til de andre nodene i grafen opp til ankomstnoden. Det er basert på en såkalt tilnærming grådig (bokstavelig talt «grådig») som ved hvert trinn, velger den lokalt beste løsningengradvis å bygge den globale løsningen. For å forstå hvordan det fungerer, kan vi forestille oss algoritmeskjemaet delt inn i fire logiske faser:
- Initialisering: en kostnad på null er tilordnet utgangspunktet, mens alle de andre nodene i grafen i utgangspunktet behandles med uendelige kostnader, siden vi ennå ikke vet hvordan vi skal nå dem.
- Utvalg: blant alle nodene som ennå ikke er analysert, velges den med den laveste registrerte kostnaden. Denne noden blir vårt nåværende referansepunkt og representerer den mest praktiske ruten kjent frem til det punktet.
- Oppdatering: nodene som er direkte koblet, via buer, til den aktuelle noden analyseres. For hver av dem blir det verifisert om, ved å passere gjennom den nåværende noden, oppnås en lavere totalkostnad enn den som er registrert tidligere. Dersom den nye ruten er billigere oppdaterer vi kostnadsverdien og noterer nåværende node som «forrige trinn». Dette vil til slutt tjene til å rekonstruere den optimale veien (dvs. løsningen) bakover. Når verifiseringen er fullført, merkes referansenoden som definitiv, siden vi er sikre på at kostnadene for å nå den ikke lenger kan forbedres.
- Iterasjon: valg- og oppdateringstrinnene gjentas til den endelige destinasjonen er nådd eller nodene som skal analyseres går tom.
Algoritmen kan visuelt forestilles som enbølge som forplanter seg i konsentriske sirkler fra startnoden. Denne utvidelsen strekker seg først til de laveste nodene og kartlegger, trinn for trinn, hele nettverket. Denne mekanismen garanterer at en node er «fiksert» som definitiv bare når det er matematisk sikkert at banen som er funnet er den mest effektive av alle.
Imidlertid avslører denne logikken basert på den progressive utvidelsen av bølgen også den viktigste teoretisk grense for algoritmen: behovet for at alle kostnader (kantvekter) skal være positive. Hvis negative kostnader eksisterte, kunne en vei som i utgangspunktet var lengre og forkastet av bølgen plutselig vise seg å være billigere på et senere tidspunkt, og kaste hele utvelgelsesprosessen ut i krise og hindre oss i å betrakte enhver node som nettopp er besøkt som «definitiv».
Applikasjoner, kompleksitet og begrensninger
Dijkstras algoritme er en hjørnestein i informatikk for enkelhet og robusthet og er fortsatt mye brukt i dag på en rekke felt, som f.eks navigasjonssystemer (beregning av optimale ruter på veinettet med GPS), deogistikk (optimalisering av leveringsruter), datanettverk Og kunstig intelligens. Ytelsen til algoritmen avhenger av datastrukturer som brukesslik at jo enklere implementeringen er, desto mindre effektiv er algoritmen og dermed løsningstiden. Til tross for fordelene er det imidlertid noen begrensninger. Som nevnt før, algoritmen det fungerer ikke med negative vekter. Videre kan det være tyngende på veldig store grafer uten riktige optimaliseringer og har begrensningene krever en enkelt startkilde: For mer komplekse problemer er det derfor nødvendig med variasjoner.
Kilder
Cascetta E. – Modeller for transportsystemer. Teori og anvendelser
