Czy ten szczególny przypadek problemu z planowaniem można rozwiązać w czasie liniowym?

Alice, studentka, ma dużo pracy domowej w ciągu najbliższych tygodni. Każda praca domowa zabiera ją dokładnie jednego dnia. Każda pozycja ma również termin i negatywny wpływ na jej oceny (zakładamy liczbę rzeczywistą, punkty bonusowe za przyjęcie założenia porównywalności), jeśli nie dotrzyma terminu.

Napisz funkcję, która podając listę (termin, wpływ na ocenę) obliczy harmonogram zadań domowych do wykonania w dniu, który minimalizuje sumę złego wpływu na jej oceny.

Wszystkie prace domowe muszą zostać ostatecznie wykonane, ale jeśli nie dotrzyma terminu, nie ma znaczenia, jak późno ją oddaje.

W alternatywnym sformułowaniu:

ACME corp chce dostarczać wodę do klientów. Wszyscy mieszkają wzdłuż jednej pod górę ulicy. ACME ma kilka studni rozmieszczonych wzdłuż ulicy. Każda studnia zawiera wystarczającą ilość wody dla jednego klienta. Klienci licytują różne kwoty pieniędzy do dostarczenia. Woda płynie tylko w dół. Maksymalizuj przychody, wybierając klientów do dostarczenia.

Możemy posortować terminy za pomocą sortowania kubełkowego (lub po prostu założyć, że już posortowaliśmy według terminu).

Możemy łatwo rozwiązać problem za pomocą chciwego algorytmu, jeśli najpierw posortujemy według malejącego wpływu na ocenę. To rozwiązanie nie będzie lepsze niż O (n log n).

Zainspirowany przez medianę median i algorytmy losowego liniowego drzewa rozpinającego , podejrzewam, że możemy rozwiązać mój prosty problem planowania / przepływu również w (losowym?) Czasie liniowym.

Szukam:

• (potencjalnie losowy) liniowy algorytm czasu
• lub alternatywnie argument, że czas liniowy nie jest możliwy

Jako odskocznia:

• Udowodniłem już, że sama wiedza o tym, które przedmioty można wykonać przed upływem terminu, wystarczy do odtworzenia pełnego harmonogramu w czasie liniowym. (Ta wiedza leży u podstaw drugiego sformułowania, w którym pytam tylko o certyfikat).
• Prosty (integralny!) Program liniowy może modelować ten problem.
• Korzystając z dualności tego programu, można sprawdzić proponowane rozwiązanie w czasie liniowym pod kątem optymalności, jeśli podano również rozwiązanie dla podwójnego programu. (Oba rozwiązania można przedstawić w postaci liniowej liczby bitów.)

Idealnie chciałbym rozwiązać ten problem w modelu, który wykorzystuje tylko porównanie wpływów ocen i nie zakłada tam liczb.

Mam dwa podejścia do tego problemu - jeden oparty na pułapkach z wykorzystaniem terminu i wpływu, drugi podobny do QuickSelect polegający na wybieraniu losowych elementów przestawnych i dzieleniu elementów przez uderzenie. Oba mają najgorsze przypadki, które wymuszają O (n log n) lub gorszą wydajność, ale nie byłem w stanie zbudować prostego specjalnego przypadku, który obniżyłby wydajność obu.

Kilka rzeczy, których do tej pory się dowiedziałem.

Możemy ograniczyć się do rozwiązania następującego pokrewnego problemu:

newtype Slot = Slot Int
newtype Schedule a = Schedule [(Slot, [a])]

findSchedule :: Ord a => Schedule a -> Schedule (a, Bool)

To znaczy podaj dane wejściowe już posortowane według terminu, ale pozwól na wykonanie dowolnej, nieujemnej liczby zadań każdego dnia. Podaj wynik, zaznaczając elementy, czy można je zaplanować na czas, czy nie.

Poniższa funkcja może sprawdzić, czy harmonogram podany w tym formacie jest wykonalny, tj. Czy wszystkie elementy znajdujące się w harmonogramie można zaplanować przed upływem terminów:

leftOverItems :: Schedule a -> [Int]
leftOverItems (Schedule sch) = scanr op 0 sch where
  op (Slot s, items) itemsCarried = max 0 (length items - s + itemsCarried)

feasible schedule = head (leftOverItems schedule) == 0

Jeśli mamy proponowane rozwiązanie kandydujące, a wszystkie elementy pominięte, możemy sprawdzić w czasie liniowym, czy kandydat jest optymalny, czy też czy w pominiętym zestawie znajdują się elementy, które poprawiłyby rozwiązanie. Te lekkie elementy nazywamy analogicznie do terminologii algorytmu minimalnego drzewa opinającego

carry1 :: Ord a => Schedule a -> [Bound a]
carry1 (Schedule sch) = map (maybe Top Val . listToMaybe) . scanr op [] $ sch where
  op (Slot s, items) acc = remNonMinN s (foldr insertMin acc items)

-- We only care about the number of items, and the minimum item.
-- insertMin inserts an item into a list, keeping the smallest item at the front.
insertMin :: Ord a => a -> [a] -> [a]
insertMin a [] = [a]
insertMin a (b:bs) = min a b : max a b : bs

-- remNonMin removes an item from the list,
-- only picking the minimum at the front, if it's the only element.
remNonMin :: [a] -> [a]
remNonMin [] = []
remNonMin [x] = []
remNonMin (x:y:xs) = x : xs

remNonMinN :: Int -> [a] -> [a]
remNonMinN n l = iterate remNonMin l !! n

data Bound a = Bot | Val a | Top
  deriving (Eq, Ord, Show, Functor)

-- The curve of minimum reward needed for each deadline to make the cut:
curve :: Ord a => Schedule a -> [Bound a]
curve = zipWith min <$> runMin <*> carry1

-- Same curve extended to infinity (in case the Schedules have a different length)
curve' :: Ord a => Schedule a -> [Bound a]
curve' = ((++) <*> repeat . last) . curve

-- running minimum of items on left:
runMin :: Ord a => Schedule a -> [Bound a]
runMin = scanl1 min . map minWithBound . items . fmap Val

minWithBound :: Ord a => [Bound a] -> Bound a
minWithBound = minimum . (Top:)

-- The pay-off for our efforts, this function uses
-- the candidate solution to classify the left-out items
-- into whether they are definitely _not_ in
-- the optimal schedule (heavy items), or might be in it (light items).
heavyLight :: Ord a => Schedule a -> Schedule a -> ([[a]],[[a]])
heavyLight candidate leftOut =
    unzip . zipWith light1 (curve' candidate) . items $ leftOut
  where
    light1 pivot = partition (\item -> pivot < Val item)

heavyLight nie tylko sprawdza proponowane harmonogramy pod kątem optymalności, ale także daje listę elementów, które mogą poprawić nieoptymalny harmonogram.

$O(n^2)$$O(n\log n)$