Algoritma Brute Force

March 24, 2008 at 6:49 pm (programming & algorithm)

Oke sekarang kita coba bahas tentang salah satu teknik algoritma yang sangat banyak dipakai banyak orang terutama untuk persoalan yang tidak memperdulikan masalah efisiensi…, yaitu algoritma brute force.

Sebenarnya secara sadar atau tidak…, kita juga sering berpikir dengan teknik ini, nah sekarang siapkan otak eh… maksudku simak neh ceritanya…

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 .

Cara kerja Algoritma Brute Force

1. Enumerasi (list) setiap solusi yang mungkin dengan cara yang sistematis.
2. Evaluasi setiap kemungkinan solusi “satu per satu” dan simpan solusi terbaik yang ditemukan sampai sejauh ini (the best solusi found so far).
3. Bila pencarian solusi berakhir, umumkan solusi terbaik (the winner)

Karakteristik Algoritma Brute Force

• Algoritma brute force sebenarnya bukanlah algoritma yang “cerdas” dan mangkus(efisien), karena ia membutuhkan jumlah langkah yang besar/banyak dalam penyelesaiannya dan tentu saja membutuhkan waktu yang berbanding lurus dengan jumlah langkah penyelesaiannya. Kadang-kadang algoritma brute force disebut juga algoritma naif (naïve algorithm).
• Algoritma brute force seringkali merupakan pilihan yang kurang disukai karena ketidakmangkusannya itu, tapi kalau mencari pola2 dasar, keteraturan, atau trik-trik khusus, biasanya dapat membantu membantu untuk menemukan algoritma yang lebih cerdas dan lebih mangkus lagi.
• Untuk persoalan2 yang kecil, kesederhanaan brute force lebih diperhitungkan daripada ketidakmangkusannya. Algoritma brute force sering digunakan sebagai basis bila membandingkan beberapa alternatif algoritma yang mangkus.
• Meskipun brute force bukan merupakan teknik pemecahan masalah yang mangkus, namun teknik brute force dapat diterapkan pada sebagian besar persoalan. Bayangkan..,sangat sulit menemukan masalah yang tidak dapat dipecahkan dengan teknik brute force, tapi ada masalah yang hanya dapat dipecahkan secara brute force.

Algoritma bubble sort mengimplementasikan teknik brute force dengan jelas sekali. Berikut contoh persoalan sorting yang dipecahkan dengan algoritma bubble sort:

procedure BubbleSort (input/output L : arrayOfInt, input n : integer) { Mengurutkan array L[1..N] sehingga terurut menaik dengan metode pengurutan bubble sort. Masukan : Array L yang sudah terdefenisi nilai-nilainya. Keluaran: Array L yang terurut menaik sedemikian sehingga L[1]  L[2]  …  L[N]. }

Deklarasi i : integer { variabel untuk jumlah langkah } k : integer { variabel,untuk pengapungan pada setiap langkah } temp : integer { variabel untuk pertukaran }

Algoritma: for i <- 1 to n – 1 do    for j <- n downto i + 1 do {looping menurun}       if (L[j] < L[j-1]) then          {tukar L[j] dengan L[j-1]}          temp <- L[j]          L[j] <- L[j-1]          L[j-1] <- temp       endif    endfor endfor

Setelah kita lihat2 lagi algoritma diatas.., sangat mudah dimengerti. Dengan melooping sebanyak isi array lalu menukarkan nilainya, jika ada nilai yang lebih kecil berada di bawah nilai yang lebih besar, lalu melooping lagi untuk sebanyak jumlah isi array untuk memastikan seluruh kondisi di-cek satu per satu dan menukarkan nilainya kembali jika masih terdapat kondisi seperti diatas dan seterusnya sampai selesai.huh… capek juga ya, coba bayangkan jika banyaknya nilai yang disorting itu mencapai ratusan ribu sampai jutaan jumlahnya hmm… bisa jenggotan juga tuh nunggunya… 😉

Nah sekarang yang menjadi pertanyaan adalah…
Adakah algoritma sorting yang lebih mangkus daripada brute force?? 😀

“Ken Thompson (salah seorang penemu Unix) mengatakan: “When in doubt, use brute force“, faktanya kernel Unix yang asli lebih menyukai algoritma yang sederhana dan kuat (robust) daripada algoritma yang cerdas tapi rapuh.

oh iya… hampir lupa teknik lain yang terkait erat dengan brute force adalah exhaustive search. Brute force maupun exhaustive search sering dianggap dua metode yang sama, padahal dari jenis masalah yang dipecahkan ada sedikit perbedaan(walopun bisa aja dianggap sama…).
Dimana perbedaannya??? ya udah.. kita liat aja entar.. hehehe… 😉