Wydajne algorytmy dla problemu widoczności pionowej

Myśląc o jednym problemie, zdałem sobie sprawę, że muszę stworzyć wydajny algorytm rozwiązujący następujące zadanie:

Problem: otrzymujemy dwuwymiarowe kwadratowe pudełko o boku $n$ którego boki są równoległe do osi. Możemy spojrzeć na to z góry. Istnieją jednak również $m$ segmenty poziome. Każdy segment ma całkowitą współrzędną $y$ ( $0 \le y \le n$ ) i współrzędne $x$ ( $0 \le x_1 < x_2 \le n$ ) i łączy punkty $(x_1,y)$ i $(x_2,y)$ (spójrz na zdjęcie poniżej).

Chcielibyśmy wiedzieć, dla każdego segmentu jednostki na górze pudełka, jak głęboko możemy spojrzeć w środku w pionie, jeśli przejrzymy ten segment.

$x \in \{0,\dots,n-1\}$ $\max_{i:\ [x,x+1]\subseteq[x_{1,i},x_{2,i}]} y_i$

Przykład: biorąc pod uwagę i segmentów zlokalizowanych jak na poniższym obrazku, wynikiem jest . Zobacz, jak głębokie światło może dostać się do pudełka. $n=9$ $m=7$ $(5, 5, 5, 3, 8, 3, 7, 8, 7)$

Siedem segmentów; część zacieniowana wskazuje obszar, do którego można dotrzeć światłem

Na szczęście dla nas zarówno , jak i są dość małe i możemy wykonywać obliczenia offline. $n$ $m$

Najłatwiejszym algorytmem rozwiązującym ten problem jest brute-force: dla każdego segmentu przejdź przez całą tablicę i zaktualizuj ją w razie potrzeby. Daje nam jednak niezbyt imponujące . $O(mn)$

Dużym ulepszeniem jest użycie drzewa segmentów, które jest w stanie zmaksymalizować wartości segmentu podczas zapytania i odczytać wartości końcowe. Nie będę tego dalej opisywał, ale widzimy, że złożoność czasu wynosi . $O((m+n) \log n)$

Wymyśliłem jednak szybszy algorytm:

Zarys:

Posortuj segmenty w malejącej kolejności współrzędnej (czas liniowy przy użyciu odmiany sortowania zliczającego). Teraz pamiętać, że jeśli szerokości jednostek, niskoprofilowy segment został objęty żadnym segmencie przed, nie po segment może związany wiązki światła przechodzącego przez ten szerokości jednostek, niskoprofilowy segmencie już. Następnie zrobimy przeciągnięcie linii od góry do dołu pudełka. $y$ $x$ $x$
Teraz wprowadzimy kilka definicji: -jednostka segmentowa jest urojonym poziomym segmentem na przemiataniu, którego współrzędnymi są liczby całkowite i których długość wynosi 1. Każdy segment podczas procesu zamiatania może być albo nieoznaczony (to znaczy wiązka światła wychodząca z góra pudełka może dosięgnąć tego segmentu) lub oznaczona (odwrotna wielkość liter). Rozważ segment unit z , zawsze niezaznaczone. również zestawy . Każdy zestaw będzie zawierał całą sekwencję następujących po sobie segmentów jednostek (jeśli istnieją) z następującymi nieoznaczonymi $x$ $x$ $x$ $x_1=n$ $x_2=n+1$ $S_0=\{0\}, S_1=\{1\}, \dots, S_n=\{n\}$ $x$ człon.
Potrzebujemy struktury danych, która byłaby w stanie działać skutecznie na tych segmentach i zestawach. Użyjemy struktury find-union rozszerzonej o pole zawierające maksymalny indeks segmentu -jednostek (indeks segmentu nieoznaczonego ). $x$
Teraz możemy efektywnie obsługiwać segmenty. Powiedzmy, że rozważamy teraz ty segment w kolejności (nazwij go „zapytaniem”), który zaczyna się od a kończy na . Musimy znaleźć wszystkie nieoznakowane segmenty unit, które są zawarte w segmencie (są to dokładnie te segmenty, na których wiązka światła kończy swoją drogę). Wykonamy następujące czynności: po pierwsze, znajdziemy pierwszy nieoznaczony segment w zapytaniu ( Znajdź reprezentanta zestawu, w którym znajduje się i uzyskaj maksymalny indeks tego zestawu, który z definicji jest segmentem nieoznaczonym ). Następnie ten indeks $i$ $x_1$ $x_2$ $x$ $i$ $x_1$ $x$ znajduje się w zapytaniu, dodaj go do wyniku (wynikiem dla tego segmentu jest ) i zaznacz ten indeks ( zestawy Unii zawierające i ). Następnie powtarzaj tę procedurę, aż znajdziemy wszystkie nieoznakowane segmenty, czyli następne zapytanie Find daje nam indeks . $y$ $x$ $x+1$ $x \ge x_2$

Zauważ, że każda operacja szukania unii zostanie wykonana tylko w dwóch przypadkach: albo zaczniemy rozważać segment (co może się zdarzyć razy), albo właśnie oznaczyliśmy segment jednostki (może się to zdarzyć razy). Zatem ogólna złożoność wynosi ( jest odwrotną funkcją Ackermanna ). Jeśli coś nie jest jasne, mogę rozwinąć więcej na ten temat. Może będę mógł dodać trochę zdjęć, jeśli będę miał trochę czasu. $m$ $x$ $n$ $O((n+m)\alpha(n))$ $\alpha$

Teraz dotarłem do „ściany”. Nie mogę wymyślić algorytmu liniowego, choć wydaje się, że powinien istnieć jeden. Mam więc dwa pytania:

Czy istnieje algorytm czasu liniowego (to znaczy ) rozwiązujący problem widoczności segmentu poziomego? $O(n+m)$
Jeśli nie, to jaki jest dowód na to, że problemem z widocznością jest ? $\omega(n+m)$

— mnbvmar
źródło

Jak szybko sortujesz swoje m segmenty?

— babou

@babou, pytanie określa sortowanie zliczające, które, jak mówi pytanie, biegnie w czasie liniowym („czas liniowy z zastosowaniem wariantu sortowania zliczającego”).

— DW

Czy próbowałeś zamiatać od lewej do prawej? Wystarczy posortować na

zarówno w krokach

aby przejść w prawo. Tak więc w sumie

x 1

$x1$

x 2

$x2$

O (m)

$O(m)$

O (m)

$O(m)$

O (m)

$O(m)$

— invalid_id

@invalid_id Tak, próbowałem. Jednak w tym przypadku linia przeciągnięcia musi odpowiednio zareagować, gdy spotka się z początkiem odcinka (innymi słowy, dodaj liczbę równą współrzędnej

segmentu do multisetu), dotrze do końca odcinka (usuń występowanie

-coordinate) i wyprowadza najwyższy aktywny segment (maksymalna wartość wyjściowa w multiset). Nie słyszałem o żadnych strukturach danych pozwalających nam to robić w (zamortyzowanym) stałym czasie.

y

$y$

y

$y$

— mnbvmar

@mnbvmar może głupia sugestia, ale co z tablicą o rozmiarze

, zamiatasz i zatrzymujesz każdą komórkę

. Dla każdej komórki znasz max

i możesz wprowadzić ją do macierzy, a ponadto możesz śledzić ogólne maksimum za pomocą zmiennej.

n

$n$

O (n)

$O(n)$

y

$y$

— invalid_id

Odpowiedzi:

Sortuj zarówno oraz współrzędne linii w dwóch oddzielnych macierzy i . $x1$ $x2$ $A$ $B$ $O(m)$
Utrzymujemy również pomocniczy rozmiar tablicy bitów aby śledzić aktywne segmenty. $n$
Zacznij zamiatać od lewej do prawej:
dla $(i=0,i<n,i++)$
{
..if w połączeniu z wartość $\exists x1=i$ $y$ $c$ $O(1)$
.. {
.... znajdź ( ) $\max$
.... sklep ( ) $\max$ $O(1)$
..}
..if w połączeniu z wartość $\exists x2=i$ $y$ $c$ $O(1)$
.. {
.... znajdź ( ) $\max$
.... sklep ( ) $\max$ $O(1)$
..}
}

find ( ) może być zaimplementowany przy użyciu tablicy bitów z bitami. Teraz za każdym razem, gdy usuwamy lub dodajemy element do , możemy zaktualizować tę liczbę całkowitą, ustawiając odpowiednio wartość true lub false. Teraz masz dwie opcje w zależności od użytego języka programowania, a założenie, że jest względnie małe, tj. Mniejsze niż czyli co najmniej 64 bity lub stała liczba tych liczb całkowitych: $\max$ $n$ $L$ $n$ $long long int$

Uzyskaj najmniej znaczący bit w stałym czasie jest obsługiwany przez niektóre urządzenia i gcc.
Konwertując na liczbę całkowitą , otrzymasz maksimum (nie bezpośrednio, ale możesz je uzyskać). $L$ $O(1)$

Wiem, że to dość hack, ponieważ zakłada maksymalną wartość dla a zatem może być postrzegane jako stała wtedy ... $n$ $n$

— nieważny numer identyfikacyjny
źródło

Jak widzę, zakładając, że masz 64-bitowy procesor x86, jesteś w stanie obsłużyć tylko

. Co jeśli

jest rzędu milionów?

n \leq 64

$n \le 64$

n

$n$

— mnbvmar

Wtedy będziesz potrzebować więcej liczb całkowitych. Dzięki dwóm liczbom całkowitym możesz obsłużyć od

do 128 itd. Zatem maksymalny krok znajdowania

jest ukryty w wymaganej liczbie liczb całkowitych, którą nadal możesz zoptymalizować, jeśli

jest małe. Wspomniałeś w swoim pytaniu, że

jest względnie małe, więc przypuszczam, że nie jest rzędu milionów. Nawiasem mówiąc, długie long int zawsze z definicji wynosi co najmniej 64 bity, nawet na procesorze 32-bitowym.

n

$n$

O (m)

$O(m)$

m

$m$

n

$n$

— invalid_id

Oczywiście to prawda, standard C ++ definiuje long long intjako co najmniej 64-bitową liczbę całkowitą. Jednak czy nie jest tak, że jeśli

jest duże, a rozmiar słowa oznaczamy jako

(zwykle

), to każde przyjmie

n

$n$

w

$w$

w = 64

$w=64$ find

czas? Wtedy otrzymalibyśmy całkowite

O (\frac{n}{w})

$O\left(\frac{n}{w}\right)$

O (\frac{m n}{w})

$O\left(\frac{mn}{w}\right)$

— mnbvmar

Tak, niestety w przypadku dużych wartości

tak jest. Więc teraz zastanawiam się, jak duże

będzie w Twoim przypadku i czy jest ona ograniczona. Jeśli rzeczywiście jest rzędu milionów, hacking dookoła nie będzie już działał, ale jeśli

dla niskich wartości

będzie szybki i praktycznie

. Zatem najlepszy wybór algorytmu zależy, jak zwykle, od danych wejściowych. Na przykład dla

sortowanie jest zwykle szybsze niż sortowanie scalone, nawet przy czasie działania

porównaniu do

n

$n$

n

$n$

c \cdot w \geq n

$c\cdot w\geq n$

c

$c$

O (n + m)

$O(n+m)$

n \leq 100

$n\leq 100$

O (n^{2})

$O(n^2)$

O (n \log n)

$O(n \log n)$

— invalid_id

Jestem zdezorientowany twoim wyborem formatowania. Wiesz, że możesz tutaj wpisać kod, prawda?

— Raphael

Nie mam algorytmu liniowego, ale ten wydaje się być O (m log m).

Sortuj segmenty na podstawie pierwszej współrzędnej i wysokości. Oznacza to, że (x1, l1) zawsze występuje przed (x2, l2) zawsze, gdy x1 <x2. Również (x1, l1) na wysokości y1 występuje przed (x1, l2) na wysokości y2 za każdym razem, gdy y1> y2.

Dla każdego podzestawu o tej samej pierwszej współrzędnej wykonujemy następujące czynności. Niech pierwszy segment będzie (x1, L). Dla wszystkich pozostałych segmentów podzbioru: Jeśli segment jest dłuższy niż pierwszy, zmień go z (x1, xt) na (L, xt) i dodaj go do podzestawu L w odpowiedniej kolejności. W przeciwnym razie upuść. Wreszcie, jeśli następny podzbiór ma pierwszą współrzędną mniejszą niż L, wówczas podziel (x1, L) na (x1, x2) i (x2, L). Dodaj (x2, L) do następnego podzbioru we właściwej kolejności. Możemy to zrobić, ponieważ pierwszy segment w podzbiorze jest wyższy i obejmuje zakres od (x1, L). Ten nowy segment może być tym, który obejmuje (L, x2), ale nie będziemy tego wiedzieć, dopóki nie spojrzymy na podzbiór, który ma pierwszą współrzędną L.

Po przejściu przez wszystkie podzbiory będziemy mieli zestaw segmentów, które się nie nakładają. Aby ustalić, jaka jest wartość Y dla danego X, musimy tylko przejść przez pozostałe segmenty.

Na czym więc polega złożoność: Sortowanie to O (m log m). Pętla przez podzbiory to O (m). Wyszukiwanie to także O (m).

Wydaje się więc, że ten algorytm jest niezależny od n.

— Nikt w szczególności
źródło