Minimalna skumulowana suma zestawu

Rozważ ten problem: biorąc pod uwagę listę zbiorów skończonych, znajdź porządek który minimalizuje .$s_1, s_2, s_3, \ldots$$|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| + \ldots$

Czy istnieją na to znane algorytmy? Jaka jest jego złożoność? Nie byłem jeszcze w stanie wymyślić wydajnego optymalnego algorytmu, ale nie jest to oczywiście w NP-Hard.

Ten problem jest faktycznie związany z problemem planowania, znanym jako „Planowanie z ograniczeniem pierwszeństwa w celu zminimalizowania ważonego czasu zakończenia”. Problem jest następujący: Biorąc pod uwagę zestaw zadań, gdzie każde zadanie ma czas przetwarzania (p) i wagę (w), a wykres zadań jest zdefiniowany w zadaniach. Celem jest zaplanowanie zadań na pojedynczej maszynie (nie zapobiegawczych), tak aby ograniczenia pierwszeństwa zostały spełnione, a suma ważonego czasu ukończenia została zminimalizowana. Problem jest trudny dla NP i znane jest przybliżenie 2.

Redukcja z problemu minimalnej sumy łącznej do problemu planowania z ograniczeniami pierwszeństwa: Dla każdego elementu utwórz zadanie z p = 1, w = 0. Również dla każdego zestawu utwórz zadanie z p = 0, w = 1. Utwórz wykres pierwszeństwa, taki że jeśli element , a następnie e muszą być zaplanowane przed S . Myślę, że ten szczególny przypadek problemu z planowaniem jest również trudny do NP.$e \in S$$e$$S$

Zobacz poniższe linki,

1) http://www.win.tue.nl/~gwoegi/papers/precsum.pdf

2) http://web.engr.illinois.edu/~chekuri/papers/dam_sched.ps

Shalmoli Gupta wyjaśnił już, że ogólny problem to NP-Hard, więc postanowiłem sprawdzić, czy jakieś specjalne przypadki można rozwiązać wielomianowo. W końcu znalazłem rozwiązanie dla specjalnego przypadku zbiorów, które reprezentują drzewo, lub bardziej ogólnie, szereg równoległego rzędu przez włączenie podzbioru ze wszystkimi rozłącznymi zestawami nieporównywalnymi.

Jedną właściwością, która ułatwia rzeczy, jest to, że lista zestawów jest zamknięta pod przecięciem. Jeśli , a następnie, istnieje optymalna kolejność, w której s 1 jest przed s 2 . Możemy założyć WLOG, że optymalne uporządkowanie jest liniowym rozszerzeniem zamówienia częściowego podanego przez włączenie podzbioru.$s_1 \subseteq s_2$$s_1$$s_2$

Ponieważ wszystkie podzestawy zestawu pojawiają się przed nim w kolejności, oznacza to, że kwota dodana do sumy bieżącej przez dany zestaw jest stała, niezależnie od tego, gdzie się pojawi. Jeśli lista zestawów, to dodatkowy koszt zestawu jest liczba elementów w S, które nie znajdują się w jednej podgrupie S, który pojawia się w S . Jeśli ten sam zestaw pojawia się wiele razy w S , możemy arbitralnie wybrać jeden, aby przejść pierwszy i pozwolić innym kosztować 0.$S$$S$$S$

Oznacza to, że problem jest równoważny problemowi minimalnego ważonego czasu ukończenia przy planowaniu pojedynczej maszyny z ograniczeniami pierwszeństwa. W tym problem, biorąc pod uwagę zbiór zadań z ciężarkami i czasu t j oraz częściowego porządku na zadania P , chcemy znaleźć uporządkowanie zadań, które minimalizuje ważonej całkowity czas zakończenia, tj$w_j$$t_j$$P$

$\sum_{i=1}^{n} w_{j_i} \left(\sum_{k=1}^{i} t_{j_k}\right)$

z zastrzeżeniem ograniczeń pierwszeństwa . Problem skumulowanego minimalnego zestawu z zamkniętymi zestawami przecięcia można w to przekształcić, tworząc zadanie dla każdego zestawu, w którym każde zadanie ma wagę 1, czas równy kosztowi przyrostowemu zdefiniowanemu powyżej, a P jest kolejnością nadaną przez włączenie podzbioru.$P$$P$

Jak się okazuje, problem ten jest NP-trudny do ogólnego , jak również. Jednak niektóre specjalne formy P można rozwiązać w czasie wielomianowym.$P$$P$

W pracy przedstawiono algorytm dla przypadku szeregów równoległych szeregowych P (który obejmuje również ważny przypadek drzew). Niestety nie mogłem uzyskać dostępu do tego papieru, więc postanowiłem spróbować go opracować niezależnie. Oto co wymyśliłem.$O(nlogn)$$P$

Aby rozwiązać ten problem, potrzeba kilku obserwacji.

Po pierwsze, przy braku jakichkolwiek ograniczeń pierwszeństwa, optymalnym rozwiązaniem jest po prostu sortowanie zadań w celu zwiększenia . Dla uproszczenia będę odnosił się do tego jako wartości zadania, w skróciev(j). Zauważ, że ponieważ sortowanie toO(nlogn), nie da się lepiej niż ta złożoność.$\frac{t_j}{w_j}$$v(j)$$O(nlogn)$

Reguła 1 Niech i b będą zadaniami takimi, że a < b ∈ P i b obejmują a. Jeśli v ( a ) < v ( b ) , wówczas możemy usunąć ograniczenie a < b bez wpływu na optymalną kolejność lub wartość obiektywną.$a$$b$$a < b \in P$$v(a) < v(b)$$a < b$

Załóżmy, że pojawia się przed a w optymalnej kolejności odprężonego problemu. Ponieważ b obejmował pierwotnie, oznacza to, że wszystkie zadania między b i a w nowym porządku są nieporównywalne z a i b. Ale ponieważ b ma wyższą wartość niż a, możemy zmniejszyć wartość celu, zamieniając b i a, sprzeczność.$b$$a$

Podobnie możemy usunąć ograniczenie w przypadku, gdy o ile zapewniamy, że po sortowaniu według wartości zrywamy więzi, sprawdzając relacje pierwszeństwa pierwotnego (uproszczonego) problemu. Zapewnia to, że optymalne rozwiązanie dla złagodzonego problemu jest również optymalnym rozwiązaniem pierwotnego problemu.$v(a) = v(b)$

Dlatego za każdym razem, gdy b obejmuje a oraz , możemy uprościć problem, usuwając ograniczenie a < b .$v(a) \leq v(b)$$a < b$

Zasada 2 Załóżmy, że wiemy, że b następuje natychmiast po optymalnym rozwiązaniu. Można połączyć A i B do nowego węzła C i T c = T + t b , przy kurczeniu poset P odpowiednio.$w_c = w_a + w_b$$t_c = t_a + t_b$$P$

Optymalna wartość obiektywna nowego problemu różni się o stałą od pierwotnej wartości obiektywnej (konkretnie ), jednak ta stała nie zależy od uporządkowania, a zatem nie ma wpływu na optymalne uporządkowanie. Możemy odzyskać optymalne rozwiązanie starego problemu poprzez optymalne rozwiązanie nowego problemu i zastąpienie c z o b .$w_at_b$$c$$ab$

Reguła 3 Załóżmy, że optymalne rozwiązanie wystąpienie problemów, bezpośrednio poprzedza B i V ( ) > V ( b ) . Załóżmy teraz, że tworzymy większą instancję problemu, dodając nowe zadania z nowym zestawem utworzonym z serii lub kompozycji równoległej z oryginałem. Zawsze będzie optymalne rozwiązanie większego problemu, gdy pojawia się bezpośrednio przed b .$a$$b$$v(a) > v(b)$$a$$b$

Załóżmy inaczej. Niech optymalne rozwiązanie zawiera . Ponieważ P została utworzona przez szereg równoległych kompozycji, wiadomo, że wszystkie x i y są nieporównywalne i b . Scalanie wszystkich x i węzły do nowego węzła x ' stosując regułę 2. Rozważmy teraz v ( x ' ) . Jeśli v ( x ′ ) ≤ v ( a ) to możemy zamienić$a, x_1, x_2, \ldots, b$$P$$x_i$$a$$b$$x_i$$x'$$v(x')$$v(x') \leq v(a)$ ibez zwiększania wartości obiektywne. Podobnie, jeśli v ( x ′ ) ≥ v ( b ) , możemy zamienić x ′ i b . Dlatego v ( a ) < v ( x ′ ) < v ( b ) . Ale v ( a ) > v ( b ) , sprzeczność.$x'$$a$$v(x') \geq v(b)$$x'$$b$$v(a) < v(x') < v(b)$$v(a) > v(b)$

Stosując regułę 2 i zasadę 3, możemy już uzyskać prosty, ale nieoptymalny algorytm . Ponieważ P jest szeregową serią równoległą, załóżmy, że dane wejściowe zawierają drzewne przedstawienie P, gdzie każdy węzeł reprezentuje skład serii lub skład równoległy, a liście są pojedynczymi zadaniami. Możemy znaleźć optymalne rozwiązanie z przechodzeniem drzewa w przedsprzedaży, utrzymując niezmiennie, że optymalnym rozwiązaniem dla każdego podproblemu jest łańcuch o rosnącej wartości.$O(n^2)$$P$$P$

Załóżmy, że jest szeregową kompozycją podproblemów z zestawami P 1 i P 2 . Niech optymalne rozwiązania będą zamawiać C 1 i C 2 . Optymalnym rozwiązaniem dla P jest oczywiście połączenie tych łańcuchów. Jednak możliwe jest, że pierwsze zadanie w C 2 ma niższą wartość niż ostatnie zadanie w C 1 . Aby zachować niezmienność, że rozwiązanie jest posortowanym łańcuchem, używamy reguły 3 + reguły 2 do scalania punktów końcowych, o ile nie są one posortowane.$P$$P_1$$P_2$$C_1$$C_2$$P$$C_2$$C_1$

Jeśli jest składem równoległym, po prostu bierzemy posortowane łańcuchy S 1 i S 2 i łączymy je w nowy posortowany łańcuch. Dzięki niezmiennikowi jest to ważne.$P$$S_1$$S_2$

Niestety algorytmem tym jest . Aby uzyskać algorytm O ( n l o g n ) , musimy leniwie obliczyć łańcuchy, stosując regułę 1.$O(n^2)$$O(nlogn)$

W szczególności, jeśli podproblem zawiera tylko węzły, w których ograniczenia pierwszeństwa są takie same jak kolejność wartości, wówczas możemy całkowicie zapomnieć o ograniczeniach pierwszeństwa i spojrzeć tylko na wartości. Jest to zapewnione przez ten sam niezmiennik, który zapewnił, że rozwiązania są posortowanymi łańcuchami w poprzednim algorytmie.

Zamiast obliczać posortowany łańcuch dla każdego podproblemu, reprezentujemy optymalne rozwiązanie podproblemu jako parę hałd Fibonacciego, jedną stertę min i jedną stertę maksimum, obie zawierające wszystkie zadania w podproblemie. Oznacza to, że możemy zrzucić minimalny lub maksymalny element rozwiązania w czasie logarytmicznym.

$P$$P$

Aby uzyskać kompozycję równoległą, po prostu łączymy pary sterty. Nowa sterta min jest scaleniem stosu min z każdego podproblemu i podobnie z stosem maksymalnym. Pamiętaj, że hałdy Fibonacciego można łączyć w stałym czasie.

Gdy mamy parę stert reprezentującą rozwiązanie całego problemu, możemy znaleźć rzeczywiste uporządkowanie rozwiązania, odsuwając stertę min, aż będzie pusta. Następnie cofamy wszystkie podstawienia reguły 2, aby uzyskać rozwiązanie pierwotnego problemu.

$O(nlogn)$