Kolejka kubełkowa - Bucket queue

Kolejka do wiader
Kolejka do wiader
	Tablica kubełków, odpowiednia dla priorytetów z zakresu od 1 do 6. Element o minimalnym priorytecie znajduje się w niepustym kubełku po lewej stronie.
Rodzaj	kolejka priorytetowa
Wynaleziony	1969
Wynalezione przez	Robert Dial
Złożoność czasowa w notacji duże O

Kolejka wiadro jest struktura danych , która implementuje priorytet kolejki abstrakcyjny typ danych : utrzymuje zbiór dynamicznych elementów z priorytetami liczbowych i pozwala na szybki dostęp do elementu z minimum (lub maksimum) priorytet. W kolejce kubełkowej priorytety muszą być liczbami całkowitymi i jest to szczególnie przydatne w aplikacjach, w których priorytety mają niewielki zakres. Kolejka kubełkowa ma postać tablicy kubełków : tablicowej struktury danych , indeksowanej według priorytetów, której komórki zawierają kolekcje elementów o tym samym priorytecie. Przy takiej strukturze danych wstawianie elementów i zmiany ich priorytetów trwają cały czas . Wyszukiwanie i usuwanie elementu o minimalnym priorytecie zajmuje czas proporcjonalny do liczby kubełków lub, poprzez utrzymywanie wskaźnika do ostatnio znalezionego kubełka, w czasie proporcjonalnym do różnicy priorytetów między kolejnymi operacjami.

Kolejka kubełkowa jest odpowiednikiem sortowania według priorytetów (nazywanego także sortowaniem kubełkowym), algorytmu sortowania, który umieszcza elementy w kubełkach zindeksowanych według ich priorytetów, a następnie łączy je. Użycie kolejki kubełkowej jako kolejki priorytetowej w sortowaniu przez selekcję daje postać algorytmu sortowania szufladkowego. Kolejki kubełkowe są również nazywane kolejkami priorytetowymi kubełkowymi lub kolejkami o ograniczonej wysokości . Kiedy są używane do skwantowanych przybliżeń do priorytetów liczb rzeczywistych , są również nazywane nieporządnymi kolejkami priorytetowymi lub pseudopriorytetowymi kolejkami . Są one ściśle powiązane z kolejką kalendarza , strukturą, która używa podobnej tablicy kubełków do dokładnego ustalania priorytetów według liczb rzeczywistych.

Zastosowania kolejki kubełkowej obejmują obliczanie degeneracji grafu , szybkie algorytmy dla najkrótszych ścieżek i najszerszych ścieżek dla grafów z wagami, które są małymi liczbami całkowitymi lub są już posortowane, oraz zachłanne algorytmy aproksymacyjne dla problemu okładki zestawu . Skwantyzowana wersja struktury została również zastosowana do planowania i marszowych sześcianów w grafice komputerowej . Pierwsze użycie kolejki kubełkowej miało miejsce w algorytmie najkrótszej ścieżki autorstwa Diala (1969) .

Operacja

Podstawowa struktura danych

Kolejka typu bucket może obsługiwać elementy o priorytetach liczb całkowitych w zakresie od 0 lub 1 do pewnego znanego ograniczenia $C$ oraz operacje wstawiania elementów, zmiany priorytetu elementów lub wyodrębniania (znajdowania i usuwania) elementu, który ma minimum (lub maksymalny) priorytet. Składa się on z szeregu $A$ o konstrukcji kontenera danych ; w większości źródeł te kontenery są podwójnie połączonymi listami, ale alternatywnie mogą to być tablice dynamiczne lub zestawy dynamiczne . Pojemnik w $p$ -tego komórek Tablica $A [P]$ przechowuje zbiór elementów, których priorytet jest $P$ .

Kolejka łyżki może obsługiwać następujące operacje:

Aby wstawić element $x$ o priorytecie $p$ , dodaj $x$ do kontenera w $A [p]$ .
Aby zmienić priorytet elementu, usuń go z kontenera dla jego starego priorytetu i wstaw go ponownie do kontenera dla nowego priorytetu.
Aby wyodrębnić element o minimalnym lub maksymalnym priorytecie, wykonaj sekwencyjne wyszukiwanie w tablicy, aby znaleźć odpowiednio pierwszy lub ostatni niepusty kontener, wybierz dowolny element z tego kontenera i usuń go z kontenera.

W ten sposób wstawienia i zmiany priorytetów zabierają stały czas, a wyodrębnienie elementu o minimalnym lub maksymalnym priorytecie zajmuje czas $O (C)$ .

Optymalizacje

W ramach optymalizacji struktura danych może rozpocząć każde sekwencyjne wyszukiwanie niepustego zasobnika w ostatnio znalezionym niepustym zasobniku zamiast na początku tablicy. Można to zrobić na dwa różne sposoby, leniwy (opóźniając te sekwencyjne wyszukiwania, dopóki nie są konieczne) lub gorliwy (wykonując wyszukiwania z wyprzedzeniem). Wybór, kiedy przeprowadzić wyszukiwanie, wpływa na to, które operacje struktury danych są spowolnione przez te wyszukiwania. Oryginalna wersja struktury Diala wykorzystywała leniwe wyszukiwanie. Można to zrobić, utrzymując indeks $L,$ który jest dolną granicą minimalnego priorytetu dowolnego elementu znajdującego się obecnie w kolejce. Podczas wstawiania nowego elementu $L$ należy zaktualizować do minimum jego starej wartości i priorytetu nowego elementu. Podczas wyszukiwania elementu o minimalnym priorytecie wyszukiwanie może rozpocząć się od $L$ zamiast od zera, a po wyszukiwaniu należy pozostawić $L$ równy priorytet, który został znaleziony w wyszukiwaniu. Alternatywnie, gorliwa wersja tej optymalizacji aktualizuje $L$ tak, aby zawsze wskazywał na pierwsze niepuste wiadro. Podczas wstawiania nowego elementu o priorytecie mniejszym niż $L$ , struktura danych ustawia $L$ na nowy priorytet, a podczas usuwania ostatniego elementu z wiaderka o priorytecie $L$ , wykonuje sekwencyjne przeszukiwanie większych indeksów, aż do znalezienia niepustego wiaderka i ustawienie $L$ na priorytet wynikowego wiadra.

W każdym z tych dwóch wariantów każde sekwencyjne wyszukiwanie zajmuje czas proporcjonalny do różnicy między starą i nową wartością $L$ . Może to być znacznie szybsze niż czas $O (C)$ związany z wyszukiwaniami w niezoptymalizowanej wersji struktury danych. W wielu zastosowaniach kolejek priorytetowych, takich jak algorytm Dijkstry , minimalne priorytety tworzą sekwencję monotoniczną , pozwalającą na użycie kolejki priorytetowej monotonicznej . W tych zastosowaniach, zarówno dla leniwych, jak i gorliwych odmian zoptymalizowanej struktury, sekwencyjne wyszukiwanie niepustych kubełków obejmuje rozłączne zakresy kubełków. Ponieważ każdy zasobnik znajduje się co najwyżej w jednym z tych zakresów, ich liczba kroków dodaje się co najwyżej do $C$ . W związku z tym w tych aplikacjach całkowity czas dla sekwencji $n$ operacji wynosi $O (n + C)$ , a nie wolniejsze ograniczenie czasowe $O (nC),$ które byłoby wynikiem bez tej optymalizacji. Odpowiednią optymalizację można zastosować w aplikacjach, w których do znalezienia elementów o maksymalnym priorytecie używana jest kolejka kubełków, ale w tym przypadku powinna ona utrzymywać indeks, który ogranicza maksymalny priorytet, a sekwencyjne wyszukiwanie niepustego kubełka powinno być kontynuowane w dół od tej górnej granicy.

Inna optymalizacja (podana już przez Dial 1969 ) może być wykorzystana do zaoszczędzenia miejsca, gdy priorytety są monotoniczne iw trakcie algorytmu zawsze mieszczą się w zakresie wartości $r$ , a nie rozciągają się na cały zakres od 0 do $C$ . W takim przypadku można indeksować tablicę według priorytetów modulo $r,$ a nie według ich rzeczywistych wartości. Poszukiwanie elementu o minimalnym priorytecie powinno zawsze zaczynać się od poprzedniego minimum, aby uniknąć priorytetów, które są wyższe niż minimum, ale mają niższe moduły. W szczególności idea ta może być zastosowana w algorytmie Dijkstry na grafach, których długości krawędzi są liczbami całkowitymi w zakresie od 1 do $r$ .

Ponieważ tworzenie nowej kolejki kubełków wiąże się z inicjalizacją tablicy pustych kubełków, ten krok inicjalizacji zajmuje czas proporcjonalny do liczby priorytetów. Odmiana kolejki kubełków opisana przez Donalda B. Johnsona w 1981 roku zamiast tego przechowuje tylko niepuste kubełki na połączonej liście, posortowane według ich priorytetów i używa pomocniczego drzewa wyszukiwania, aby szybko znaleźć pozycję na tej połączonej liście dla każdego nowego wiadra. Potrzeba czasu $O (log log C)$ na zainicjowanie tej struktury wariantu, stały czas na znalezienie elementu o minimalnym lub maksymalnym priorytecie oraz czas $O (log log D)$ na wstawienie lub usunięcie elementu, gdzie $D$ jest różnicą między najbliższymi mniejsze i większe priorytety do priorytetu wstawionego lub usuniętego elementu.

Przykład

Rozważmy na przykład kolejkę kubełkową o czterech priorytetach, liczbach 0, 1, 2 i 3. Składa się ona z tablicy, której każda z czterech komórek zawiera zbiór elementów, początkowo pusty. Na potrzeby tego przykładu można zapisać jako sekwencję czterech zbiorów w nawiasach: . Rozważmy sekwencję operacji, w którym wkładka z dwóch elementów , a z tego samego pierwszeństwa 1 włożeniu trzeci element z priorytetem 3 zmiany priorytetu do 3, a następnie wykonać dwie ekstrakcje elementu minimalna priorytecie. ${\ Displaystyle A}$ ${\ Displaystyle A}$ $A=[\pustyzestaw,\pustyzestaw,\pustyzestaw,\pustyzestaw]$ $x$ $y$ $z$ $x$

Po wstawieniu z priorytetem 1, . $x$ $A=[\pustyzestaw,\{x\},\pustyzestaw,\pustyzestaw]$
Po wstawieniu z priorytetem 1, . $y$ $A=[\pusty zestaw,\{x,y\},\pusty zestaw,\pusty zestaw]$
Po wstawieniu z o priorytecie 3, . $A=[\pusty zestaw,\{x,y\},\pusty zestaw,\{z\}]$
Zmiana priorytetu x z 1 na trzy polega na usunięciu go z i dodaniu do , po czym . ${\ Displaystyle A [1]}$ ${\ Displaystyle A [3]}$ $A=[\pusty zestaw,\{y\},\pusty zestaw,\{x,z\}]$
Wyodrębnienie elementu o minimalnym priorytecie, w podstawowej wersji kolejki kubełkowej, od początku szuka pierwszego niepustego elementu: is empty ale , niepusty zestaw. Wybiera dowolny element tego zestawu (jedyny element, ) jako element o minimalnym priorytecie. Usuwanie z konstrukcji liści . ${\ Displaystyle A}$ $A[0]$ ${\ Displaystyle A [1] = \ {y \}}$ $y$ $y$ $A=[\pustyzestaw,\pustyzestaw,\pustyzestaw,\{x,z\}]$
Druga operacja wyodrębniania, w podstawowej wersji kolejki kubełkowej, przeszukuje ponownie od początku tablicy: , , , niepuste. W ulepszonych wariantach kolejki kubełkowej to wyszukiwanie rozpoczyna się od ostatniej pozycji, która okazała się niepusta, . W obu przypadkach okazuje się, że jest to pierwszy niepusty zestaw. Jeden z jego elementów jest wybierany arbitralnie jako element o minimalnym priorytecie; na przykład może być wybrany. Ten element jest usuwany, pozostawiając . $A[0]=\pusty zestaw$ $A[1]=\pusty zestaw$ $A[2]=\pustyzestaw$ ${\ Displaystyle A [3] = {}}$ ${\ Displaystyle A [1]}$ ${\ Displaystyle A [3] = \ {x, z \}}$ $z$ $A=[\pustyzestaw,\pustyzestaw,\pustyzestaw,\{x\}]$

Aplikacje

Degeneracja wykresu

Kolejka łyżka może być stosowane w celu utrzymania wierzchołki wydane nieukierunkowane wykresie , priorytecie ich stopni i wielokrotnie znajdowanie i usunięcie wierzchołka minimalnym stopniu. Ten zachłanny algorytm może być użyty do obliczenia degeneracji danego grafu, równej największemu stopniowi dowolnego wierzchołka w momencie jego usunięcia. Algorytm przyjmuje czas liniowy , z optymalizacją lub bez, która utrzymuje dolną granicę minimalnego priorytetu, ponieważ każdy wierzchołek znajduje się w czasie proporcjonalnym do jego stopnia, a suma wszystkich stopni wierzchołków jest liniowa względem liczby krawędzi wykresu.

Algorytm wybierania dla najkrótszych ścieżek

W algorytmie Dijkstry dla najkrótszych ścieżek w grafach skierowanych z wagami krawędzi, które są dodatnimi liczbami całkowitymi, priorytety są monotoniczne, a kolejka wiadra monotonicznego może być użyta do uzyskania ograniczenia czasowego $O (m + dc)$ , gdzie $m$ jest liczbą krawędzi , $d$ to średnica sieci, a $c$ to maksymalny (całkowity) koszt łącza. Ten wariant algorytmu Dijkstry jest również znany jako algorytm Diala , od Roberta B. Diala, który opublikował go w 1969 roku. Ten sam pomysł działa również, używając skwantyzowanej kolejki kubełkowej, dla grafów z dodatnimi rzeczywistymi wagami krawędzi, gdy stosunek maksimum do minimalna waga wynosi co najwyżej $c$ . W tej skwantyzowanej wersji algorytmu wierzchołki są przetwarzane niewłaściwie w porównaniu z wynikiem z nieskwantowaną kolejką priorytetową, ale nadal znajdują się prawidłowe najkrótsze ścieżki. W tych algorytmach priorytety będą obejmowały tylko zakres szerokości $c + 1$ , więc optymalizacja modułowa może zostać wykorzystana do zmniejszenia przestrzeni do $O (n + c)$ .

Wariant tego samego algorytmu może być użyty dla problemu najszerszej ścieżki . W połączeniu z metodami szybkiego dzielenia niecałkowitych wag krawędzi na podzbiory, którym można przypisać priorytety liczb całkowitych, prowadzi to do niemal liniowych rozwiązań dla wersji z jednym źródłem i jednym miejscem docelowym najszerszego problemu ścieżki.

Chciwy zestaw okładki

Problemem zestaw osłona ma za wejście do rodziny zbiorów . Dane wyjściowe powinny być podrodziną tych zbiorów, z taką samą sumą jak oryginalna rodzina, obejmująca możliwie jak najmniej zbiorów. Jest NP-trudny , ale ma zachłanny algorytm aproksymacji, który osiąga logarytmiczny stosunek aproksymacji, zasadniczo najlepszy z możliwych, chyba że P = NP . Ten algorytm aproksymacyjny wybiera swoją podrodzinę poprzez wielokrotne wybieranie zbioru, który obejmuje maksymalną możliwą liczbę pozostałych niepokrytych elementów. Standardowe ćwiczenie w projektowaniu algorytmów wymaga implementacji tego algorytmu, który zajmuje liniowy czas w rozmiarze wejściowym, który jest sumą rozmiarów wszystkich zestawów wejściowych.

Można to rozwiązać za pomocą kolejki kubełkowej zestawów w rodzinie wejściowej, uszeregowanych według liczby pozostałych elementów, które obejmują. Za każdym razem, gdy algorytm zachłanny wybiera zbiór jako część swoich wyników, nowo objęte elementy zbioru powinny być odejmowane od priorytetów innych zbiorów, które je pokrywają; w trakcie działania algorytmu liczba tych zmian priorytetów jest tylko sumą rozmiarów zbiorów wejściowych. Priorytety są monotonicznie malejącymi liczbami całkowitymi, ograniczonymi od góry przez liczbę elementów do pokrycia. Każdy wybór algorytmu zachłannego polega na znalezieniu zestawu o maksymalnym priorytecie, co można zrobić, skanując w dół kubełki kolejki kubełkowej, zaczynając od ostatniej poprzedniej maksymalnej wartości. Całkowity czas jest liniowy w rozmiarze wejściowym.

Planowanie

Kolejki Bucket mogą służyć do planowania zadań z terminami, np. w przesyłaniu pakietów dla danych internetowych z gwarancją jakości usługi . W przypadku tego zastosowania terminy powinny być skwantyfikowane w dyskretnych przedziałach, a zadania, których terminy przypadają w tym samym przedziale, są uważane za równorzędne.

Odmiana skwantyzowanej struktury danych kolejki kubełkowej, kolejka kalendarza , została zastosowana do planowania symulacji zdarzeń dyskretnych , w której elementy w kolejce są przyszłymi zdarzeniami z priorytetami według czasu w symulacji, w którym zdarzenia powinny się wydarzyć. W tej aplikacji kolejność zdarzeń jest krytyczna, więc priorytety nie mogą być aproksymowane. Dlatego kolejka kalendarza przeszukuje element o minimalnym priorytecie w inny sposób niż kolejka kubełkowa: w kolejce kubełkowej może zostać zwrócony dowolny element pierwszego niepustego kubełka, ale zamiast tego kolejka kalendarza przeszukuje wszystkie elementy w z tego wiadra, aby określić, który z nich ma najmniejszy nieskwantowany priorytet. Aby te wyszukiwania były szybkie, ta odmiana próbuje utrzymać liczbę wiader proporcjonalną do liczby elementów, dostosowując skalę kwantyzacji i odbudowując strukturę danych, gdy wyjdzie z równowagi. Kolejki kalendarza mogą być wolniejsze niż kolejki kubełkowe w najgorszym przypadku (gdy wiele elementów ląduje w tym samym najmniejszym kubełku), ale są szybkie, gdy elementy są równomiernie rozłożone między kubełkami, powodując, że średni rozmiar kubełka jest stały.

Szybki marsz

W stosowanych matematycznych i metod numerycznych, na rozwiązanie równań różniczkowych , niechlujny kolejek priorytetowych zostały wykorzystane do nadania priorytetów etapów szybkiego sposobu marszu na rozwiązanie problemów brzegowych z równania Eikonal , wykorzystywane do modelowania propagacji fali . Ta metoda znajduje czasy, w których poruszająca się granica przecina zbiór dyskretnych punktów (takich jak punkty siatki liczb całkowitych) przy użyciu metody priorytetyzacji przypominającej ciągłą wersję algorytmu Dijkstry , a jej czas działania jest zdominowany przez kolejkę priorytetów tych punktów. Można go przyspieszyć do czasu liniowego, zaokrąglając priorytety używane w tym algorytmie do liczb całkowitych i używając kolejki kubełkowej dla tych liczb całkowitych. Podobnie jak w algorytmach Dijkstry i Dial, priorytety są monotoniczne, więc szybki marsz może wykorzystywać monotonną optymalizację kolejki kubełkowej i jej analizę. Dyskretyzacja wprowadza jednak pewien błąd w otrzymanych obliczeniach.

Zobacz też

Miękka sterta , inny sposób na przyspieszenie kolejek priorytetowych za pomocą przybliżonych priorytetów

Languages

In other projects