Apakah ini masalah optimisasi / penjadwalan kombinasi yang diketahui?

Kami diberi tumpukan yang menampung "item" dengan warna berbeda dan sebuah mesin yang dapat memproses banyak item dengan warna yang sama sekaligus. Pada setiap langkah, kita dapat menghapus satu item dari bagian atas setiap tumpukan dan memasukkannya ke dalam mesin kami (sehingga secara efektif mesin dapat memproses paling banyak item dalam satu langkah - agar itu terjadi, semua tumpukan harus memiliki item dengan warna yang sama di atas). Tujuannya adalah untuk memproses semua item dalam waktu minimal. $n$ $n$

Input contoh:

Salah satu solusi yang mungkin adalah algoritma serakah: pada setiap langkah, cukup ambil item sebanyak mungkin dan masukkan semuanya ke dalam mesin. Sayangnya, algoritma serakah tidak optimal - menghasilkan jadwal berikut untuk contoh input:

Jadwal optimal adalah sebagai berikut:

Saya berencana untuk pergi dengan beberapa bentuk pencarian ruang negara, tetapi mungkin ada pendekatan yang lebih spesifik masalah dan efisien? Tautan ke literatur yang relevan dihargai.

ds.algorithms reference-request scheduling Mikhail Glushenkov
sumber

Pada setiap langkah, Anda hanya diperbolehkan mengambil satu item dari atas setiap tumpukan (dan semua item yang Anda masukkan ke mesin harus memiliki warna yang sama). Jadi algoritma serakah menghasilkan jadwal yang tidak optimal (lihat gambar 2).

Mikhail Glushenkov

Dan Anda harus memproses semua item secara berurutan, yaitu hanya mengambilnya dari atas.

Mikhail Glushenkov

Ahh. Oke. Masalah menarik. Saya akan membuat tabel pencarian optimal untuk memutuskan beberapa baris pertama jika ini adalah sistem realtime. Adapun kompleksitas yang tepat ... buktikan optimal untuk dua kasus kolom terlebih dahulu.

Chad Brewbaker

Pertanyaannya akan lebih menarik, jika beroperasi pada set daftar FIFO di mana Anda hanya dapat mengintip elemen hingga kedalaman tertentu untuk perhitungan.

George Polevoy

Jawaban:

Masalah Anda setara dengan Shortest Common Supersequence (SCS) dan dianggap dalam dengan nama Penjadwalan pada mesin batch dengan kendala diutamakan sebagai rantai dan kompatibilitas . Jika item dalam masalah memiliki warna yang sama maka masalah tersebut dalam P dan dapat diselesaikan dalam . $[1]$ $O(n^2)$ $[2]$

Apa yang menyangkut aproksimasi sumber yang baik adalah Ringkasan masalah optimasi NP .

Hasil terbaru pada SCS dapat ditemukan di . $[3,4]$

Untuk algoritma praktis, lihat yang penulisnya menyatakan bahwa "Hybrid MA-BS adalah teknik terkini untuk SCSP ". $[5]$ $[6]$

Brauner N., Naves G. Penjadwalan rantai operasi pada mesin batching dengan set kompatibilitas operasi terpisah .
Algoritma Penjadwalan Brucker P. (Bab 8. Masalah Batching).
Timkovsky VG Beberapa Perkiraan untuk Nonsub berikutnyaence dan Supersequences .
Gotthilf Z. dan Lewenstein M. Peningkatan Hasil Pendekatan pada Masalah Supersequence Umum Terpendek .
Kubalik J. Algoritma pencarian lokal stokastik efisien untuk memecahkan masalah supersequence umum terpendek .
Blum, C., Cotta, C., Fernandez, AJ, Gallardo, JE A Probabilistic Beam Search Approach untuk Problem Supersequence Umum Terpendek .

Oleksandr Bondarenko
sumber

kertas [1] berisi pengamatan saya akan menulis juga: ketika ada tumpukan dan item total, ada solusi pemrograman dinamis dalam waktu

k

$k$

n

$n$

O (n^{k})

$O(n^k)$

Sasho Nikolov

Masalah optimasi tampaknya sama dengan supersequensi umum terpendek juga. Dua hasil yang saya temukan terkait dengan perkiraan masalah ini (umumnya NP-hard) adalah ini dan ini . Ada beberapa hasil yang tidak dapat diperkirakan dan hasil perkiraan yang jauh lebih lemah. The pertama kertas menunjukkan kekerasan pendekatan dan faktor pendekatan polinomial. $\Omega(\log^\delta n)$

$k$ $k$ $X$ $|X| = x$ $X$ $x$ $x$ $X$ $x/k$ barang. Jadi masalahnya memiliki solusi pemrograman dinamis polytime ketika ada banyak tumpukan yang terus-menerus, dan perkiraan serakah yang konstan ketika selalu ada banyak kelas warna.

Sasho Nikolov
sumber