Algoritma Brute Force
Deskripsi
Materi ini membahas tentang algoritma brute force dengan berbagai studi kasus
Definisi Brute Force Straighforward (lempeng) Sederhana dan jelas Lebih mempertimbangkan solusi dari problem
Tanpa mempertimbangkan efisiensi Dengan cara meminimumkan jumlah operasi
Contoh-contoh Brute Force Menghitung an (a > 0, n adalah bilangan bulat taknegatif) an = a x a x … x a (n kali) , jika n > 0 =1 , jika n = 0 Algoritma: kalikan 1 dengan a sebanyak n kali
Menghitung n! (n bilangan bulat tak-negatif) n! = 1 × 2 × 3 × … × n , jika n > 0 =1 , jika n = 0 Algoritma: kalikan n buah bilangan, yaitu 1, 2, 3, …, n, bersama-sama
Mengalikan dua buah matrik yang berukuran n × n.
Misalkan C = A × B dan elemen-elemen matrik dinyatakan sebagai cij, aij, dan bij n
cij ai 1b1 j ai 2 b2 j ain bnj aik bkj k 1
Algoritma: hitung setiap elemen hasil perkalian satu per satu, dengan cara mengalikan dua vektor yang panjangnya n.
Algoritma Perkalian Matriks procedure PerkalianMatriks(input A, B : Matriks, input n : integer, output C : Matriks) 1 2
for i1 to n do for j1 to n do
3
C[i,j]0
4
for k 1 to n do
5 6 7 8
{ inisialisasi penjumlah }
C[i,j]C[i,j] + A[i,k]*B[k,j] endfor endfor endfor
Mencari elemen terbesar (atau terkecil) Persoalan: Diberikan sebuah himpunan yang beranggotakan n buah bilangan bulat. Bilanganbilangan bulat tersebut dinyatakan sebagai a1, a2, …, an. Carilah elemen terbesar di dalam himpunan tersebut.
Algoritma Cari Elemen Terbesar procedure CariElemenTerbesar (input a1, a2, ..., an : integer, output maks : integer) 1 2 3 4 5 6
maksa1 for k2 to n do if ak > maks then maksak endif endfor
Sequential Search Persoalan: Diberikan n buah bilangan bulat yang dinyatakan sebagai a1, a2, …, an. Carilah apakah x terdapat di dalam himpunan bilangan bulat tersebut. Jika x ditemukan, maka lokasi (indeks) elemen yang bernilai x disimpan di dalam peubah idx. Jika x tidak terdapat di dalam himpunan tersebut, maka idx diisi dengan nilai 0.
Algoritma Pencarian Beruntun procedure PencarianBeruntun (input a1, a2, ..., an : integer, x : integer, output idx : integer) 1 2 3
k1 while (k < n) and (ak x) do k k + 1
4
endwhile
5
{ k = n or ak = x }
6
if ak = x then
7 8 9 10
{ x ditemukan }
idxk else idx 0 endif
{ x tidak ditemukan }
Bubble Sort •
Apa metode yang paling lempang dalam memecahkan masalah pengurutan? Jawabnya adalah algoritma pengurutan bubble sort.
•
Algoritma bubble sort mengimplementasikan teknik brute force dengan jelas sekali.
Algoritma Bubble Sort procedure BubbleSort (input/output L : TabelInt, input n : integer) 1
for i 1 to n - 1 do
2
for k n downto i + 1 do
3
if L[k] < L[k-1] then
4
{pertukarkan L[k] dengan L[k-1]}
5
temp L[k]
6
L[k] L[k-1]
7
L[k-1] temp
8 9 10
endif endfor endfor
Karakteristik Algoritma Brute Force
Mudah diimplementasikan Tidak cerdas dan tidak efektif
Seringkali bukan pilihan yang disukai Dapat ditemukan algoritma yang lebih cerdas dan efektif
Butuh jumlah langkah yang besar Naïve algorithm. Kata “force” mengindikasikan “tenaga” ketimbang “otak”
Dengan mencari pola-pola yang mendasar, keteraturan, atau trik-trik khusus
Kadang brute force lebih tepat daripada algoritma lain, ditinjau dari implementasinya Hampir semua permasalahan dapat diselesaikan dengan brute force
Malah, ada beberapa masalah yang hanya bisa diselesaikan dengan brute force
Kekuatan Metode Brute Force
Digunakan untuk memecahkan hampir sebagian besar masalah (wide applicability). Sederhana dan mudah dimengerti. Menghasilkan algoritma yang layak untuk beberapa masalah penting seperti pencarian, pengurutan, pencocokan string, perkalian matriks. Menghasilkan algoritma baku (standard) untuk tugas-tugas komputasi seperti penjumlahan/perkalian n buah bilangan, menentukan elemen minimum atau maksimum di dalam tabel (list).
Kelemahan Metode Brute Force
Metode brute force jarang menghasilkan algoritma yang efektif Beberapa algoritma brute force lambat sehingga tidak dapat diterima Tidak sekontruktif/sekreatif teknik pemecahan masalah lainnya 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
Latihan
Buatlah suatu algoritma brute force untuk pencocokan string. Persoalan: Diberikan a. teks (text), yaitu (long) string yang panjangnya n karakter b. pattern, yaitu string dengan panjang m karakter (m < n) yang akan dicari di dalam teks. Carilah lokasi pertama di dalam teks yang bersesuaian dengan pattern. Jika pattern/sub-string ditemukan maka return valuenya berupa posisi substring tersebut. Jika sub-string tidak ditemukan maka return valuenya bernilai -1
