Algorytm znajdowania maksymalnej sumy w sekwencji nakładających się interwałów

Problem, który próbuję rozwiązać ma listę interwałów w linii liczb, każdy z predefiniowanym wynikiem. Muszę zwrócić maksymalną możliwą liczbę punktów.

Haczyk polega na tym, że interwały nakładają się na siebie, a z nakładających się interwałów mogę użyć tylko jednego. Oto przykład. 

Intervals   - Score  
   0- 5     -  15  
   4- 9     -  18  
  10-15     -  12  
   8-21     -  19  
  25-30     -  25

Tutaj, interwały 0-5, 4-9 i 8-21 nakładają się.
Odstępy 10-15 i 8-21 również pokrywają się.
Maksymalna suma wynosiłaby 55 (18+12+25).

Należy tutaj zauważyć, że wybieramy interwał 4-9 z pierwszej partii nakładających się interwałów, mimo że nie ma on najwyższego wyniku z trzech.

Dzieje się tak dlatego, że wybranie przedziału 8-21 uniemożliwiłoby nam użycie przedziału 10-15 w późniejszym czasie, zmniejszając w ten sposób sumę całkowitą (w takim przypadku całkowita suma wynosiłaby 19+25=44).

Szukam rozwiązania O (nlogn) lub O (n) tego problemu. Myślę, że można używać programowania dynamicznego, ale mogę się mylić. Czy ktoś mógłby zasugerować rozwiązanie / algorytm(y), które może zrobić sztuczkę tutaj?

Edit: interwały nie są w określonej kolejności.

Author: Bakuriu, 2010-07-14
Source

6 answers

Jest to ważona zmienność harmonogramu interwałowego ; można go rozwiązać w O(N log N) z programowania dynamicznego .

Niech przedział będzie g(start, stop, score) i niech będą sortowane według stop. Dla uproszczenia, Załóżmy na razie, że wszystko stop jest unikalne.

Niech best[i] będzie najlepszym wynikiem, jaki możemy uzyskać, kiedy możemy użyć g[1], ..., g[i]. Nie musimy oczywiście używać ich wszystkich i ogólnie nie możemy, ponieważ podzbiór interwałów, których używamy, musi być nie nakładające się na siebie.

  • wyraźnie best[0] = 0. Oznacza to, że ponieważ nie możemy użyć żadnego interwału, najlepszy wynik jaki możemy uzyskać to 0.
  • dla dowolnego 1 <= k <= N mamy:
    • best[k] = max( best[k-1], best[j] + g[k].score ), gdzie
      • j jest największym indeksem takim, że g[j].stop < g[k].start (j może być zero)

To znaczy, biorąc pod uwagę, że możemy używać g[1], ... g[k], najlepsze, co możemy zrobić, to lepsza ocena tych dwóch opcji:

  • nie uwzględniamy g[k]. Tak więc wynik tego opcja to best[k-1].
    • ... ponieważ to najlepsze co możemy zrobić z g[1], ... g[k-1]
  • włączamy g[k], a po jego lewej stronie robimy wszystko, co w naszej mocy, ze wszystkimi genami, które nie pokrywają się z g[k], tj. wszystkie g[1], ..., g[j], gdzie g[j].stop < g[k].start i j są jak największe. Tak więc wynik tej opcji wynosi best[j] + g[k].score.

(zwróć uwagę na optymalną podbudowę i nakładające się na siebie podproblemy programowania dynamicznego zawarte w powyższym równaniu).

Ogólnie odpowiedź na to pytanie brzmi best[N], czyli najlepszy wynik, jaki możemy uzyskać, kiedy możemy wykorzystać wszystkie geny. UPS, powiedziałem geny? Chodzi mi o interwały.

To jest O(N log N) ponieważ:

  • sortowanie wszystkich interwałów trwa O(N log N)
  • znalezienie j dla każdego k jest {[27] } za pomocą wyszukiwania binarnego

Jeśli kilka genów może mieć te same wartości stop, to nic się nie zmieniło: nadal musisz szukać najbardziej prawego j. W np. Pythonie jest to łatwe z bisect_right. W Javie, gdzie wyszukiwanie binarne w bibliotece standardowej nie gwarantuje, który indeks zostanie zwrócony w przypadku powiązania, można (wśród wielu opcji) śledzić go za pomocą wyszukiwania liniowego (dla O(N) najgorszego przypadku) lub innej serii wyszukiwania binarnego, aby znaleźć odpowiedni indeks najbardziej.

UPS znowu powiedziałem geny? Chodzi mi o interwały.

Podobne pytania

 23
Author: polygenelubricants,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 12:31:55

Po pierwsze, myślę, że maksimum to 59, a nie 55. Jeśli wybierzesz interwały [0-5], [8-21] i [25,30], otrzymasz 15+19+25=59. Możesz użyć jakiegoś dynamicznego programowania, aby sobie z tym poradzić.

Najpierw posortujesz wszystkie interwały według ich punktu początkowego, a następnie powtarzasz od końca do początku. Dla każdego elementu na liście, wybierasz maksymalną sumę od tego punktu do ostatniego jako max(S[i]+S[j], S[i+1]), gdzie i jest pozycją, na której się znajdujesz, j jest pozycją, która jest pierwszym nie nakładającym się wpisem po twoim elemencie (czyli, pierwszy element, którego początek jest większy od końca bieżącego elementu). Aby przyspieszyć algorytm, należy zapisać maksymalną sumę częściową S [j] dla każdego elementu.

Aby wyjaśnić, pozwól, że rozwiążę twój przykład zgodnie z tym. Najpierw Sortuj interwały: 

 1:  0- 5 -  15
 2:  4- 9 -  18
 3:  8-21 -  19
 4: 10-15 -  12
 5: 25-30 -  25

Więc, 

 S[5] = 25
 S[4] = max(12+S[5], 25)=37
 S[3] = max(19+S[5], S[4])=max(19+25,37)=44
 S[2] = max(18+S[4], S[3])=max(18+37,44)=55
 S[1] = max(15+S[3], S[2])=max(15+44, 55)=59

Jest to adaptacja algorytmu w ten post, ale niestety, nie ma ładnego O (n) czasu pracy. Zdegenerowana lista, gdzie każdy wpis pokrywa się z następnym, spowodowałaby, że będzie O (n^2).

 4
Author: vhallac,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 12:09:32

Może można zastosować podejście podobne do Tej odpowiedzi, czyli O (n) przynajmniej dla tego problemu. Oznaczałoby to powtarzanie raz przez interwały i śledzenie tylko tych kombinacji interwałów, które nadal mogą prowadzić do optymalnego ostatecznego rozwiązania.

 0
Author: sth,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 12:17:21

Brzmi jak wariacja na temat problemu plecaka. W poszukiwaniu tych rozwiązań można znaleźć inspirację.

O ilu interwałach mówimy? Jeśli to tylko o 5 (jak w twoim przykładzie), to ' prawdopodobnie bardziej praktyczne, aby po prostu spróbować każdej kombinacji. Jeśli jest więcej, Czy wystarczy przybliżenie idealnego rozwiązania? Ponownie, rozwiązania Knapsack (takie jak chciwy algorytm aproksymacji George ' a Dantziga) mogą być dobrym miejscem do rozpoczęcia.

 0
Author: Damovisa,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-07-14 03:52:21

Pomyślałem o tym trochę i coś wymyśliłem.

Drzewa interwałowe zapewniają skuteczny sposób znajdowania wszystkich interwałów, które nakładają się na dany interwał. Przechodząc przez cały zestaw interwałów, możemy znaleźć wszystkie nakładające się interwały dla danego. Kiedy już je mamy, możemy znaleźć interwał z najwyższym wynikiem, zapisać go i przejść dalej.

Budowanie drzewa zajmuje Czas O (N Log N), A wyszukiwanie zajmuje czas O (Log N). Ponieważ robimy wyszukiwanie dla wszystkich elementów, rozwiązanie staje się O (n Log N).

Jednakże, jeśli mamy do czynienia z czymś takim jak powyższy przykład, gdzie najwyższy przedział punktacji w jednej grupie zmniejsza sumę, algorytm nie powiedzie się, ponieważ nie mamy sposobu, aby wiedzieć, że najwyższy przedział punktacji nie powinien być używany przed ręką. Oczywistym sposobem obejścia tego byłoby obliczenie obu (lub wszystkich) liczb całkowitych w przypadku, gdy nie jesteśmy pewni, ale to stawia nas z powrotem do potencjalnie O (N^2) lub gorszego rozwiązania.

 0
Author: efficiencyIsBliss,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-07-14 15:39:06

Myślę, że możemy użyć tej rekurencji...

S[i] oznacza wynik każdego interwału
Interval[i] oznacza wszystkie interwały 

ResMax[i] = max(ResMax[i-1] + S[i] //if i is included
           ,max(R[i-1],S[i]) 
         )
Nie jestem dokładnie sprawdzony, ale powinno zadziałać.
 0
Author: Jyotirmoy Sundi,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-11-23 04:50:44