Korteste sti-problem - Shortest path problem

I grafteori er det korteste baneproblemet problemet med å finne en sti mellom to hjørner (eller noder) i en graf slik at summen av vekten av dens konstituerende kanter minimeres.

Problemet med å finne den korteste stien mellom to kryss på et veikart kan modelleres som et spesielt tilfelle av det korteste sti-problemet i grafer, der toppunktene tilsvarer kryss og kantene tilsvarer veisegmenter, hver vektet med lengden på segmentet.

Definisjon

Det korteste sti-problemet kan defineres for grafer enten det er ikke-rettet , rettet eller blandet . Det er definert her for ikke-rettet grafer; for dirigerte grafer krever definisjonen av bane at påfølgende hjørner blir koblet sammen med en passende rettet kant.

To hjørner er tilstøtende når begge faller inn i en felles kant. En sti i en ikke-rettet graf er en sekvens av hjørner som ligger ved siden av for . En slik sti kalles en sti med lengde fra til . (Dette er variabler; deres nummerering her er relatert til deres posisjon i sekvensen og trenger ikke å forholde seg til noen kanonisk merking av toppunktene.) ${\ displaystyle P = (v_ {1}, v_ {2}, \ ldots, v_ {n}) \ in V \ times V \ times \ cdots \ times V}$${\ displaystyle v_ {i}}$${\ displaystyle v_ {i + 1}}$${\ displaystyle 1 \ leq i <n}$${\ displaystyle P}$${\ displaystyle n-1}$${\ displaystyle v_ {1}}$${\ displaystyle v_ {n}}$${\ displaystyle v_ {i}}$

La være kanten hendelsen for både og . Gitt en virkelig verdsatt vektfunksjon , og en ikke-rettet (enkel) graf , er den korteste banen fra til banen (hvor og ) som over alt mulig minimerer summen Når hver kant i grafen har enhetsvekt eller , tilsvarer dette finne stien med færrest kanter. ${\ displaystyle e_ {i, j}}$${\ displaystyle v_ {i}}$${\ displaystyle v_ {j}}$${\ displaystyle f: E \ rightarrow \ mathbb {R}}$${\ displaystyle G}$${\ displaystyle v}$${\ displaystyle v '}$${\ displaystyle P = (v_ {1}, v_ {2}, \ ldots, v_ {n})}$${\ displaystyle v_ {1} = v}$${\ displaystyle v_ {n} = v '}$${\ displaystyle n}$${\ displaystyle \ sum _ {i = 1} ^ {n-1} f (e_ {i, i + 1}).}$${\ displaystyle f: E \ rightarrow \ {1 \}}$

Problemet kalles også noen ganger det korteste stien-problemet for å skille det fra følgende varianter:

• Den enkelt-kilde korteste vei problem , der vi har for å finne korteste vei fra en kilde node v til alle andre topp-punkt i diagrammet.
• Den enkelt-destinasjon korteste vei problem , der vi har for å finne korteste vei fra samtlige hjørner i den rettede graf til en enkelt destinasjon toppunkt v . Dette kan reduseres til det korteste sti-problemet med én kilde ved å reversere buene i den rettet grafen.
• Hele parets korteste sti-problem , der vi må finne korteste stier mellom hvert par av toppunktene v , v ' i grafen.

Disse generaliseringene har betydelig mer effektive algoritmer enn den forenklede tilnærmingen med å kjøre en enkeltpar korteste algoritme på alle relevante par av hjørner.

Algoritmer

De viktigste algoritmene for å løse dette problemet er:

• Dijkstras algoritme løser kortkjøringsveiproblemet med en kilde med ikke-negativ kantvekt.
• Bellman – Ford algoritme løser enkeltkildeproblemet hvis kantvekter kan være negative.
• En * søkealgoritme løser den korteste stien med ett par ved å bruke heuristikk for å prøve å øke hastigheten på søket.
• Floyd – Warshall-algoritmen løser alle parens korteste veier.
• Johnsons algoritme løser alle par korteste stier, og kan være raskere enn Floyd – Warshall på sparsomme grafer .
• Viterbi-algoritme løser det korteste stokastiske sti-problemet med en ekstra sannsynlig vekt på hver node.

Ytterligere algoritmer og tilhørende evalueringer finnes i Cherkassky, Goldberg & Radzik (1996) .

Korteste stier med én kilde

Ikke-dirigerte grafer

Vekter	Tidskompleksitet	Forfatter
ℝ +	O ( V 2 )	Dijkstra 1959
ℝ +	O (( E  +  V ) log  V )	Johnson 1977 ( binær dyng )
ℝ +	O ( E  +  V  log  V )	Fredman & Tarjan 1984 ( Fibonacci-dyngen )
ℕ	O ( E )	Thorup 1999 (krever multiplikasjon med konstant tid)

Uveide grafer

Algoritme	Tidskompleksitet	Forfatter
Bredde-første søk	O ( E  +  V )

Regisserte asykliske grafer (DAGer)

En algoritme som bruker topologisk sortering kan løse den enkeltkildes korteste veiproblemet i tid Θ ( E + V ) i vilkårlig vektede DAGer.

Rettet grafer med ikke-negative vekter

Følgende tabell er hentet fra Schrijver (2004) , med noen rettelser og tillegg. En grønn bakgrunn indikerer en asymptotisk best bundet i tabellen; L er den maksimale lengden (eller vekten) blant alle kanter, forutsatt heltallvekt.

Vekter	Algoritme	Tidskompleksitet	Forfatter
ℝ		O ( V 2 EL )	Ford 1956
ℝ	Bellman – Ford algoritme	O ( VE )	Shimbel 1955 , Bellman 1958 , Moore 1959
ℝ		O ( V 2  log  V )	Dantzig 1960
ℝ	Dijkstras algoritme med liste	O ( V 2 )	Leyzorek et al. 1957 , Dijkstra 1959 , Minty (se Pollack & Wiebenson 1960 ), Whiting & Hillier 1960
ℝ	Dijkstras algoritme med binær bunke	O (( E  +  V ) log  V )	Johnson 1977
ℝ	Dijkstras algoritme med Fibonacci-heap	O ( E  +  V  log  V )	Fredman & Tarjan 1984 , Fredman & Tarjan 1987
ℕ	Dial's algoritme ( Dijkstras algoritme som bruker en bøttekø med L- skuffer)	O ( E  +  LV )	Ring 1969
		O ( E  logg  L )	Johnson 1981 , Karlsson & Poblete 1983
	Gabows algoritme	O ( E  log E / V  L )	Gabow 1983 , Gabow 1985
		O ( E  +  V √ logg L )	Ahuja et al. 1990
	Thorup	O ( E  +  V-  logg  V )	Thorup 2004

Rettet grafer med vilkårlige vekter uten negative sykluser

Vekter	Algoritme	Tidskompleksitet	Forfatter
ℝ		O ( V 2 EL )	Ford 1956
ℝ	Bellman – Ford algoritme	O ( VE )	Shimbel 1955 , Bellman 1958 , Moore 1959
ℝ	Johnson-Dijkstra med binær dyng	O ( V  ( E  + log  V ))	Johnson 1977
ℝ	Johnson-Dijkstra med Fibonacci-dyngen	O ( V  ( E  + log  V ))	Fredman & Tarjan 1984 , Fredman & Tarjan 1987 , tilpasset etter Johnson 1977
ℕ	Johnsons teknikk anvendt på Dals algoritme	O ( V  ( E  +  L ))	Dial 1969 , tilpasset etter Johnson 1977

Planrettede grafer med vilkårlige vekter

Alle par korteste stier

Problemet med kortest sti for alle par finner de korteste stiene mellom hvert par av toppunktene v , v ' i grafen. Problemet med kortest stier i parene for uvektede rettet grafer ble introdusert av Shimbel (1953) , som observerte at det kunne løses ved et lineært antall matriksmultiplikasjoner som tar en total tid på O ( V ⁴ ) .

Udirigert graf

Vekter	Tidskompleksitet	Algoritme
ℝ +	O ( V 3 )	Floyd – Warshall-algoritme
${\ displaystyle \ {1, \ infty \}}$	${\ displaystyle O (V ^ {\ omega} \ log V)}$	Seidels algoritme (forventet kjøretid)
ℕ	${\ displaystyle O (V ^ {3} / 2 ^ {\ Omega (\ log n) ^ {1/2}})}$	Williams 2014
ℝ +	O ( EV  log α ( E , V ))	Pettie & Ramachandran 2002
ℕ	O ( EV )	Thorup 1999 gjaldt hvert toppunkt (krever multiplikasjon med konstant tid).

Regissert graf

Vekter	Tidskompleksitet	Algoritme
ℝ (ingen negative sykluser)	O ( V 3 )	Floyd – Warshall-algoritme
ℕ	${\ displaystyle O (V ^ {3} / 2 ^ {\ Omega (\ log n) ^ {1/2}})}$	Williams 2014
ℝ (ingen negative sykluser)	O ( EV  +  V 2  log  V )	Johnson – Dijkstra
ℝ (ingen negative sykluser)	O ( EV  +  V 2  logglogg  V )	Pettie 2004
ℕ	O ( EV  +  V 2  logglogg  V )	Hagerup 2000

applikasjoner

Kortestalgoritmer brukes for å automatisk finne veibeskrivelse mellom fysiske steder, for eksempel veibeskrivelse på nettkartleggingsnettsteder som MapQuest eller Google Maps . For denne applikasjonen er raske spesialiserte algoritmer tilgjengelig.

Hvis man representerer en ikke-deterministisk abstrakt maskin som en graf der hjørner beskriver tilstander og kanter beskriver mulige overganger, kan korteste banealgoritmer brukes til å finne en optimal rekkefølge av valg for å nå en bestemt måltilstand, eller for å etablere lavere grenser på tiden som trengs for å nå en gitt tilstand. For eksempel, hvis hjørner representerer tilstandene til et puslespill som en Rubiks kube, og hver rettet kant tilsvarer et enkelt trekk eller en sving, kan korteste banealgoritmer brukes til å finne en løsning som bruker minst mulig antall trekk.

I et nettverks- eller telekommunikasjonstankegang blir dette korteste sti-problemet noen ganger kalt min-forsinkelsessti-problemet og vanligvis knyttet til et bredeste sti-problem . For eksempel kan algoritmen søke den korteste (min forsinkelsen) bredeste banen, eller den bredeste korteste (min forsinkelsen) banen.

En mer lysende applikasjon er spillene med " seks grader av separasjon " som prøver å finne den korteste veien i grafer som filmstjerner som vises i samme film.

Andre applikasjoner, ofte studert i operasjonsforskning , inkluderer anleggs- og anleggslayout, robotikk , transport og VLSI- design.

Veinettverk

Et veinett kan betraktes som en graf med positive vekter. Knutepunktene representerer veikryss, og hver kant av grafen er assosiert med et veisegment mellom to kryss. Vekten av en kant kan tilsvare lengden på det tilknyttede veisegmentet, tiden det tar å krysse segmentet, eller kostnaden for å krysse segmentet. Ved hjelp av rettet kant er det også mulig å modellere enveiskjørte gater. Slike grafer er spesielle i den forstand at noen kanter er viktigere enn andre for langturer (f.eks. Motorveier). Denne egenskapen er formalisert med begrepet motorveidimensjon. Det er mange algoritmer som utnytter denne egenskapen, og som derfor kan beregne den korteste banen mye raskere enn det som er mulig på generelle grafer.

Alle disse algoritmene fungerer i to faser. I den første fasen er grafen forhåndsbehandlet uten å kjenne kilden eller målnoden. Den andre fasen er spørringsfasen. I denne fasen er kilde og målnode kjent. Tanken er at veinettet er statisk, så forhåndsbehandlingsfasen kan gjøres en gang og brukes til et stort antall spørsmål på samme veinett.

Algoritmen med den raskeste kjente spørretiden kalles navmerking og er i stand til å beregne korteste vei på veinettverkene i Europa eller USA i en brøkdel av en mikrosekund. Andre teknikker som er brukt er:

• ALT ( A * søk , landemerker og trekant ulikhet )
• Bueflagg
• Kontraksjonshierarkier
• Rute for transportnode
• Rekkebasert beskjæring
• Merking
• Navetiketter

Relaterte problemer

For korteste baneproblemer i beregningsgeometri , se den euklidiske korteste banen .

Det omreisende selgerproblemet er problemet med å finne den korteste veien som går gjennom hvert toppunkt nøyaktig en gang, og går tilbake til starten. I motsetning til det korteste veiproblemet, som kan løses i polynomtid i grafer uten negative sykluser, er det reisende selgerproblemet NP-komplett og antas derfor ikke å være effektivt løst for store datasett (se P = NP-problem ). Problemet med å finne den lengste banen i en graf er også NP-komplett.

Det kanadiske reisende-problemet og det stokastiske problemet med korteste sti er generaliseringer der enten grafen ikke er helt kjent for flytteren, endres over tid, eller der handlinger (traversaler) er sannsynlige.

Den korteste multiple frakoblede banen er en representasjon av det primitive banenettverket innenfor rammen av Reptation theory .

Det bredeste sti-problemet søker en sti slik at minimumsmerket for en hvilken som helst kant er så stort som mulig.

Strategiske korteste stier

Noen ganger har kantene i en graf personligheter: hver kant har sin egen egoistiske interesse. Et eksempel er et kommunikasjonsnettverk der hver kant er en datamaskin som muligens tilhører en annen person. Ulike datamaskiner har forskjellige overføringshastigheter, så hver kant i nettverket har en numerisk vekt som er lik antall millisekunder det tar å overføre en melding. Målet vårt er å sende en melding mellom to punkter i nettverket på kortest mulig tid. Hvis vi vet overføringstiden til hver datamaskin (vekten av hver kant), så kan vi bruke en standard algoritme for korteste stier. Hvis vi ikke vet overføringstidene, må vi be hver datamaskin om å fortelle oss overføringstiden. Men datamaskinene kan være egoistiske: en datamaskin kan fortelle oss at overføringstiden er veldig lang, slik at vi ikke kommer til å bry det med meldingene våre. En mulig løsning på dette problemet er å bruke en variant av VCG-mekanismen , som gir datamaskinene et incitament til å avsløre deres sanne vekter.

Lineær programmeringsformulering

Det er en naturlig lineær programmeringsformulering for det korteste sti-problemet, gitt nedenfor. Det er veldig enkelt sammenlignet med de fleste andre bruksområder for lineære programmer i diskret optimalisering , men det illustrerer forbindelser til andre konsepter.

Gitt en rettet graf ( V , A ) med kildenode s , målnode t og kostnad w _ij for hver kant ( i , j ) i A , vurder programmet med variabler x _ij

minimer gjenstand for og for alle jeg ,${\ displaystyle \ sum _ {ij \ in A} w_ {ij} x_ {ij}}$${\ displaystyle x \ geq 0}$${\ displaystyle \ sum _ {j} x_ {ij} - \ sum _ {j} x_ {ji} = {\ begin {cases} 1, & {\ text {if}} i = s; \\ - 1, & {\ text {if}} i = t; \\ 0, & {\ text {ellers.}} \ end {cases}}}$

Intuisjonen bak dette er at det er en indikatorvariabel for om kanten ( i , j ) er en del av den korteste banen: 1 når den er, og 0 hvis den ikke er. Vi ønsker å velge kantsettet med minimal vekt, med forbehold om begrensningen at dette settet danner en bane fra s til t (representert av likhetsbegrensningen: for alle hjørner unntatt s og t antall innkommende og utgående kanter som er en del av stien må være den samme (dvs. at den skal være en sti fra s til t). ${\ displaystyle x_ {ij}}$

Denne LP-en har den spesielle egenskapen at den er integrert; mer spesifikt har hver grunnleggende optimale løsning (når en eksisterer) alle variablene lik 0 eller 1, og settet med kanter hvis variabler lik 1 danner en s - t dipath . Se Ahuja et al. for et bevis, selv om opprinnelsen til denne tilnærmingen dateres tilbake til midten av 1900-tallet.

Det dobbelte for dette lineære programmet er

maksimere y _t - y _s underlagt for alle ij , y _j - y _i ≤ w _ij

og mulige dualer tilsvarer konseptet med en konsekvent heuristikk for A * -algoritmen for korteste veier. For alle mulige dobbel y er de reduserte kostnadene ikke-negative, og A * kjører i hovedsak Dijkstras algoritme på disse reduserte kostnadene. ${\ displaystyle w '_ {ij} = w_ {ij} -y_ {j} + y_ {i}}$

Generelle algebraiske rammeverk på semirings: problemet med algebraisk vei

Mange problemer kan innrammes som en form for den korteste veien for noen passende substituerte forestillinger om tillegg langs en sti og tar minimum. Den generelle tilnærmingen til disse er å betrakte de to operasjonene som en semiring . Semiringmultiplikasjon gjøres langs stien, og tillegget er mellom stiene. Dette generelle rammeverket er kjent som det algebraiske sti-problemet .

De fleste av de klassiske korteste banealgoritmene (og nye) kan formuleres som å løse lineære systemer over slike algebraiske strukturer.

Mer nylig har det blitt utviklet et enda mer generelt rammeverk for å løse disse (og mye mindre åpenbart relaterte problemene) under verdsettelse av algebraer .

Korteste vei i stokastiske tidsavhengige nettverk

I virkelige situasjoner er transportnettverket vanligvis stokastisk og tidsavhengig. Faktisk kan en reisende som krysser en lenke daglig oppleve forskjellige reisetider på den lenken, ikke bare på grunn av svingningene i reisebehovet (opprinnelsesdestinasjonsmatrise), men også på grunn av hendelser som arbeidssoner, dårlige værforhold, ulykker og kjøretøynedbrudd. . Som et resultat er et stokastisk tidsavhengig (STD) nettverk en mer realistisk fremstilling av et faktisk veinett sammenlignet med det deterministiske.

Til tross for betydelig fremgang i løpet av det siste tiåret, er det fortsatt et kontroversielt spørsmål hvordan en optimal vei skal defineres og identifiseres i stokastiske veinettverk. Det er med andre ord ingen unik definisjon av en optimal vei under usikkerhet. Et mulig og vanlig svar på dette spørsmålet er å finne en sti med minimum forventet reisetid. Hovedfordelen med å bruke denne tilnærmingen er at effektive korteste banealgoritmer introdusert for deterministiske nettverk lett kan brukes til å identifisere banen med den minste forventede reisetiden i et stokastisk nettverk. Imidlertid er den resulterende optimale banen identifisert av denne tilnærmingen kanskje ikke pålitelig, fordi denne tilnærmingen ikke takler variasjon i reisetid. For å takle dette problemet bruker noen forskere distribusjon av reisetid i stedet for forventet verdi av det, slik at de finner sannsynlighetsfordelingen av total reisetid ved hjelp av forskjellige optimaliseringsmetoder som dynamisk programmering og Dijkstras algoritme . Disse metodene bruker stokastisk optimalisering , spesielt stokastisk dynamisk programmering for å finne den korteste banen i nettverk med sannsynlig buelengde. Begrepet reisetidspålitelighet brukes om hverandre med variasjon i reisetid i transportforskningslitteraturen, slik at man generelt kan si at jo høyere variasjon i reisetid, jo lavere vil påliteligheten være, og omvendt.

For å gjøre rede for påliteligheten av reisetid mer nøyaktig, er to vanlige alternative definisjoner for en optimal vei under usikkerhet blitt foreslått. Noen har introdusert konseptet med den mest pålitelige banen, med sikte på å maksimere sannsynligheten for å ankomme i tide eller tidligere enn et gitt reisebudsjett. Andre har alternativt fremmet konseptet med en α-pålitelig sti basert på som de hadde til hensikt å minimere reisetidsbudsjettet som kreves for å sikre en forhåndsdefinert sannsynlighet for ankomst.

Se også

• Toveis søk , en algoritme som finner den korteste banen mellom to hjørner i en rettet graf
• Euklidisk korteste vei
• Flytenettverk
• K korteste sti-ruting
• Min-plus matriksmultiplikasjon
• Stifinning
• Bro over korteste vei
• Tre med korteste sti

Referanser

Merknader

Bibliografi

Videre lesning

• Frigioni, D .; Marchetti-Spaccamela, A .; Nanni, U. (1998). Msgstr "Fullt dynamisk utgang begrenset problem med korteste sti med enkelt kilde". Proc. 7. annu. ACM-SIAM Symp. Diskrete algoritmer . Atlanta, GA. s. 212–221. CiteSeerX  10.1.1.32.9856 .
• Dreyfus, SE (oktober 1967). En vurdering av noen korteste sti-algoritmer (PDF) (rapport). Prosjekt Rand. USAs luftvåpen. RM-5433-PR. DTIC AD-661265.