Apakah kasus khusus ini masalah penjadwalan dipecahkan dalam waktu linier?

Alice, seorang siswa, memiliki banyak pekerjaan rumah selama beberapa minggu ke depan. Setiap item pekerjaan rumah membawanya tepat satu hari. Setiap item juga memiliki tenggat waktu, dan dampak negatif pada nilai-nilainya (anggap angka sebenarnya, poin bonus hanya dengan asumsi dapat diperbandingkan), jika dia melewatkan tenggat waktu.

Tuliskan fungsi yang diberi daftar (tenggat waktu, dampak kelas) menggambarkan jadwal pekerjaan rumah yang harus dilakukan pada hari yang meminimalkan jumlah dampak buruk pada nilai-nilainya.

Semua pekerjaan rumah harus dilakukan pada akhirnya, tetapi jika dia melewatkan tenggat waktu untuk sebuah barang, tidak masalah seberapa terlambat dia menyerahkannya.

Dalam formulasi alternatif:

ACME corp ingin memasok air ke pelanggan. Mereka semua hidup di sepanjang jalan yang menanjak. ACME memiliki beberapa sumur yang didistribusikan di sepanjang jalan. Setiap sumur menghasilkan air yang cukup untuk satu pelanggan. Pelanggan menawarkan jumlah uang yang berbeda untuk dipasok. Air hanya mengalir menurun. Maksimalkan pendapatan dengan memilih pelanggan yang akan dipasok.

Kami dapat mengurutkan tenggat waktu menggunakan penyortiran ember (atau anggap saja kami telah menyortir berdasarkan tenggat waktu).

Kita dapat memecahkan masalah dengan mudah dengan algoritma serakah, jika kita mengurutkannya dengan menurunkan dampak kelas terlebih dahulu. Solusi itu tidak akan lebih baik dari O (n log n).

Terinspirasi oleh Median of Median dan algoritma pohon rentang minimum linear acak , saya menduga bahwa kita dapat menyelesaikan masalah penjadwalan / aliran sederhana saya dalam waktu (acak?) Linear.

Saya mencari:

• algoritma waktu linear (berpotensi acak)
• atau sebagai alternatif argumen bahwa waktu linier tidak dimungkinkan

Sebagai batu loncatan:

• Saya telah membuktikan bahwa hanya mengetahui item mana yang dapat dilakukan sebelum batas waktu mereka, cukup untuk merekonstruksi jadwal lengkap dalam waktu linier. (Wawasan itu mendasari rumusan kedua di mana saya hanya bertanya tentang sertifikat.)
• Program linear sederhana (integral!) Dapat memodelkan masalah ini.
• Menggunakan dualitas dari program ini, seseorang dapat memeriksa kandidat solusi yang diusulkan dalam waktu linier untuk optimalitas, jika seseorang juga diberikan solusi untuk program ganda. (Kedua solusi dapat direpresentasikan dalam jumlah linier bit.)

Idealnya, saya ingin menyelesaikan masalah ini dalam model yang hanya menggunakan perbandingan antara dampak kelas, dan tidak menganggap angka di sana.

Saya memiliki dua pendekatan untuk masalah ini --- satu didasarkan pada treaps menggunakan tenggat waktu dan dampak, yang lain QuickSelect berdasarkan pemilihan elemen pivot acak dan mempartisi item berdasarkan dampak. Keduanya memiliki kasus terburuk yang memaksa O (n log n) atau kinerja lebih buruk, tetapi saya belum dapat membuat kasus khusus sederhana yang menurunkan kinerja keduanya.

Beberapa hal yang saya temukan sejauh ini.

Kita dapat mengurangi diri untuk memecahkan masalah terkait berikut:

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

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

Yaitu memberikan data input yang sudah diurutkan berdasarkan tenggat waktu, tetapi memungkinkan sejumlah tugas yang tidak negatif dilakukan setiap hari. Berikan output dengan hanya menandai elemen pada apakah mereka dapat dijadwalkan pada waktunya, atau tidak.

Fungsi berikut dapat memeriksa apakah jadwal yang diberikan dalam format ini layak, yaitu apakah semua item yang masih dalam jadwal dapat dijadwalkan sebelum tenggat waktu mereka:

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

Jika kami memiliki solusi kandidat yang diusulkan, dan semua item yang ditinggalkan, kami dapat memeriksa dalam waktu linier apakah kandidat optimal, atau apakah ada item dalam set kiri yang akan meningkatkan solusi. Kami menyebut item ringan ini , dalam analogi dengan terminologi dalam algoritma Minimum Spanning Tree

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 tidak hanya memeriksa jadwal yang diusulkan untuk optimalitas, itu juga memberi Anda daftar item yang dapat meningkatkan jadwal yang tidak optimal.

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