k kortaste vägen

Det k kortaste vägdirigeringsproblemet är en generalisering av det kortaste vägdirigeringsproblemet i ett givet nätverk. Den frågar inte bara om en kortaste väg utan också om nästa k−1 kortaste väg (som kan vara längre än den kortaste vägen). En variant av problemet är de slinglösa k kortaste vägarna.

Att hitta k kortaste vägarna är möjligt genom att utöka Dijkstra-algoritmen eller Bellman-Ford-algoritmen .

Historia

Sedan 1957 har många artiklar publicerats om problemet med den kortaste vägen. De flesta av de grundläggande arbetena gjordes mellan 1960-talet och 2001. Sedan dess har det mesta av forskningen handlat om problemets tillämpningar och dess varianter. 2010, Michael Günther et al. publicerade en bok om symbolisk beräkning av k -kortaste vägar och relaterade mått med det stokastiska processalgebraverktyget CASPA .

Algoritm

Dijkstra -algoritmen kan generaliseras för att hitta de k kortaste vägarna.

Definitioner :
  • G(V, E) : vägd riktad graf, med uppsättning av hörn V och uppsättning riktade kanter E ,
  • w(u, v) : kostnad för riktad kant från nod u till nod v (kostnaderna är icke-negativa).
Länkar som inte uppfyller begränsningar på den kortaste vägen tas bort från grafen
  • s : källnoden
  • t : destinationsnoden
  • K : antalet kortaste vägar att hitta
  • p u : en väg från s till u
  • B är en högdatastruktur som innehåller vägar
  • P : uppsättning kortaste vägar från s till t
  • count u : antal kortaste vägar som hittats till nod u

Algoritm:

P =tom,
räkna u = 0, för alla u i V
infoga väg p s = {s} i B med kostnad 0
medan B inte är tom och räkna t < K :
– låt p u vara den kortaste kostnadsvägen i B med kostnad C
– B = B − {p u } , räkna u = räkna u + 1
– om u = t så P = P U {p u }
– om räkna u < K då
  • för varje vertex v intill u :
– låt p v vara en ny väg med kostnad C + w(u, v) bildad av sammanlänkning av kant (u, v) till väg p u
– infoga p v i B
retur P

Variationer

Det finns två huvudvarianter av routingproblemet med k kortaste vägen. I en variant tillåts banor att besöka samma nod mer än en gång, vilket skapar loopar. I en annan variant krävs att vägar är enkla och loopfria . Den loopiga versionen är lösbar med Eppsteins algoritm och den looplösa variationen är lösbar med Yens algoritm .

Loopy variant

I den här varianten förenklas problemet genom att inte kräva att vägar ska vara loopfria. En lösning gavs av BL Fox 1975 där de k -kortaste vägarna bestäms i O ( m + kn log n ) asymptotisk tidskomplexitet (med hjälp av big O -notation . 1998 rapporterade David Eppstein ett tillvägagångssätt som upprätthåller en asymptotisk komplexitet på O ( m + n log n + k ) genom att beräkna en implicit representation av vägarna, som var och en kan matas ut i O ( n ) extra tid. År 2015 tog Akuba et al fram en indexeringsmetod som ett betydligt snabbare alternativ för Eppsteins algoritm, där en datastruktur som kallas ett index konstrueras från en graf och sedan topp- k avstånd mellan godtyckliga par av hörn kan snabbt erhållas.

Slinglös variant

I den slinglösa varianten är vägarna förbjudna att innehålla slingor, vilket ger en extra komplexitetsnivå. Det kan lösas med hjälp av Yens algoritm för att hitta längden på alla kortaste vägar från en fast nod till alla andra noder i ett n -nod-nätverk med icke negativt avstånd, en teknik som endast kräver 2 n 2 tillägg och n 2 jämförelse, färre än andra tillgängliga kortaste väg algoritmer behöver. Körtidskomplexiteten är pseudopolynom , vilket är O ( kn ( m + n log n )) (där m och n representerar antalet kanter respektive hörn). 2007 John Hershberger och Subhash Suri en ersättningsvägsalgoritm, en mer effektiv implementering av Lawlers och Yens algoritm med O ( n ) förbättring i tid.

Några exempel och beskrivning

Exempel #1

Följande exempel använder sig av Yens modell för att hitta k kortaste vägarna mellan kommunicerande ändnoder. Det vill säga att den hittar en kortaste väg, näst kortaste väg etc. upp till den K: e kortaste vägen. Mer detaljer finns här . Koden som tillhandahålls i det här exemplet försöker lösa det k kortaste vägdirigeringsproblemet för ett nätverk med 15 noder som innehåller en kombination av enkelriktade och dubbelriktade länkar:

15-nodsnätverk som innehåller en kombination av dubbelriktade och enkelriktade länkar

Exempel #2

Ett annat exempel är användningen av k kortaste vägarnas algoritm för att spåra flera objekt. Tekniken implementerar en spårning av flera objekt baserat på den k kortaste vägarnas routingalgoritm. En uppsättning probabilistiska beläggningskartor används som indata. En objektdetektor tillhandahåller ingången.

Den fullständiga informationen finns på " Computer Vision Laboratory – CVLAB".

Exempel #3

En annan användning av k kortaste vägarnas algoritmer är att designa ett transitnät som förbättrar passagerarnas upplevelse av kollektivtrafiksystem. Ett sådant exempel på ett transitnät kan konstrueras genom att ta hänsyn till restid. Utöver restid kan andra villkor gälla beroende på ekonomiska och geografiska begränsningar. Trots variationer i parametrar hittar de k kortaste vägalgoritmerna de mest optimala lösningarna som tillfredsställer nästan alla användarbehov. Sådana tillämpningar av k kortaste vägsalgoritmer blir vanliga, nyligen studerade Xu, He, Song och Chaudry (2012) de k kortaste vägproblemen i transitnätsystem.

Ansökningar

Den k kortaste vägen är ett bra alternativ för:

Relaterade problem

Cherkassky et al. tillhandahålla fler algoritmer och tillhörande utvärderingar.

Se även

Anteckningar

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=K_shortest_path_routing&oldid=1141285906 "