Algoritma Brute Force

Algoritma Brute Force

Brute force adalah sebuah pendekatan yang sangat jelas (straightforward) untuk memecahkan suatu persoalan, biasanya didasarkan pada problem statement dan definisi konsep yang dilibatkan. Algoritma brute force memecahkan masalah dengan sangat sederhana, langsung dan dengan cara yang jelas. Algoritma brute force adalah algoritma yang memecahkan masalah dengan sangat sederhana, langsung, dan dengan cara yang jelas (obvious way). Algoritma brute force adalah algoritma yang lempang atau apa adanya.

contoh-contoh algoritma brute force

a.    Menghitung aⁿ (a > 0, n adalah bilangan bulat tak-negatif)

aⁿ = a x a x ... x a  (n kali), jika n > 0

                            =                                   , jika n = 0

Algoritma: kalikan 1 dengan a sebanyak n kali

b.    Menghitung n! (n bilangan bulat tak-negatif)

N! = 1 x 2 x 3 x ... x n         q          , jika n > 0

                                  =                                               , jika n = 0

Algoritma: kalikan n buah bilangan, yaitu 1,2,3, ..., n, bersama-sama

c.    Mengalikan dua buah matrik yang berukuran n x n.

1.    Minsalnya C = A x B dan elemen-elemen matrik dinyatakan sebagai c_ij, a_ij, dan  b_ij

c_ij = a_i1b_jk + a_i2b_2j + ... + a_inb_nj­ =a_ikb_kj

2.    Algoritma: hitung setiap elemen hasil perkalian satu per satu, dengan cara mengalikan 2 faktor yang panjangnya n.

d.   Menemukan semua faktor dari bilangan bulat n selain dari 1 dan dan n itu sendiri.

Definisi: bilangan bulat a adalah faktor dari bilangan bulat b jika a habis membagi b.

e.    Mencari elemen terbesar atau terkecil

Persoalan: diberikan sebuah himpunan yang beranggotakan n buah bilangan bulat. Bilangan-bilangan bulat tersebut dinyatakan sebagai a­­₁, a₂, ..., a_n. Carikan elemen terbesar didalam himpunan tersebut.

f.      Sequental search

Persoalan: diberikan n buah bilangan a­­₁, a₂, ..., a_n. Carilah apakah x terdapat di dalam himpunan bilangan bulat tersebut. Jika x ditemukan, maka lokasi (indeks) elemen yang bernilai x disimpan didalam peubah idx, jika x tidak terdapat di dalam himpunan tersebut, maka idx diisi dengan nilai 0

g.     Bubble Sort

1.    Apa metode yang paling lempang dalam memecahkan masalah pengurutan? Jawabannya adalah algoritma pengurutan bubble sort.

2.    Algoritma bubble sort

Mengimplementasikan teknik brute force dengan jelas sekali.

h.    Uji Keprimaan

Persoalan: diberi sebuah bilangan bulat positif. Ujilah apakah bilangan tersebut merupakan bilangan prima atau bukan.

i.      Mengghitung nilai polinom secara brute force

Persoalan: hitung nilai polonom

P(x) = a_nxⁿ = a_n-1x^n-1 + ... + a₁x + a₀

Pada titik x = x₀.

j.      Perbaikan (Inprove):

            Adapun  karakteristik Algoritma Brute Force sebagai berikut          

a.    Algoritma brute force sebenarnya bukanlah algoritma yang cerdas dan efesien, karena algoritma brute force membutuhkan jumlah langkah yang  banyak dalam penyelesaiannya dan tentu saja membutuhkan waktu yang berbanding lurus dengan jumlah langkah penyelesaiannya.

b.    Algoritma brute force seringkali merupakan pilihan yang kurang disukai karena kurang efesien, tapi kalau mencari pola2 dasar, keteraturan, atau trik-trik khusus, biasanya dapat membantu untuk menemukan algoritma yang lebih cerdas dan lebih efesien  lagi.

c.    Untuk persoalan-persoalan yang kecil, kesederhanaan brute force lebih diperhitungkan daripada ketidakefesienannya.  Algoritma brute force sering digunakan sebagai basis bila membandingkan beberapa alternatif algoritma yang efesien.

d.   Meskipun brute force bukan merupakan teknik pemecahan masalah yang efesien, namun teknik brute force dapat diterapkan pada sebagian besar persoalan.

Adapun cara Kerja Algoritma brute force adalah sebagai berikut:

a.    Enumerasi (list) setiap solusi yang mungkin dengan cara yang sistematis.

b.    Evaluasi setiap kemungkinan solusi satu per satu dan simpan solusi terbaik yang ditemukan sampai sejauh ini (the best solusi found so far).

c.    Bila pencarian solusi berakhir, umumkan solusi terbaik (the winner).

Tahapan-tahapan yang dilakukan algoritma brute force pada saat mencocokkan string adalah:

1.    Algoritma brute force mulai mencocokkan pattern pada awal teks.

2.    Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:

a.    Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).

b.    Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini.

3.    Algoritma kemudian terus menggeser pattern sebesar satu ke kanan, dan mengulangi langkah ke-2 sampai pattern berada di ujung teks.

Adapun Kekuatan algoritma brute force adalah sebagai berikut:

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

2.    Metode brute force sederhana dan mudah dimengerti.

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

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

Adapun  Kelemaham algoritma  brute force adalah sebagai berikut:

1.    Metode brute force  jarang menghasilkan algoritma yang mangkus.

2.    Beberapa algoritma brute force lambat sehingga tidak dapat diterima.

3.    Tidak sekontruktif atau sekreatif teknik pemecahan masalah yang lainnya.