k trasowanie najkrótszej ścieżki

k najkrótszej ścieżki jest uogólnieniem problemu trasowania najkrótszej ścieżki w danej sieci. Pyta nie tylko o najkrótszą ścieżkę, ale także o następne k−1 najkrótszych ścieżek (które mogą być dłuższe niż najkrótsza ścieżka). Odmianą problemu jest k najkrótszych ścieżek bez pętli.

Znalezienie k najkrótszych ścieżek jest możliwe poprzez rozszerzenie algorytmu Dijkstry lub algorytmu Bellmana-Forda .

Historia

Od 1957 roku opublikowano wiele artykułów dotyczących problemu trasowania k najkrótszej ścieżki. Większość fundamentalnych prac wykonano w latach 1960-2001. Od tego czasu większość badań dotyczyła zastosowań problemu i jego wariantów. W 2010 roku Michael Günther i in. opublikował książkę na temat Symbolicznego obliczania k - najkrótszych ścieżek i powiązanych miar za pomocą narzędzia algebry procesów stochastycznych CASPA .

Algorytm

Algorytm Dijkstry można uogólnić, aby znaleźć k najkrótszych ścieżek.

definicje :
  • G(V, E) : graf skierowany ważony, ze zbiorem wierzchołków V i zbiorem skierowanych krawędzi E ,
  • w(u, v) : koszt skierowanej krawędzi od węzła u do węzła v (koszty są nieujemne).
Łącza, które nie spełniają ograniczeń na najkrótszej ścieżce, są usuwane z grafu
  • s : węzeł źródłowy
  • t : węzeł docelowy
  • K : liczba najkrótszych ścieżek do znalezienia
  • p u : ścieżka od s do u
  • B to struktura danych sterty zawierająca ścieżki
  • P : zbiór najkrótszych ścieżek od s do t
  • count u : liczba najkrótszych znalezionych ścieżek do węzła u

Algorytm:

P =puste,
policz u = 0, dla wszystkich u w V
wstaw ścieżkę p s = {s} do B z kosztem 0
, podczas gdy B nie jest puste i policz t < K :
– niech p u będzie najkrótszą ścieżką kosztową w B z kosztem do
- b = b - {p u } , policz u = policz u + 1
– jeśli u = t to P = P U {p u }
– jeśli liczba u < K to
  • dla każdego wierzchołka v sąsiadującego z u :
– niech p v będzie nową ścieżką o koszcie C + w(u, v) utworzoną przez konkatenację krawędź (u, v) do ścieżki p u
– wstaw p v do B
return P

Wariacje

Istnieją dwie główne odmiany problemu trasowania k najkrótszej ścieżki. W jednej odmianie ścieżki mogą odwiedzać ten sam węzeł więcej niż jeden raz, tworząc w ten sposób pętle. W innym wariancie ścieżki muszą być proste i pozbawione pętli . Wersję z pętlą można rozwiązać za pomocą algorytmu Eppsteina , a wersję bez pętli można rozwiązać za pomocą algorytmu Yena .

Zapętlony wariant

W tym wariancie problem jest uproszczony, ponieważ nie wymaga się, aby ścieżki były pozbawione pętli. Rozwiązanie zostało podane przez BL Foxa w 1975 roku, w którym k - najkrótsze ścieżki są określone w O ( m + kn log n ) asymptotycznej złożoności czasowej (przy użyciu notacji dużego O ). W 1998 roku David Eppstein zgłosił podejście, które utrzymuje asymptotyczną złożoność O ( m + n log n + k ) przez obliczenie niejawnej reprezentacji ścieżek, z których każda może zostać wyprowadzona w O ( n ) dodatkowym czasie. W 2015 roku Akuba i in. opracowali metodę indeksowania jako znacznie szybszą alternatywę dla algorytmu Eppsteina, w której struktura danych zwana indeksem jest konstruowana z grafu, a następnie można szybko uzyskać górne k odległości między dowolnymi parami wierzchołków.

Wariant bez pętli

W wariancie bez pętli ścieżki nie mogą zawierać pętli, co dodaje dodatkowy poziom złożoności. Można to rozwiązać za pomocą algorytmu Yena, aby znaleźć długości wszystkich najkrótszych ścieżek od stałego węzła do wszystkich innych węzłów w n -węzłowej sieci bez ujemnej odległości, technika wymagająca tylko 2 n 2 dodań i n 2 porównań, mniej niż inne dostępne algorytmy najkrótszej ścieżki . Złożoność czasu działania jest pseudowielomianem i wynosi O ( kn ( m + n log n )) (gdzie m i n oznaczają odpowiednio liczbę krawędzi i wierzchołków). W 2007 roku John Hershberger i Subhash Suri zaproponowali algorytm ścieżek zastępczych, bardziej wydajną implementację algorytmu Lawlera i Yena z poprawą O ( n ) w czasie.

Kilka przykładów i opis

Przykład 1

Poniższy przykład wykorzystuje model Yena do znalezienia k najkrótszych ścieżek między komunikującymi się węzłami końcowymi. Oznacza to, że znajduje najkrótszą ścieżkę, drugą najkrótszą ścieżkę itd. aż do K -tej najkrótszej ścieżki. Więcej szczegółów można znaleźć tutaj . Kod przedstawiony w tym przykładzie próbuje rozwiązać k najkrótszej ścieżki dla sieci 15-węzłowej zawierającej kombinację łączy jednokierunkowych i dwukierunkowych:

15-węzłowa sieć zawierająca kombinację łączy dwukierunkowych i jednokierunkowych

Przykład nr 2

Innym przykładem jest użycie algorytmu k najkrótszych ścieżek do śledzenia wielu obiektów. Technika ta implementuje śledzenie wielu obiektów w oparciu o k najkrótszych ścieżek. Jako dane wejściowe używany jest zestaw probabilistycznych map zajętości. Detektor obiektów zapewnia dane wejściowe.

Pełne informacje można znaleźć na stronie „ Laboratorium wizji komputerowej – CVLAB”.

Przykład nr 3

Innym zastosowaniem algorytmów k najkrótszych ścieżek jest zaprojektowanie sieci tranzytowej, która poprawia wrażenia pasażerów w systemach transportu publicznego. Taki przykład sieci tranzytowej można zbudować uwzględniając czas przejazdu. Oprócz czasu podróży, w zależności od ograniczeń ekonomicznych i geograficznych, mogą zostać uwzględnione inne warunki. Pomimo różnic w parametrach k najkrótszej ścieżki znajdują najbardziej optymalne rozwiązania, które spełniają prawie wszystkie potrzeby użytkownika. Takie zastosowania k algorytmy najkrótszej ścieżki stają się powszechne, ostatnio Xu, He, Song i Chaudry (2012) badali problemy k najkrótszej ścieżki w systemach sieci tranzytowych.

Aplikacje

Routing k najkrótszej ścieżki jest dobrą alternatywą dla:

Powiązane problemy

Czerkaski i in. zapewnić więcej algorytmów i powiązanych ocen.

Zobacz też

Notatki

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=K_shortest_path_routing&oldid=1141285906 ”