Brute Force

Brute force adalah sebuah pendekatan yang terang-terangan di dalam memecahkan suatu masalah, pada umumnya secara langsung didasarkan kepada pernyataan masalah dan pengertian konsep yang terlibat di dalamnya. Algoritma brute force memecahkan masalah dengan sangat sederhana, langsung dan dengan cara yang jelas (obvious way).

Karakteristik Brute Force

Berikut ini merupakan karakteristik dari algoritma-algoritma yang menggunakan pendekatan brute force sebagai basisnya.

Algoritma brute force umumnya tidak "cerdas" dan tidak efektif, karena ia membutuhkan jumlah langkah yang besar dalam penyelesaiannya. Kadang-kadang algoritma brute force disebut juga algoritma naif (naïve algorithm).

Algoritma brute force seringkali merupakan pilihan yang kurang disukai karena ketidakefektifannya itu, tetapi dengan mencari pola-pola yang mendasar, keteraturan, atau trik-trik khusus, biasanya akan membantu kita menemukan algoritma yang lebih cerdas dan lebih efektif.

Untuk masalah yang ukurannya kecil, kesederhanaan brute force biasanya lebih diperhitungkan daripada ketidakefektifannya

Algoritma brute force sering digunakan sebagai basis bila membandingkan beberapa alternatif algoritma yang efektif.

Algoritma brute force seringkali lebih mudah diimplementasikan daripada algoritma yang lebih canggih, dan karena kesederhanaannya, kadang-kadang algoritma brute force dapat lebih efektif (ditinjau dari segi implementasi).

Algoritma brute force akan selalu menemukan solusi jika diberikan waktu yang cukup

Sequntial Sort dan Bubble Sort

Pendekatan brute force dapat digunakan untuk memecahkan masalah sorting atau pengurutan. Ada 2 algoritma pokok yang terkenal dengan pendekatan tersebut, yaitu algoritma selection sort dan bubble sort.

Sequential sort dimulai dengan memeriksa keseluruhan list untuk menemukan elemen terkecil dan kemudian menukar posisinya dengan elemen pertama di dalam list. Setelah itu, kembali dilakukan pemeriksaan list dimulai dari elemen kedua, untuk menemukan elemen terkecil dari keseluruhan elemen yang tersisa, lalu elemen tersebut ditukar posisinya dengan elemen kedua dan begitu seterusnya untuk elemen selanjutnya hingga didapatkan list yang berurut dari nilai terkecil hingga nilai terbesar.

Bubble sort diaplikasikan dengan membandingkan elemen yang berdekatan di dalam list dan menukar posisi mereka jika tidak berurutan. Dengan melakukan hal tersebut berulang-ulang, akan didapatkan penggelembungan elemen terbesar di posisi terakhir di dalam list. Pada langkah selanjutnya, dilakukan penggelembungan terhadap elemen kedua terbesar, begitu selanjutnya hingga setelah melewati giliran ke n – 1, dihasilkan list yang sudah berurut.

Depth-First Search dan Breadth-First Search

Untuk masalah yang melibatkan graf dalam kecerdasan buatan dan penelitian operasi-operasi dapat juga diselesaikan dengan memakai pendekatan brute force. Algoritma yang memakai pendekatan tersebut antara lain adalah depth-first search dan breadth-first search.

Depth-first search memulai penelusurannya pada titik sebarang dengan menandainya sebagai titik yang sudah dikunjungi. Pada setiap iterasi yang dilakukan, algoritmanya melanjutkan ke titik yang belum dikunjungi dan yang berdekatan dengan titik yang didiaminya saat itu. Proses ini terus berlanjut hingga menemui titik akhir-sebuah titik yang tidak memiliki titik berdekatan yang belum dikunjungi-. Pada titik akhir, algoritma tersebut kembali satu tingkat ke titik tempat dia berasal dan mencoba untuk lanjut mengunjungi titik yang belum dikunjungi dari titik tersebut. Algoritma mendadak akan terhenti setelah tiba kembali di titik permulaan, dengan titik-titik lain sudah menjadi titik akhir. Dengan begitu, semua titik yang terhubung pada komponen yang sama dengan titik permulaan sudah dikunjungi. Jika masih ada titik-titik yang masih belum dikunjungi, pencarian harus diulang dari salah satu titik-titik pada komponen yang belum dikunjungi tersebut.

Berbeda dengan depth-first search yang bergerak semakin menjauh dari titik permulaanya, breadth-first search bergerak secara terkonsentrasi dengan mengunjungi semua titik-titik yang berdekatan dengan titik permulaan, kemudian berlanjut ke titik-titik di tingkat bawahnya, begitu seterusnya hingga semua titik yang terhubung pada komponen yang sama dengan titik pertama berhasil dikunjungi. Jika masih ada titik yang belum dikunjungi, algoritmanya harus diulang dari sebarang titik pada komponen lain dari graf.

Operasi depth-first search dan breadth-first search memiliki efisiensi yang sama dilihat berdasarakan kedekatan representasi matriks dan kedekatan representasi list.

Exhaustive Search

Exhaustive search adalah teknik pencarian solusi secara brute force untuk masalah yang melibatkan pencarian elemen dengan sifat tertentu, seperti optimasi panjang jarak tempuh dan optimasi anggaran biaya. Pertama, tiap elemen dari ruang lingkup permasalahan yang ada dibangkitkan, kemudian dipilih elemen-elemen yang memenuhi semua syarat dari semua elemen yang telah dibangkitkan tersebut, baru kemudian dilakukan pencarian terhadap elemen yang diinginkan. Meskipun algoritma exhaustive search secara teoritis menghasilkan solusi, namun waktu atau sumberdaya yang dibutuhkan dalam pencarian solusinya sangat besar.

Kelebihan dan Kekurangan Brute Force

Metode brute force yang terkenal dengan kesederhanannya memiliki kelebihan-kelebihan sebagai berikut.

Metode brute force dapat digunakan untuk memecahkan hampir sebagian besar masalah (wide applicability).

Metode brute force sederhana dan mudah dimengerti.

Metode brute force menghasilkan algoritma yang layak untuk beberapa masalah penting seperti pencarian, pengurutan, pencocokan string, perkalian matriks.

Metode brute force menghasilkan algoritma baku (standar) untuk tugas-tugas komputasi seperti penjumlahan/perkalian n buah bilangan, menentukan elemen minimum atau maksimum di dalam tabel (list).

Di samping kelebihan-kelebihan yang dimilikinya, metode brute force juga memiliki kekurangan-kekurangan yang antara lain sebagai berikut.

Metode brute force jarang menghasilkan algoritma yang efektif.

Beberapa algoritma brute force lambat sehingga tidak dapat diterima.

Tidak sekonstruktif/sekreatif teknik pemecahan masalah lainnya.

Divide and ConquerDivide and conquer merupakan paradigma umum dalam teknik desain algoritma yang terinspirasi dari para penguasa pada masa kerajaan dan kolonial. Pada umumnya, algoritma divide and conquer bekerja sebagai berikut.

Suatu masalah dibagi ke dalam beberapa kelompok masalah yang berjenis sama, idealnya dengan ukuran yang sama pula.

Kelompok-kelompok masalah tersebut kemudian diselesaikan

Jika diperlukan, solusi dari kelompok-kelompok masalah tersebut dapat digabungkan untuk mendapatkan solusi yang sebenarnya dari masalah awal.

Mergesort

Mergesort merupakan contoh sempurna dari keberhasilan aplikasi teknik divide and conquer. Algoritmanya mengurutkan array A[0..n – 1] yang diberikan dengan membagi dua array tersebut menjadi A[0..[n/2] – 1] dan A[[n/2]..n – 1], mengurutkan mereka secara rekursif, lalu kemudian menyatukan dua array berurut tersebut menjadi sebuah kesatuan array yang berurutan.

Quicksort

Quicksort merupakan salah satu algoritma penting untuk proses sorting yang basisnya menggunakan pendekatan divide and conquer. Tidak seperti mergesort, yang membagi elemen masukan di dalam array sesuai dengan posisi mereka, quicksort membagi elemen tersebut berdasarkan nilai masing-masing elemen. Secara umum, algoritma quicksort membagi array menjadi 2 kelompok array, L dan R, di mana nilai elemen-elemen di kelompok L lebih kecil dibandingkan dengan nilai elemen-elemen di kelompok R. Setelah itu, kelompok L dan R masing-masing diurutkan secara rekursif, dan kemudian kelompok R ditambahkan di akhir kelompok L.

Penelusuran Pohon Biner (Binary Tree)

Sebuah pohon biner T diartikan sebagai sebuah kumpulan titik dengan jumlah tetap yang dapat tidak berisi apa-apa (kosong) atau terdiri dari sebuah akar dan dua pohon terpisah TL dan TR, di mana masing-masing merupakan kelompok tree bagian kiri dan kanan dari akar tersebut.Sesuai dengan pengertian tersebut, banyak permasalahan yang berkaitan dengan pohon biner dapat diselesaikan dengan mengguanakan teknik divide and conquer.

Algoritma divide and conquer yang paling penting untuk pohon biner adalah tiga penelusuran klasik, yaitu: preorder, inorder, dan postorder. Ketiga penelusuran tersebut mengunjungi titik-titik pada pohon biner secara rekursif. Perbedaannya hanya terletak pada waktu kunjungan ke akar.

Pada penelusuran preorder, akar dikunjungi terlebih dahulu sebelum bagian kiri dan kanan pohon (sesuai urutan yang disebutkan).

Pada penelusuran inorder, akar dikunjungi setelah mengunjungi bagian kiri, tetapi sebelum mengunjungi bagian kanan pohon.

Pada penelusuran postorder, akar dikunjungi setelah bagian kiri dan kanan pohon dikunjungi terlebih dahulu (sesuai urutan yang disebutkan).

Kelebihan dan Kekurangan Metode Divide and Conquer

Berikut ini adalah beberapa keuntungan dengan menggunakan algoritma divide and conquer.

Dapat memecahkan permasalahan yang sulit (kompleks)

Dalam masalah pengurutan, algoritma divide and conquer dapat menjadi solusi yang baik untuk mengatasi efisiensi. Sebagai contoh, metode quicksort dan mergesort memiliki dasar algoritma divide and conquer dan dikenal sebagai metode pengurutan yang paling efesien. Efisiensi algoritma divide and conquer bernotasi O(n log n).

Penggunaan algoritma divide and conquer sesuai untuk eksekusi pada mesn multi prosessor, terutama pembagian sistem memori dimana sub-masalah dapat dijalankan pada prosessor yang berbeda.

Permasalahan yang diselesaikan dengan algoritma divide and conquer juga dapat berpengaruh dalam pengaksesan memori, dikarenakan masalah dibagi menjadi beberapa bagian dan setiap bagian diselesaikan dengan solusi yang sama maka dalam pengaksesan memori setiap kelompok masalah diselesaikan cukup dengan mengakses cache memory yang tidak terlalu lambat.

Berikut ini adalaha kelemahan jika menggunakan algoritma divide and conquer.

Sering menggunakan rekursi yang menyebabkan overhead.

Dapat diterapkan dan inferior untuk solusi algoritmik yang lebih sederhana.

Decrease and ConquerTeknik decrease and conquer didasarkan kepada eksploitasi hubungan antara solusi dari sebuah permasalahan yang diberikan dengan solusi dari permasalah an yang lebih kecil dari permasalahan yang sama. Hubungan tersebut dapat dieksploitasi baik secara top down maupun bottom up. Untuk top down biasanya mengarah kepada implementasi rekursif, walaupun untuk beberapa implementasi lain termasuk ke dalam kategori non-rekursif. Sedangkan, untuk bottom up pada umumnya dimplementasikan secara iteratif, dimulai dari solusi untuk permasalahan yang paling kecil, sehingga terkadang disebut juga sebagai pendekatan inkremental.

Ada 3 variasi umum dari teknik decrease and conquer. Pertama, variasi decrease-by-a-constant, pada variasi ini ukuran sebuah instans dibagi dengan konstanta yang sama pada setiap iterasi algoritma. Pada teknik kedua, decrease-by-a-constant-factor, instans masalah dikurangi dengan faktor konstanta yang sama pada setiap iterasi algoritma. Kemudian, pada variasi terakhir, variable-size-decrease, pola reduksi ukuran berbeda-beda untuk tiap-tiap iterasi algoritma.

Insertion Sort

Salah satu dari beberapa algoritma sorting menggunakan pendekatan decrease and conquer dalam pemecahan masalahnya. Algoritma dengan pendekatan ini mengasumsikan bahwa permasalahan yang berukuran lebih kecil dari array A[0..n – 1] ,yaitu A[0..n – 2] sudah terurut, sehingga untuk mengurutkan seluruh elemen A[0..n – 1] dilakukan dengan menyisipkan elemen A[n – 1] ke posisi yang benar dengan menggunakan salah satu dari tiga cara berikut.

Mencari dari kiri ke kanan sampai ditemukan elemen yang lebih besar sama dengan A[n – 1] dan memasukkan elemen A[n – 1] di sisi kiri elemen tersebut.

Mencari dari kanan ke kiri sampai ditemukan elemen yang lebih kecil sama dengan A[n – 1] dan memasukkan elemen A[n – 1] di sisi kanan elemen tersebut.

Menggunakan teknik binary search untuk mendapatkan posisi yang tepat untuk memasukkan elemen A[n – 1].

Dikarenakan terdapat elemen yang dimasukkan ke dalam array, maka algoritma ini dikenal sebagai insertion sort.

Binary Search

Binary search merupakan sebuah algoritma yang benar-benar efisien untuk melakukan pencarian pada array yang sudah terurut. Cara kerjanya dengan membandingkan sebuah kunci pencarian K dengan elemen tengah array A[m]. Jika keduanya cocok, maka algoritma berhenti, dengan kata lain operasi yang sama diulang secara rekursif pada setengah selang pertama dari array jka K < A[m], dan untuk setengah selang kedua jika K > A[m].

Kelebihan dan Kekurangan Metode Decrease and Conquer

Kelebihan dari metode decrease and conquer terletak pada implementasinya yang dapat dilakukan secara rekursif (top down) maupun iterasi (bottom up). Seringkali algoritma yang dihasilkan sari metode ini sangat efisien. Meskipun begitu, kurang berlakunya metode ini secara luas (terutama penurunan oleh faktor konstan) menjadi hambatan bagi metode ini untuk menyelesaikan masalah tertentu.