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
 

 

Algoritma greedy

Pengertian Algoritma greedy


Algoritma greedy merupakan jenis algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara pada setiap langkahnya. Nilai maksimum sementara ini dikenal dengan istilah optimum local. Pada kebanyakan kasus, algoritma greedy terkadang tidak akan menghasilkan solusi paling optimal. algoritma greedy biasanya memberikan solusi yang mendekati nilai optimum dalam waktu yang cukup cepat.

Greedy = rakus atau tamak
prinsip dasar dari greedy yaitu " take what you get now " .

Pemecahan masalah dalam Algoritma greedy  dilakukan langkah per langkah (step by step ) . Pada setiap langkah Algoritma Greedy
1. Mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu (berdasarkan Prinsip "take what you can get now ")
2. Berharap bahwa memilih optimum local pada setiap langkah akan berakhir dengan optimum global.

Skema Umum Algoritma Greedy

Algoritma greedy disusun oleh elemen-elemen berikut:

• Himpunan kandidat.

Berisi elemen-elemen pembentuk solusi.

• Himpunan solusi

Berisi kandidat-kandidat yang terpilih sebagai solusi  persoalan.

• Fungsi seleksi (selection function)

Memilih kandidat yang paling memungkinkan mencapai solusi optimal. Kandidat yang sudah dipilih pada suatu langkah tidak pernah dipertimbangkan lagi pada langkah selanjutnya.  

• Fungsi kelayakan (feasible)

Memeriksa apakah suatu kandidat yang telah dipilih dapat memberikan solusi yang layak, yakni kandidat tersebut bersama-sama dengan himpunan solusi yang sudah terbentuk tidak melanggar kendala (constraints) yang ada. Kandidat yang layak dimasukkan ke dalam himpunan solusi, sedangkan kandidat yang tidak layak dibuang dan tidak pernah dipertimbangkan lagi.
              

• Fungsi obyektif 

fungsi yang memaksimumkan atau meminimumkan nilai solusi (misalnya panjang lintasan, keuntungan, dan lain-lain).

Contoh kasus 

Mencari jarak terpendek pada peta

Misalkan kita ingin bergerak dari titik A ke titik B, dan kita telah menemukan beberapa jalur dari peta


Dimisalkan peta  direpresentasikan dengan titik-titik penghubung seperti berikut






dalam peta jarak terpendek sebenarnya



Untuk mencari jarak terpendek dari A ke B, sebuah algoritma greedy akan menjalankan langkah-langkah seperti berikut:

1. Kunjungi satu titik pada graph, dan ambil seluruh titik yang dapat dikunjungi dari titik sekarang.
2. Cari optimum local  ke titik selanjutnya.
3. Tandai graph sekarang sebagai graph yang telah dikunjungi, dan pindah ke local maximum yang telah ditentukan.
4. Kembali ke langkah 1 sampai titik tujuan didapatkan.

Jika mengapliikasikan langkah-langkah di atas pada graph A ke B maka hasil akhir adalah sebagai berikut

Dengan menggunakan algoritma greedy pada graph di atas, hasil akhir yang akan didapatkan sebagai jarak terpendek adalah A-C-D-E-F-B. Hasi jarak terpendek yang didapatkan ini tidak tepat dengan jarak terpendek yang sebenarnya (A-G-E-F-B). Algoritma greedy memang tidak selamanya memberikan solusi yang optimal, dikarenakan pencarian local maximum pada setiap langkahnya, tanpa memperhatikan solusi secara keseluruhan. Gambar berikut memperlihatkan bagaimana algoritma greedy dapat memberikan solusi yang kurang optimal.

Contoh Minimisasi Waktu di dalam Sistem (Penjadwalan)

Persoalan: Sebuah server (dapat berupa processor, pompa, kasir di bank, dll) mempunai n pelanggan (customer, client) yang harus dilayani. Waktu pelayanan untuk setiap pelanggan i adalah ti.
Minimumkan total waktu di dalam sistem:
  
T = (waktu di dalam sistem)
Ekivalen dengan meminimumkan waktu rata-rata pelanggan di dalam sistem.

Tiga pelanggan dengan

t1 = 7,    t2 = 12,     t3 = 5,

Enam urutan pelayanan yang mungkin:
============================================
Urutan        T
============================================                                              
1, 2, 3:    7 + (7 + 12) + (7 + 12 + 5 ) = 50
1, 3, 2:    7 + (7 + 5) + (7 + 5 + 12) = 43
2, 1, 3:    12 + (12 + 7) + (12 + 7 + 5) = 55
2, 3, 1:    12 + (12 + 5) + (12 + 5 + 7) = 53
3, 1, 2:    5 + (5 + 7) + (5 + 7 + 12) = 41 -> (optimal)
3, 2, 1:    5 + (5 + 12) + (5 + 12 + 7) = 46
============================================

Penyelesaian dengan metode greedy

Strategi greedy: Pada setiap langkah, pilih pelanggan yang membutuhkan waktu pelayanan terkecil di antara pelanggan lain yang belum dilayani.

function PenjadwalanPelanggan(input C : himpunan_pelanggan) ® himpunan_pelanggan

{ mengembalikan urutan jadwal pelayanan pelanggan yang meminimumkan waktu di dalam sistem }

Deklarasi

   S : himpunan_pelanggan

   i : pelanggann

Algoritma

  S ¬ {}

  while (C ¹ {}) do

     i ¬ pelanggan yang mempunyai t[i] terkecil

     C ¬ C - {i}

     S ¬ S È {i}    

  endwhile

 

  return S

Agar proses pemilihan pelanggan berikutnya optimal, urutkan pelanggan berdasarkan waktu pelayanan dalam urutan yang menaik.
Jika pelanggan sudah terurut, kompleksitas algoritma greedy = O(n).

procedure PenjadwalanPelanggan(input n:integer)

{ Mencetak informasi deretan pelanggan yang akan diproses oleh server tunggal

  Masukan: n pelangan, setiap pelanggan dinomori 1, 2, …, n

  Keluaran: urutan pelanggan yang dilayani

}          

Deklarasi

   i : integer

Algoritma:

  {pelanggan 1, 2, ..., n sudah diurut menaik berdasarkan t_i}

  for i¬1 to n do

     write(‘Pelanggan ‘, i, ‘ dilayani!’)

  endfor