Jak użyć chciwego algorytmu, aby znaleźć malejącą sekwencję najbliższą podanej?

20

Otrzymujesz n liczb całkowitych wszystkie od do . Pod każdą liczbą całkowitą należy wpisać liczbę całkowitą między a z warunkiem, że tworzą ciąg nie malejący. Zdefiniuj odchylenie takiej sekwencji na . Zaprojektuj algorytm, który znajdzie z minimalnym odchyleniem w czasie wykonywania . $a_1, \ldots, a_n$ $0$ $l$ $a_i$ $b_i$ $0$ $l$ $b_i$ $\max(|a_1-b_1|, \ldots, |a_n-b_n|)$ $b_i$ $O(n\sqrt[4]{l})$

Szczerze mówiąc, nie mam pojęcia, jak nawet zacząć rozwiązywać to pytanie. Wygląda mi to na pytanie dotyczące programowania dynamicznego, ale profesor powiedział, że należy to rozwiązać za pomocą chciwego algorytmu. Byłoby bardzo mile widziane, gdyby ktoś mógł skierować mnie w dobrym kierunku, podając małą wskazówkę.

— Aden Dong
źródło

9

Zacznijmy od następującej obserwacji:

Niech $max$ oznacza maksimum sekwencji $a_1,...,a_n$ , a niech $min$ oznacza minimum. Jeśli $a_1=max$ , Optymalne jest wybranie $b_1=b_2=...=b_n=\lfloor(max+min)/2\rfloor$ .

Dlaczego tak jest? Cóż, ponieważ sekwencja zaczyna się od maksimum, albo wybieramy $b_1$ duże i cierpimy na duże odchylenie od minimum sekwencji (ponieważ każde kolejne $b_i$ musi być większe lub równe $b_1$ ), lub wybieramy $b_1$ małe i cierpimy na odchylenie do $max$ . Średnia minimalizuje maksymalne odchylenie.

Możemy teraz spróbować uogólnić to spostrzeżenie, aby zastosować je w ogólnych sekwencjach $a_1,...,a_n$ . Na przykład, możemy podzielić dowolną sekwencję na podsekwencje, tak aby każda zaczynała się od maksimum odpowiedniej podsekwencji.

Przykład: dzieli się na , i . $(2,6,4,1,5,2,8,7,5,1)$ $(2)$ $(6,4,1,5,2)$ $(8,7,5,1)$

Biorąc pod uwagę ten podział, możemy teraz rozwiązać każdy z tych podsekwencji osobno i uzyskać przypisanie , co może jednak naruszać warunek nie malejący. Można to naprawić bez utraty optymalności. $b_i$

Zauważ, że ostatni podsekwencja zawsze zawiera maksymalne całej sekwencji (w przeciwnym razie po niej pojawiłaby się kolejna podsekwencja). Niech być przypisane wartości mamy do podciągów. Teraz, aby osiągnąć nie zmniejszanie w , zaczynamy od tyłu w i do przodu. Jeśli jest większy niż , po prostu ustawiamy . Jeśli jest mniejszy, zachowujemy go. Następnie przechodzimy do porównania z i tak dalej. Zauważ, że obniżenie dowolnego do wartości $max$ $w_1,w_2,...,w_k$ $k$ $w_1,...,w_k$ $w_k$ $w_{k-1}$ $w_k$ $w_{k-1}:=w_k$ $w_{k-2}$ $w_{k-1}$ $w_i$ $w_{i+1}$ nigdy nie zwiększa odchylenia, ponieważ wartość maksymalna w podsekwencji przypisanej za pomocą jest zawsze niższa niż maksymalna w podsekwencji przypisanej za pomocą . $w_i$ $w_{i+1}$

Myślę, że ten algorytm powinien być poprawny. Jeśli chodzi o czas wykonywania, kluczowym krokiem jest obliczenie rosnących maksimów dla podsekwencji, co jest możliwe w ? Nie jestem pewien, gdzie przyczynia się. $O(n)$ $l$

— Syzygy
źródło

2

Zamyślę tu głośno, po prostu analizując podane wskazówki. Przejdźmy do pierwotnej wskazówki, że jest tym, co powinieneś najpierw wypróbować. Mogę wymyślić chciwy algorytm, który ma ten czas. $O(nl)$

Część złożoności czasowej oznacza, że możesz przechowywać listę zliczeń każdego wystąpienia każdej wartości . To po prostu stwórz zestaw który śledzi liczbę każdego w zestawie. Możesz utworzyć listę inicjalizującą, skanując sekwencję wejściową jeden raz. $l$ $0..l$ $\text{Count} = { C_0, \ldots, C_l}$ $l$

Możesz zeskanować tę listę w aby uzyskać maksymalną i minimalną wartość. Gdyby wypełnić całą listę tym punktem środkowym, wariancja byłaby po prostu różnicą od tej wartości i maksimum / min. To jest w zasadzie twój najgorszy scenariusz, nazwijmy to . $O(l)$ $b$ $b_w$

Więc swoją drogą do od lewej. Możesz zarówno upuścić ten element z i uzyskać min / max w . Teraz możemy być chciwi. Nie wybieramy ponieważ wymusza to wzrost całej pozostałej listy (aby spełnić wymagania nie malejące), a tym samym zwiększa wariancję. Minimalną wartością, jaką możemy wybrać, jest . Jeśli znajduje się w dopuszczalnym zakresie, wybieramy go, jeśli poniżej zakresu, należy użyć minimum. Minimalizuje to wariancję w punkcie przy znanych znanych ograniczeniach. $b_i$ $\text{Count}$ $b[i+1] \ldots b[n]$ $O(l)$ $b_i > b_w$ $b[i-1]$ $a_i$ $b_i$

To tylko pomysł, być może mam szczęście i wskazuje ci właściwy kierunek. Ten algorytm może nie działać (działa w moich kilku prostych testach), ale pasuje do podanych wskazówek, więc być może jest pomocny. Jeśli jest poprawne, łatwo zauważyć, że część z pewnością można upuścić do , a co więcej, nie jestem pewien. $O(l)$ $O(\log l)$

— edA-qa mort-ora-y
źródło

2

Oto rozwiązanie profesora, które nazywa „redukcją”: Dla każdego od do , spróbuj zbudować rozwiązanie, jeśli wiemy, że odchylenie jest mniejsze lub równe . Pierwszym dla którego można znaleźć rozwiązanie, jest minimalne odchylenie. Możemy znaleźć rozwiązanie, biorąc pod uwagę odchylenie w czasie . Czas działania to . Następnie zamiast wyszukiwania liniowego możemy użyć wyszukiwania binarnego, aby określić najmniejsze odchylenie, dla którego możliwe jest rozwiązanie. Skraca to czas działania do , co spełnia wymaganie . $i$ $0$ $l$ $i$ $i$ $O(n)$ $O(nl)$ $O(n\log l)$ $O(n\sqrt[4]{l})$

— Aden Dong
źródło

4

Więc było podstępem ... Ale bardziej intryguje mnie „Możemy znaleźć rozwiązanie, biorąc pod uwagę odchylenie w czasie O (n)” .. jak to nie jest interesująca część?

O (n \sqrt[4]{l})

$O(n\sqrt[4]{l})$

— jmad

@jmad Zważywszy dla każdego , wziąć jak najniższej wartości, która jest co najmniej tak duży jak wszystkich poprzednich , i który ma więcej niż z dala od . Jeśli nie możemy znaleźć takiej wartości, co to oznacza? Oznacza to, że poprzedni jest większy niż większy niż . Tak więc poprzednie jest o ponad większe niż . Więc ta wartość „ nie była możliwa. Jeśli przejdziesz przez wartości bez utknięcia w ten sposób, znalazłeś rozwiązanie dla

i

$i$

j

$j$

b_{j}

$b_j$

b_{k}

$b_k$

i

$i$

a_{j}

$a_j$

b_{t}

$b_t$

i

$i$

a_{j}

$a_j$

a_{t}

$a_t$

2 i

$2i$

a_{j}

$a_j$

i

$i$

n

$n$

i

$i$ bez cofania się, w czasie .

O (n)

$O(n)$

— jwg

O (n log l) stanowiłoby silną wskazówkę, że musisz przeprowadzić wyszukiwanie binarne w zakresie od 0 do l.

— gnasher729

0

Myślę, że powinno to być wykonalne w O (n).

Podejmij podobny problem: Biorąc pod uwagę , 1 ≤ i ≤ n oraz d ≥ 0, znajdź w kolejności malejącej, tak że dla wszystkich i lub pokaż, że nie jest to możliwe. Można to zrobić w O (n), a przy użyciu wyszukiwania binarnego oryginalny problem rozwiązuje się w O (n log l). $a_i$ $b_i$ $|a_i - b_i| ≤ d$

Teraz, jeśli są i ≤ j takie, że a_i - a_j> 2d, to nie ma rozwiązania (ponieważ ). $b_i ≥ a_i - d, b_j ≤ a_j + d < a_i - 2d + d = a_i - d ≤ b_i$

Ale jeśli a_i - a_j ≤ 2d dla wszystkich i ≤ j, to myślę, że zawsze znajdzie się rozwiązanie. Więc wszystko, co musimy zrobić, to znaleźć m = max (a_i - a_j) dla wszystkich i ≤ j, i wybrać d = floor ((m + 1) / 2). To maksimum można znaleźć w O (n).

— gnasher729
źródło

Intrygujący pomysł! Mogę wierzyć, że coś takiego może działać, ale wygląda na to, że na końcu twojej odpowiedzi jest duża luka i trudno mi podać szczegóły. Czy masz dowód, że jeśli dla wszystkich to rozwiązanie zawsze istnieje? Co ważniejsze, jak to znaleźć? Oryginalne pytanie mówi, że musimy znaleźć . Nawet jeśli założymy, że istnieje rozwiązanie, trudno mi znaleźć sposób na znalezienie odpowiednich . Czy możesz to rozwinąć?

a_{i} - a_{j} \leq 2 d

$a_i - a_j \le 2d$

i \leq j

$i\le j$

b_{i}

$b_i$

b_{i}

$b_i$

— DW