Algoritma Brute Force

Definisi Brute Force

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

Karakteristik Algoritma Brute Force : 

• Algoritma brute force umumnya tidak “cerdas” dan tidak mangkus, 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 ketidakmangkusannya itu, tetapi dengan mencari pola-pola yang mendasar, keteraturan, atau trik-trik khusus, biasanya akan membantu kita menemukan algoritma yang lebih cerdas dan lebih mangkus.

• Untuk masalah yang ukurannya kecil, kesederhanaan brute force biasanya lebih diperhitungkan daripada ketidakmangkusannya. Algoritma brute force sering digunakan sebagai basis bila membandingkan beberapa alternatif algoritma yang mangkus. 

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

Contoh algoritma pencocokkan string

Algoritma-algoritma pencocokkan string dapat diklasifikasikan menjadi tiga bagian menurut arah pencariannya.
 
Tiga kategori itu adalah :

• Dari arah yang paling alami, dari kiri ke kanan, yang merupakan arah untuk membaca, algoritma yang termasuk kategori ini adalah:

1. Algoritma Brute Force
2. Algoritma dari Morris dan Pratt, yang kemudian dikembangkan oleh Knuth, Morris, dan Pratt

• Dari kanan ke kiri, arah yang biasanya menghasilkan hasil terbaik secara praktikal, contohnya adalah:

1. Algoritma dari Boyer dan Moore, yang kemudian banyak dikembangkan, menjadi Algoritma turbo Boyer-Moore, Algoritma tuned Boyer-Moore, dan Algoritma Zhu-Takaoka;

• Dan kategori terakhir, dari arah yang ditentukan secara spesifik oleh algoritma tersebut, arah ini menghasilkan hasil terbaik secara teoritis, algoritma yang termasuk kategori ini adalah:

1. Algoritma Colussi
2. Algoritma Crochemore-Perrin

Algoritma brute force dalam pencarian string

Algoritma brute force merupakan algoritma pencocokan string yang ditulis tanpa memikirkan peningkatan performa. Algoritma ini sangat jarang dipakai dalam praktek, namun berguna dalam studi pembanding dan studi-studi lainnya.

Cara kerja

Secara sistematis, langkah-langkah yang dilakukan algoritma brute force pada saat mencocokkan string adalah:
Algoritma brute force mulai mencocokkan pattern pada awal teks.
Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:
Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).
Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini.
Algoritma kemudian terus menggeser pattern sebesar satu ke kanan, dan mengulangi langkah ke-2 sampai pattern berada di ujung teks.
Berikut adalah Algoritma brute force yang sedang bekerja mencari string:

Pseudocode
Pseudocode algoritma brute force ini:
procedure BruteForceSearch
(
input m, n : integer,
input P : array[0..n-1] of char,
input T : array[0..m-1] of char,
output ketemu : array[0..m-1] of boolean
)

Deklarasi:
i, j: integer

Algoritma:
for (i:=0 to m-n) do
j:=0
while (j < n and T[i+j] = P[j]) do
j:=j+1
endwhile
if(j >= n) then
ketemu[i]:=true;
endif
endfor