Get best of the week

Buku “Algoritma Sempurna. Algoritma Greedy dan Pemrograman Dinamis "

gambarHalo, habrozhiteli! Dalam buku baru, Tim Rafgarden berbicara tentang algoritma serakah (masalah perencanaan, pohon spanning minimal, pengelompokan, kode Huffman) dan pemrograman dinamis (masalah ransel, perataan urutan, jalur terpendek, jalur pencarian optimal). Posting ini menyajikan kutipan "Mengembangkan algoritma serakah."

Algoritma serakah tampaknya cocok untuk tugas penjadwalan, meminimalkan jumlah waktu penyelesaian yang tertimbang. Output memiliki struktur berulang, di mana pekerjaan diproses satu per satu. Mengapa tidak menggunakan algoritme serakah yang secara iteratif menentukan pekerjaan mana yang akan dilakukan selanjutnya?

Langkah pertama dari rencana kami adalah menyelesaikan dua kasus khusus dari masalah umum. Solusi kami untuk kasus-kasus ini akan menunjukkan bagaimana algoritma serakah mungkin terlihat seperti dalam kasus umum. Kemudian kami mempersempit domain menjadi satu algoritma kandidat dan membuktikan bahwa kandidat inilah yang memecahkan masalah dengan benar. Proses kita sampai pada algoritma ini lebih penting untuk mengingat daripada algoritma itu sendiri; proses ini berulang dan Anda dapat menggunakannya di aplikasi Anda sendiri.

13.3.1. Dua kasus khusus


Mari kita asumsikan bahwa untuk tugas meminimalkan jumlah tertimbang tanggal penyelesaian, sebenarnya, ada algoritma serakah yang benar. Seperti apa jadinya jika kita berasumsi bahwa semua karya memiliki panjang yang sama (tetapi mungkin bobotnya berbeda) atau, sebaliknya, memiliki bobot yang sama (tetapi mungkin panjangnya berbeda)?
13.2

(1) , ?
(2) , ?
) ;
) ;
) ;
) ;
( . 13.3.3.)

13.3.2.


Secara umum, pekerjaan mungkin memiliki bobot dan panjang yang berbeda. Setiap kali dua aturan praktis kami - untuk memilih pekerjaan yang lebih pendek dan bekerja dengan bobot yang lebih tinggi - beruntung untuk beberapa pekerjaan yang bersamaan, kami tahu mana yang harus direncanakan terlebih dahulu (lebih pendek dengan bobot yang lebih tinggi). Tetapi bagaimana jika kedua aturan ini memberikan saran yang bertentangan? Apa yang harus kita lakukan dengan satu pekerjaan pendek dengan bobot rendah dan satu pekerjaan panjang dengan bobot tinggi?

Apa yang akan menjadi algoritma serakah paling sederhana yang akan bekerja sebagaimana mestinya? Setiap karya memiliki dua parameter, dan algoritma harus melihat keduanya. Pilihan terbaik adalah mengembangkan formula yang mengkompilasi panjang dan berat masing-masing pekerjaan menjadi satu tanda (kontribusi), sehingga pekerjaan perencanaan dari tanda tertinggi ke terendah dijamin untuk meminimalkan jumlah tanggal penyelesaian tertimbang. Jika formula seperti itu ada, maka dari dua kasus khusus kami, itu mengikuti bahwa itu harus memiliki dua sifat: (i) membiarkan panjang tetap, itu harus meningkat dengan berat pekerjaan; (ii) membiarkan beratnya tetap, itu harus berkurang dari panjang pekerjaan (ingat bahwa semakin tinggi tanda, semakin baik). Luangkan waktu sejenak untuk melakukan brainstorming beberapa formula yang memiliki kedua sifat ini.

gambar

Mungkin fungsi yang paling sederhana, yang menambah bobot dan mengurangi panjangnya, adalah perbedaan di antara mereka:
proposal nomor 1 untuk tanda pekerjaan. gambar

Tanda yang ditunjukkan bisa negatif, tetapi ini tidak menimbulkan hambatan pada konstruksi pekerjaan yang konsisten dari yang tertinggi ke yang terendah. . Namun, ada banyak opsi lain. Misalnya, rasio dua parameter adalah kandidat lain:

Proposal No. 2 untuk menandai pekerjaan. gambar

Kedua fungsi untuk menghitung tanda mengarah ke dua algoritma serakah yang berbeda.
PERBEDAAN GREEDYDIFF Keserakahan

Rencana bekerja dalam urutan menurun gambar
(semena-mena melanggar nilai-nilai kebetulan).
GREEDYRATIO

gambar
( ).

Dengan demikian, sudah studi kasus pertama kami menggambarkan topik pertama dari paradigma rakus (bagian 13.1.2): untuk mengusulkan tugas beberapa algoritma serakah bersaing biasanya tidak sulit. Tapi yang mana dari dua algoritma, jika ada, yang benar? Cara cepat untuk mengecualikan salah satunya adalah dengan menemukan contoh di mana dua algoritma menampilkan jadwal yang berbeda dengan nilai fungsi obyektif yang berbeda. Untuk algoritma apa pun yang hasilnya lebih buruk dalam contoh ini, kita dapat menyimpulkan bahwa itu tidak selalu optimal. Dalam dua kasus khusus dengan karya dengan bobot yang sama atau panjang yang sama, kedua algoritma bekerja dengan benar. Contoh kemungkinan paling sederhana dari pengecualian salah satunya adalah contoh tugas di mana dua karya memiliki bobot dan panjang yang berbeda,sebagai hasilnya, kedua algoritma berencana untuk bekerja dalam urutan yang berlawanan. Yaitu, kami sedang mencari dua karya, yang urutannya berbeda dari urutannya dalam hubungan. Contoh:

gambar

Karya pertama memiliki rasio besar yang lebih besar gambartetapi perbedaan yang lebih besar (–2 vs –1). Jadi, algoritma GreedyDiffmerencanakan pekerjaan kedua terlebih dahulu, sedangkan algoritma GreedyRatiomerencanakan yang sebaliknya.
LATIHAN 13.3

Berapakah jumlah dari tanggal penyelesaian tertimbang dalam jadwal yang disimpulkan oleh GreedyDiffdan algoritma, masing-masing GreedyRatio?

a) 22 dan 23
b) 23 dan 22
c) 17 dan 17
d) 17 dan 11
(Untuk solusi dan penjelasan, lihat bagian 13.3.3.)

Kami bergerak maju dengan mengecualikan algoritma GreedyDiffdari pertimbangan lebih lanjut. Namun, hasil latihan 13.3 tidak secara langsung mengarah pada fakta bahwa algoritma GreedyRatioakan selalu optimal. Sejauh yang kami tahu, ada kasus lain ketika algoritma ini menghasilkan jadwal yang tidak optimal. Anda harus selalu skeptis terhadap suatu algoritma yang tidak disertai dengan bukti kebenarannya, bahkan jika algoritma ini melakukan hal yang benar dalam beberapa kasus uji dan sangat skeptis terhadap algoritma serakah.

Dalam kasus kami, algoritma GreedyRatio, pada kenyataannya, dijamin untuk meminimalkan jumlah tanggal penyelesaian tertimbang.

Teorema 13.1 (kebenaran dari algoritma GreedyRatio) . Untuk setiap set bobot kerja positifgambardan panjang pekerjaan positif, gambaralgoritma GreedyRatiomenampilkan jadwal dengan jumlah terkecil dari tanggal penyelesaian tertimbang.

Pernyataan logis ini tidak jelas, dan Anda tidak boleh percaya padanya tanpa menerima bukti. Sesuai dengan tema ketiga dari paradigma rakus (bagian 13.1.2), bukti ini mengambil seluruh bagian berikutnya.
, . .

. — , ( ). — , , , . «» ( ) , .

Tema yang tersisa dari paradigma rakus adalah kesederhanaan analisis runtime (bagian 13.1.2). Di sini, tentu saja. Algoritme GreedyRatio hanya mengurutkan pekerjaan berdasarkan hubungan, yang membutuhkan waktu O (n log n), di mana n adalah jumlah pekerjaan pada input (lihat catatan kaki 1 pada halaman 24).

13.3.3. Solusi Latihan 13.2–13.3


Solusi untuk berolahraga 13.2

Jawaban yang benar adalah: (a) . Pertama, anggaplah bahwa semua n pekerjaan memiliki panjang yang sama, katakanlah 1. Kemudian setiap jadwal memiliki tenggat waktu yang persis sama - {1, 2, 3, ..., n} - dan satu-satunya pertanyaan adalah pekerjaan seperti apa yang didapat tanggal penyelesaian dan apa batas waktunya. Semantik kami untuk bobot kerja tentu menyiratkan bahwa pekerjaan dengan bobot lebih besar harus menerima waktu penyelesaian yang lebih pendek, dan ini benar. Misalnya, Anda tidak ingin merencanakan pekerjaan dengan bobot 10 sepertiga (dengan tenggat waktu 3) dan bekerja dengan bobot 20 perlima (dengan tenggat waktu 5); Anda akan lebih baik mengubah posisi kedua karya ini, yang akan mengurangi jumlah tenggat waktu tertimbang sebesar 20 (seperti yang Anda lihat sendiri).

Kasus kedua, di mana semua karya memiliki bobot yang sama, sedikit lebih tipis. Di sini Anda ingin memberikan preferensi untuk pekerjaan yang lebih pendek. Misalnya, pertimbangkan dua pekerjaan unit berat dengan panjang 1 dan 2. Jika Anda pertama kali merencanakan pekerjaan yang lebih pendek, maka tenggat waktu penyelesaian akan menjadi 1 dan 3 dengan total 4. Dalam urutan terbalik, tenggat waktu akan 2 dan 3 dengan hasil terburuk 5. Secara umum, yang direncanakan pekerjaan pertama berkontribusi pada waktu penyelesaian semua pekerjaan, karena semua pekerjaan harus menunggu penyelesaian pekerjaan pertama. Semua hal dianggap sama, merencanakan pekerjaan terpendek terlebih dahulu meminimalkan dampak negatif ini. Pekerjaan kedua berkontribusi pada semua tanggal penyelesaian kecuali pekerjaan pertama, sehingga pekerjaan terpendek kedua harus direncanakan berikutnya, dan seterusnya.

Solusi latihan 13.3

Jawaban yang benar adalah: (b). Algoritma ini GreedyDiffmerencanakan pekerjaan kedua terlebih dahulu. Batas waktu untuk menyelesaikan pekerjaan ini adalah gambarsedangkan batas waktu untuk menyelesaikan pekerjaan lain adalah gambarJumlah dari tenggat waktu tertimbang untuk diselesaikan

gambar

Algoritma ini GreedyRatiomerencanakan pekerjaan pertama terlebih dahulu, menghasilkan tenggat waktu gambar
dan jumlah tenggat waktu tertimbang sama dengan

gambar

Karena algoritma GreedyDiffgagal menghitung jadwal optimal untuk contoh ini , itu tidak selalu benar.

»Informasi lebih lanjut tentang buku itu dapat ditemukan di situs web penerbit
» Isi
» Kutipan

Untuk Khabrozhiteley Diskon 25% pada kupon - Algoritma

Setelah pembayaran versi kertas buku, sebuah buku elektronik dikirim melalui email.

More articles:


All Articles