Algoritma Brute Force

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 praktik, 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:

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:
1. Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).
2. 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.

Definisi Brute Force

Brute force : pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah. Biasanya didasarkan pada:

·         pernyataan masalah (problem statement)

·         definisi konsep yang dilibatkan.

 Algoritma brute force memecahkan masalah dengan sangat sederhana, langsung, jelas (obvious way).

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

2. 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 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 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).

3. Cara kerja

Secara sistematis, langkah-langkah 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:
1. Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).
2. 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.

Jadi secara keselurhuan cara kerjanya yaitu: 

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

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

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

Contoh-contoh algoritma Brute Force:

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

an = a x a x … x a (n kali) , jika n > 0

= 1 , jika n = 0

Algoritma: kalikan 1 dengan a sebanyak n kali

2. 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

3. Mengalikan dua buah matrik yang berukuran n × n.

Misalkan C = A × B dan elemen-elemen matrik dinyatakan sebagai cij, aij, dan bij

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

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

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

5. Mencari elemen terbesar (atau terkecil)

Persoalan: Diberikan sebuah himpunan yang beranggotakan n buah bilangan bulat. Bilangan-bilangan bulat tersebut dinyatakan sebagai a1, a2, …, an. Carilah elemen terbesar di dalam himpunan tersebut.

6. 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.

7. 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.

8. Uji keprimaan

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

9. Menghitung nilai polinom secara brute force

Persoalan: Hitung nilai polinom

p(x) = anxn + an-1xn-1 + … + a1x + a0

pada titik x = x0.

Contoh Java code nya algoritma  brute force dari sekian banyak yang ane bahas :

BUBBLE SORT

 Misalkan kita mempunyai sebuah array dengan elemenelemen “4 2 5 3 9”. Proses yang akan terjadi apabila digunakan algoritma bubblesort adalah sebagai berikut .  Pass pertama
(4 2 5 3 9) menjadi (2 4 5 3 9)
(2 4 5 3 9) menjadi (2 4 5 3 9)
(2 4 5 3 9) menjadi (2 4 3 5 9)
(2 4 3 5 9) menjadi (2 4 3 5 9) 
Pass kedua
(2 4 3 5 9) menjadi (2 4 3 5 9)
(2 4 3 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9) 
Pass ketiga
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)

selanjutnya bagaimanakah implementasinya dalam bahasa pemrograman java oke langsun aja gan..!!!

 /**
 *
 * @author Edi Zhou
 */
import java.util.Scanner;
public class pengurutan { 
    int[] angka=new int[5];
    public pengurutan()
    {
        Scanner input = new Scanner(System.in);
        for(int i=0;i<5 br="" i="">         {
            System.out.print("Masukkan Angka ke "+(i+1)+" : ");
            angka[i] = input.nextInt();
        } 
        tampilkanAngka();
        urutkanAngka();
        tampilkanAngka(); 
    
    } 
    void tampilkanAngka()
    {
        System.out.println("\n--------------------------------");
        for (int i=0;i<5 br="" i="">         {
            System.out.print(angka[i]+" ");
        }
    } 
    void urutkanAngka()
    {
        int tampung;
        for (int i=0;i         {
            for(int j=0;j             {
                if(angka[j]>angka[j+1])
                {
                    tampung=angka[j];
                    angka[j]=angka[j+1];
                    angka[j+1]=tampung;
                } 
            }
        
        } 
    } 
    public static void main(String[] aksi)
    {
        pengurutan urut = new pengurutan();
    }

Sekian semoga bermanfaat,,!!


sumber : http://ardiansyaha.blogspot.co.id/2015/01/algoritma-brute-force.html