Algoritma Divide And Conquer

Paradigma divide-and-conquer sering digunakan untuk mencari solusi optimal dari suatu masalah. Ide dasarnya adalah untuk menguraikan masalah yang diberikan menjadi dua atau lebih serupa, tetapi lebih sederhana, subproblem, untuk menyelesaikannya secara bergantian, dan menyusun solusi mereka untuk memecahkan masalah yang diberikan. Masalah kesederhanaan yang cukup diselesaikan secara langsung. Misalnya, untuk mengurutkan daftar n bilangan asli tertentu, pisahkan menjadi dua daftar yang masing-masing berisi sekitar n / 2, urutkan masing-masing secara bergantian, dan sisipkan kedua hasil dengan tepat untuk mendapatkan versi yang diurutkan dari daftar yang diberikan (lihat gambar). Pendekatan ini dikenal sebagai algoritma pengurutan gabungan .

Nama “divide and conquer” kadang-kadang diterapkan pada algoritma yang mengurangi setiap masalah menjadi hanya satu sub-masalah, seperti algoritma pencarian biner untuk menemukan catatan dalam daftar yang diurutkan (atau analognya dalam komputasi numerik , algoritma pembagian dua untuk root menemukan ). ^[2] Algoritma ini dapat diimplementasikan lebih efisien daripada algoritma divide-and-conquer umum; khususnya, jika mereka menggunakan rekursi ekor , mereka dapat diubah menjadi loop sederhana. Di bawah definisi yang luas ini, bagaimanapun, setiap algoritma yang menggunakan rekursi atau loop dapat dianggap sebagai “algoritma divide-and-conquer”. Oleh karena itu, beberapa penulis menganggap bahwa nama “divide and conquer” harus digunakan hanya jika setiap masalah dapat menghasilkan dua atau lebih subproblem. ^[3] Pengurangan dan penaklukan nama telah diusulkan sebagai gantinya untuk kelas subproblem tunggal. ^[4]

Aplikasi penting dari divide and conquer adalah dalam pengoptimalan,   dimana jika ruang pencarian dikurangi (“dipangkas”) oleh faktor konstan pada setiap langkah, keseluruhan algoritme memiliki kompleksitas asimtotik yang sama dengan langkah pemangkasan, dengan konstan tergantung pada faktor pemangkasan (dengan menjumlahkan deret geometris ); ini dikenal sebagai prune and search .

Contoh awal dari algoritme divide and conquer dengan beberapa subproblem adalah deskripsi Gauss pada tahun 1805 tentang apa yang sekarang disebut algoritme Cooley-Tukey fast Fourier transform (FFT), ^[6] meskipun dia tidak menganalisis jumlah operasinya secara kuantitatif, dan FFT tidak tersebar luas sampai ditemukan kembali lebih dari satu abad kemudian.

Algoritme D&C dua subproblem awal yang secara khusus dikembangkan untuk komputer dan dianalisis dengan benar adalah algoritme pengurutan gabungan , yang ditemukan oleh John von Neumann pada tahun 1945. ^[7]

Contoh penting lainnya adalah algoritma yang ditemukan oleh Anatolii A. Karatsuba pada tahun 1960 ^[8] yang dapat mengalikan dua angka n- digit dalam operasi (dalam notasi Big O ). Algoritma ini membantah dugaan 1956 Andrey Kolmogorov itu operasi akan diperlukan untuk tugas itu.

Sebagai contoh lain dari algoritme divide and conquer yang awalnya tidak melibatkan komputer, Donald Knuth memberikan metode yang biasanya digunakan kantor pos untuk merutekan surat: surat diurutkan ke dalam tas terpisah untuk wilayah geografis yang berbeda, masing-masing tas ini diurutkan sendiri ke dalam batch untuk sub-wilayah yang lebih kecil, dan seterusnya sampai dikirimkan. ^[5] Ini terkait dengan jenis radix , dijelaskan untuk mesin sortir kartu berlubang sejak tahun 1929. ^[5]

Memecahkan masalah yang sulit

Divide-and-conquer adalah alat yang ampuh untuk memecahkan masalah yang sulit secara konseptual: yang dibutuhkan hanyalah cara memecahkan masalah menjadi sub-masalah, memecahkan kasus-kasus sepele dan menggabungkan sub-masalah ke masalah asli. Demikian pula, mengurangi dan menaklukkan hanya membutuhkan pengurangan masalah menjadi satu masalah yang lebih kecil, seperti teka-teki Menara Hanoi klasik , yang mengurangi memindahkan menara dengan ketinggian n untuk memindahkan menara dengan ketinggian n  – 1.

Efisiensi algoritma

Paradigma divide-and-conquer sering membantu dalam penemuan algoritma yang efisien. Itu adalah kunci, misalnya, untuk metode perkalian cepat Karatsuba, algoritma quicksort dan mergesort, algoritma Strassen untuk perkalian matriks, dan transformasi Fourier cepat.

Dalam semua contoh ini, pendekatan D&C mengarah pada peningkatan biaya asimtotik solusi. Misalnya, jika (a) kasus dasar memiliki ukuran batas konstan, pekerjaan pemecahan masalah dan penggabungan solusi parsial sebanding dengan ukuran masalah n , dan (b) ada bilangan terbatas p dari sub-masalah dari size ~ n / p pada setiap tahap, maka biaya algoritma divide-and-conquer adalah O ( n  log _p n ).

Paralelisme

Algoritme Divide-and-conquer secara alami diadaptasi untuk eksekusi di mesin multi-prosesor, terutama sistem memori bersama di mana komunikasi data antara prosesor tidak perlu direncanakan sebelumnya, karena sub-masalah yang berbeda dapat dijalankan pada prosesor yang berbeda.

Akses memori

Algoritme divide and conquer secara alami cenderung memanfaatkan cache memori secara efisien . Alasannya adalah bahwa setelah sub-masalah cukup kecil, sub-masalah itu dan semua sub-masalah pada prinsipnya dapat diselesaikan dalam cache, tanpa mengakses memori utama yang lebih lambat. Algoritme yang dirancang untuk mengeksploitasi cache dengan cara ini disebut cache-oblivious , karena tidak memuat ukuran cache sebagai parameter eksplisit. ^[9] Selain itu, algoritme D&C dapat dirancang untuk algoritme penting (misalnya, pengurutan, FFT, dan perkalian matriks) menjadi algoritme yang tidak menyadari cache yang optimal – algoritme tersebut menggunakan cache dengan cara yang mungkin optimal, dalam arti asimtotik, terlepas dari ukuran cache. Sebaliknya, pendekatan tradisional untuk mengeksploitasi cache adalahmemblokir , seperti dalam pengoptimalan sarang loop , di mana masalah secara eksplisit dibagi menjadi beberapa bagian dengan ukuran yang sesuai — ini juga dapat menggunakan cache secara optimal, tetapi hanya jika algoritme disetel untuk ukuran cache tertentu dari mesin tertentu.

Keuntungan yang sama terdapat pada sistem penyimpanan hierarki lainnya, seperti NUMA atau memori virtual , serta untuk beberapa level cache: setelah sub-masalah cukup kecil, sub-masalah dapat diselesaikan dalam level hierarki tertentu, tanpa mengakses level yang lebih tinggi (lebih lambat).

Kontrol pembulatan

Dalam perhitungan dengan aritmatika bulat, misalnya dengan bilangan floating-point , algoritme divide and conquer dapat menghasilkan hasil yang lebih akurat daripada metode iteratif yang secara dangkal setara. Misalnya, seseorang dapat menambahkan nomor N baik dengan loop sederhana yang menambahkan setiap datum ke variabel tunggal, atau dengan algoritma D&C yang disebut penjumlahan berpasangan yang memecah kumpulan data menjadi dua bagian, secara rekursif menghitung jumlah setiap setengah, dan kemudian menambahkan dua jumlah. Meskipun metode kedua melakukan jumlah penambahan yang sama seperti yang pertama, dan membayar biaya tambahan dari panggilan rekursif, metode ini biasanya lebih akurat. ^[10]

Pengulangan

Algoritma divide-and-conquer secara alami diimplementasikan sebagai prosedur rekursif . Dalam kasus tersebut, sebagian sub-masalah yang mengarah ke masalah yang saat ini sedang diselesaikan secara otomatis disimpan dalam tumpukan panggilan prosedur . Fungsi rekursif adalah fungsi yang memanggil dirinya sendiri dalam definisinya.

Tumpukan eksplisit

Algoritma Divide-and-conquer juga dapat diimplementasikan oleh program non-rekursif yang menyimpan sub-masalah parsial dalam beberapa struktur data eksplisit, seperti tumpukan , antrian , atau antrian prioritas . Pendekatan ini memungkinkan lebih banyak kebebasan dalam memilih sub-masalah yang akan dipecahkan selanjutnya, fitur yang penting dalam beberapa aplikasi – misalnya dalam rekursi pertama-luas dan metode cabang-dan-terikat untuk optimasi fungsi. Pendekatan ini juga merupakan solusi standar dalam bahasa pemrograman yang tidak memberikan dukungan untuk prosedur rekursif.

Ukuran tumpukan

Dalam implementasi rekursif algoritme D&C, seseorang harus memastikan bahwa ada cukup memori yang dialokasikan untuk tumpukan rekursi, jika tidak, eksekusi mungkin gagal karena tumpukan melimpah . Algoritme D&C yang hemat waktu seringkali memiliki kedalaman rekursi yang relatif kecil. Sebagai contoh, algoritma quicksort dapat diimplementasikan sehingga tidak membutuhkan lebih dari panggilan rekursif bersarang untuk mengurutkan item.

Stack overflow mungkin sulit untuk dihindari saat menggunakan prosedur rekursif, karena banyak compiler berasumsi bahwa stack rekursi adalah area memori yang berdekatan, dan beberapa mengalokasikan jumlah ruang yang tetap untuk itu. Kompiler juga dapat menyimpan lebih banyak informasi dalam tumpukan rekursi daripada yang benar-benar diperlukan, seperti alamat pengembalian, parameter yang tidak berubah, dan variabel internal prosedur. Dengan demikian, risiko stack overflow dapat dikurangi dengan meminimalkan parameter dan variabel internal dari prosedur rekursif atau dengan menggunakan struktur stack eksplisit.

Memilih kasus dasar

Dalam algoritme rekursif apa pun, ada banyak kebebasan dalam memilih kasus dasar , sub-masalah kecil yang diselesaikan secara langsung untuk menghentikan rekursi.

Memilih kasus dasar terkecil atau sesederhana mungkin lebih elegan dan biasanya mengarah ke program yang lebih sederhana, karena ada lebih sedikit kasus untuk dipertimbangkan dan lebih mudah dipecahkan. Misalnya, algoritme FFT dapat menghentikan rekursi jika inputnya adalah sampel tunggal, dan algoritme pengurutan daftar quicksort dapat berhenti jika inputnya adalah daftar kosong; pada kedua contoh hanya ada satu kasus dasar yang perlu dipertimbangkan, dan tidak memerlukan pemrosesan.

Di sisi lain, efisiensi sering meningkat jika rekursi dihentikan pada kasus dasar yang relatif besar, dan ini diselesaikan secara non-rekursif, menghasilkan algoritme hibrid . Strategi ini menghindari overhead panggilan rekursif yang melakukan sedikit atau tidak ada pekerjaan, dan juga memungkinkan penggunaan algoritme non-rekursif khusus yang, untuk kasus dasar tersebut, lebih efisien daripada rekursi eksplisit. Prosedur umum untuk algoritme rekursif hybrid sederhana adalah melakukan hubungan arus pendek pada casing dasar , juga dikenal sebagai rekursi arm’s-length.. Dalam kasus ini apakah langkah selanjutnya akan menghasilkan kasus dasar diperiksa sebelum pemanggilan fungsi, menghindari pemanggilan fungsi yang tidak perlu. Misalnya, dalam sebuah pohon, daripada mengulang ke simpul anak dan kemudian memeriksa apakah itu null, memeriksa null sebelum mengulang; ini menghindari setengah pemanggilan fungsi dalam beberapa algoritme pada pohon biner. Karena algoritme D&C pada akhirnya mengurangi setiap masalah atau instance sub-masalah menjadi sejumlah besar instance dasar, ini sering kali mendominasi keseluruhan biaya algoritme, terutama ketika overhead pemisahan / penggabungan rendah. Perhatikan bahwa pertimbangan ini tidak bergantung pada apakah rekursi diimplementasikan oleh kompilator atau tumpukan eksplisit.

Jadi, misalnya, banyak implementasi pustaka quicksort akan beralih ke algoritme sortir penyisipan berbasis loop sederhana (atau serupa) setelah jumlah item yang akan diurutkan cukup kecil. Perhatikan bahwa, jika daftar kosong adalah satu-satunya kasus dasar, pengurutan daftar dengan n entri akan memerlukan maksimal n panggilan quicksort yang tidak akan melakukan apa pun selain langsung kembali. Meningkatkan kasus dasar ke daftar ukuran 2 atau kurang akan menghilangkan sebagian besar panggilan tidak melakukan apa-apa, dan lebih umum kasus dasar yang lebih besar dari 2 biasanya digunakan untuk mengurangi sebagian kecil waktu yang dihabiskan dalam overhead panggilan fungsi atau manipulasi tumpukan.

Alternatifnya, seseorang dapat menggunakan kasus dasar besar yang masih menggunakan algoritme divide-and-conquer, tetapi mengimplementasikan algoritme tersebut untuk kumpulan ukuran tetap yang telah ditentukan di mana algoritme dapat sepenuhnya dibuka gulungannya menjadi kode yang tidak memiliki rekursi, loop, atau kondisional (terkait dengan teknik evaluasi parsial ). Misalnya, pendekatan ini digunakan dalam beberapa implementasi FFT yang efisien, di mana kasus dasar adalah implementasi yang tidak digulung dari algoritma FFT divide-and-conquer untuk satu set ukuran tetap. ^[11] Metode pembuatan kode sumber dapat digunakan untuk menghasilkan sejumlah besar kasus dasar terpisah yang diinginkan untuk mengimplementasikan strategi ini secara efisien. ^[11]

Versi umum dari ide ini dikenal sebagai rekursi “unrolling” atau “coarsening”, dan berbagai teknik telah diusulkan untuk mengotomatiskan prosedur memperbesar base case. ^[12]

Berbagi submasalah yang berulang

Untuk beberapa masalah, rekursi bercabang mungkin akhirnya mengevaluasi sub-masalah yang sama berkali-kali. Dalam kasus seperti itu, mungkin ada baiknya mengidentifikasi dan menyimpan solusi untuk sub masalah yang tumpang tindih ini, teknik yang biasa dikenal sebagai memoization . Diikuti hingga batasnya, ini mengarah ke algoritme divide-and-conquer bottom-up seperti pemrograman dinamis dan penguraian grafik .