Abstrac
Selama ini metode dasar yang digunakan dalam menyelesaikan semua
masalah dengan cara yang sangat sederhana adalah algoritma Brute Force. Metode Brute force yang khusus mencari solusi dari objek-objek dengan kriteria tertentu adalah Algoritma Exhaustive Search. Langkah-langkah algoritma Exhaustive Search yaitu mencoba semua kemungkinan solusi yang ada, sehingga solusi terbaik secara pasti akan ditemukan. Namun kelemahan dari Exhaustive Search dalah kompleksitas waktu yang besar sehingga tidak dapat digunakan untuk menyelesaikan masalah dalam jumlah yang besar. Karena itu, perlu adanya teknik heuristik untuk mengatasi hal tersebut.
1. Brute Force
Brute force adalah sebuah pendekatan yang lempang (straight forward) untuk memecahkan suatu masalah, biasanya didasarkan pada pernyataan masalah (problem statement) dan definisi konsep yang dilibatkan.
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).
Algoritma Brute force:
- Mula-mula pattern dicocokkan pada awal teks.
- Dengan bergerak dari kiri ke kanan, bandingkan setiap karakter di alam pattern dengan karakter yang bersesuaian di dalam teks sampai:
— semua karakter yang dibandingkan cocok atau sama (pencarian berhasil), atau
— dijumpai sebuah ketidakcocokan karakter (pencarian belum berhasil)
Bila pattern belum ditemukan kecocokannya dan teks belum habis, geser pattern satu karakter ke kanan dan ulangi langkah 2
Kekuatan dan kelemaham Metode Brute force:
· Kekuatan:
1. Metode brute force dapat digunakan untuk memecahkan hampir sebagian besar masalah (wide applicability).
2. Metode brute force sederhana dan mudah dimengerti.
3. Metode brute force menghasilkan algoritma yang layak untuk beberapa masalah penting seperti pencarian, pengurutan, pencocokan string, perkalian matriks.
4. Metode brute force menghasilkan algoritma baku (standard) untuk tugas-tugas komputasi seperti penjumlahan/perkalian n buah bilangan, menentukan elemen minimum atau maksimum di dalam tabel (list).
· Kelemahan:
1. Metode brute force jarang menghasilkan algoritma yang mangkus.
2. Beberapa algoritma brute force lambat sehingga tidak dapat diterima.
3. Tidak sekontruktif/sekreatif teknik pemecahan masalah lainnya.
Contoh Listing program
| procedure PencocokanString(input P : string, T : string, n, m : integer, output idx : integer) { Masukan: pattern P yang panjangnya m dan teks T yang panjangnya n. Teks T direpresentasika sebagai string (array of character) Keluaran: lokasi awal kecocokan (idx) } Deklarasi i : integer ketemu : boolean Algoritma: i¬0 ketemu¬false while (i £ n-m) and (not ketemu) do j¬1 while (j £ m) and (Pj = Ti+j ) do j¬j+1 endwhile { j > m or Pj ¹ Ti+j } if j = m then { kecocokan string ditemukan } ketemu¬true else i¬i+1 {geser pattern satu karakter ke kanan teks } endif endfor { i > n – m or ketemu } if ketemu then idx¬i+1 else idx¬-1 endif |
Kompleksitas algoritma: O(nm) pada kasus terburuk
O(n) pada kasus rata-rata
2. Exhaustive Search
Pencarian solusi terbaik dari objek-objek dengan kriteria tertentu dengan menggunakan algoritma Exhaustive Search adalah dengan mencari semua kombinasi dan permutasi dari objek-objek yang ada. Semakin banyak objek, semakin banyak juga kemungkinan solusinya. Biasanya kompleksitas waktu dari algoritma Exhaustive Search masih eksponensial, sehingga algoritma ini cenderung untuk dihindari walaupun solusi yang ditemukan adalah solusi yang memang benar-benar terbaik.
Untuk mempercepat pencarian solusi dengan Exhaustive Search dapat digunakan suatu teknik yang disebut teknik heuristik (heuristic). Teknik ini meliputi salah satunya adalah mengeliminasi kemungkinan solusi yang tidak mungkin menjadi solusi terbaik, ataupun mengadopsi metode lain.
Exhaustive search adalah teknik pencarian solusi secara solusi brute force untuk masalah yang melibatkan pencarian elemen dengan sifat khusus, biasanya di antara objek-objek kombinatorik seperti permutasi, kombinasi, atau himpunan bagian dari sebuah himpunan.
- Langkah-langkah metode exhaustive search:
1. Enumerasi (list) setiap solusi yang mungkin dengan cara yang sistematis.
2. Evaluasi setiap kemungkinan solusi satu per satu, mungkin saja beberapa kemungkinan solusi yang tidak layak dikeluarkan, dan simpan solusi terbaik yang ditemukan sampai sejauh ini (the best solusi found so far).
3. Bila pencarian berakhir, umumkan solusi terbaik (the winner)
· Meskipun algoritma exhaustive secara teoritis menghasilkan solusi, namun waktu atau sumberdaya yang dibutuhkan dalam pencarian solusinya sangat besar.
Contoh. Misalkan kita mempunyai tiga pelanggan dengan
t1 = 5, t2 = 10, t3 = 3,
maka enam urutan pelayanan yang mungkin adalah:
Urutan T
=================================
1, 2, 3: 5 + (5 + 10) + (5 + 10 + 3 ) = 38
1, 3, 2: 5 + (5 + 3) + (5 + 3 + 10) = 31
2, 1, 3: 10 + (10 + 5) + (10 + 5 + 3) = 43
2, 3, 1: 10 + (10 + 3) + (10 + 3 + 5) = 41
3, 1, 2: 3 + (3 + 5) + (3 + 5 + 10) = 29 ¬ (optimal)
3, 2, 1: 3 + (3 + 10) + (3 + 10 + 5) = 34
Pemecahan Masalah dengan Algoritma Exhaustive Search
- Urutan pelangan yang dilayani oleh server merupakan suatu permutasi
- Jika ada n orang pelanggan, maka tedapat n! urutan pelanggan. Waktu yang dibutuhkan untuk mengevaluasi fungsi obyektif adalah O(n), oleh karena itu kompleksitas algoritma exhaustive search untuk masalah ini adalah O(nn!)
- Knapsack
knapsack = karung, kantung, buntilan
Masalah dari Knapsack Problem adalah : “Diberikan n buah objek dan sebuah knapsack dengan kapasitas tertentu (K). Setiap objek memilki property bobot w(weight) dan keuntungan p(profit). Objektif persoalan adalah bagaimana memilih objek-objek yang dimasukkan ke dalam knapsack sehingga tidak melebihi kapasitas knapsack namun memaksimumkan total keuntungan yang diperoleh.” Masalah tersebut dapat diselesaikan dengan menggunakan algoritma Exhaustive Search. Langkah -langkahnya adalah:
1. Misalkan terdapat n objek yang memiliki profit dan berat masing-masing Dan kapasitas knapsack sebanyak Maks.
2. Cari himpunan bagian dari n objek
3. Uji jumlah berat dari himpunan bagian tersebut. Jika beratnya melebihi kapasitas, kembali ke nomor 2. Jika tidak, lanjut ke nomer 3.
4. Uji jumlah profit dari himpunan bagian tersebut. Jika profitnya melebihi profit maksimal sementara, simpan profit baru sebagai profit maksimal dan himpunan bagiannya. Jika tidak, kembali ke nomor 2.
5. Jika seluruh himpunan bagian sudah diuji, himpunan bagian dengan profit maksimal terakhir adalah solusi terbaik dari knapsack
Algoritma tersebut membutuhkan waktu berorde 2n untuk mencari himpunan bagian, dan n untuk masing-masing pengujian berat dan profit. Karena itu, algoritma ini memiliki waktu penyelesaian berorde n2n. Walaupun akan menghasilkan solusi yang benar-benar terbaik, tetapi algoritma ini tidak mungkin digunakan jika objek berjumlah besar. Sebenarnya dalam kasus ini, algoritma Exhaustive Search akan menjadi sangat efisien jika dipadu dengan algoritma runut-balik (backtracking).
Algoritma Runut-Balik (backtracking) adalah algoritma yang berbasis pada Depth First Search yang hanya melakukan pencarian ke arah solusi saja yang dipertimbangkan. Dengan metode ini, kemungkinan solusi yang tidak layak akan dieliminasi secara efektif sehingga waktu yang diperlukan untuk menyelesaikan masalah akan berkurang.
Persoalan: Diberikan n buah objek dan sebuah knapsack dengan kapasitas bobot W. Setiap objek memiliki properti bobot (weigth) wi dan keuntungan(profit) pi. Objektif persoalan adalah memilih memilih objek-objek yang dimasukkan ke dalam knapsack sedemikian sehingga memaksimumkan keuntungan. Total bobot objek yang dimasukkan ke dalam knapsack tidak boleh melebihi kapasitas knapsack.
Solusi persoalan dinyatakan sebagai vektor n-tupel:
X = {x1, x2, …, xn}
xi = 1 jika objek ke-i dimasukkan ke dalam knapsack,
xi = 0 jika objek ke-i tidak dimasukkan.
Formulasi secara matematis:
maksimasi F =
dengan kendala (constraint)
yang dalam hal ini, xi = 0 atau 1, i = 1, 2, …, n
- Aplikasi: masalah pengangkutan barang
- Persoalan 0/1 Knapsack dapat kita pandang sebagai mencari himpunan bagian (subset) dari keseluruhan objek yang muat ke dalam knapsack dan memberikan total keuntungan terbesar.
- Algoritma exhaustive search untuk persoalan 0/1 Knapsack ini adalah:
1. Enumerasikan (list) semua himpunan bagian dari himpunan dengan n objek.
2. Hitung (evaluasi) total keuntungan dari setiap himpunan bagian dari langkah 1.
3. Pilih himpunan bagian yang memberikan total keuntungan terbesar.
Contoh knapsack:
Tinjau persoalan 0/1 Knapsack dengan n = 4. Misalkan objek-objek tersebut kita beri nomor 1, 2, 3, dan 4. Properti setiap objek i dan kapasitas knapsack adalah sebagai berikut
w1 = 2; p1 = 20
w2 = 5; p1 = 30
w3 = 10; p1 = 50
w4 = 5; p1 = 10
Kapasitas knapsack W = 16
Langkah-langkah pencarian solusi 0/1 Knapsack secara exhaustive search dirangkum dalam tabel di bawah ini:
| Himpunan Bagian | Total Bobot | Total keuntungan |
| {} {1} {2} {3} {4} {1, 2} {1, 3} {1, 4} {2, 3} {2, 4} {3, 4} {1, 2, 3} {1, 2, 4} {1, 3, 4} {2, 3, 4} {1, 2, 3, 4} | 0 2 5 10 5 7 12 7 15 10 15 17 12 17 20 22 | 0 20 30 50 10 50 70 30 80 40 60 tidak layak 60 tidak layak tidak layak tidak layak |
- Himpunan bagian objek yang memberikan keuntungan maksimum adalah {2, 3} dengan total keuntungan adalah 80.
- Solusi persoalan 0/1 Knapsack di atas adalah X = {0, 1, 1, 0}
- Berapa banyak himpunan bagian dari sebuah himpunan dengan n elemen? Jawab adalah 2n. Ini berarti, algoritma exhaustive search untuk persoalan 0/1 Knapsack mempunyai kompleksitas O(2n).
- 0/1 Knapsack adalah contoh persoalan yang mempunyai kompleksitas algoritma eksponensial. Knapsack digolongkan sebagai persoalan NP (Non-deterministic Polynomial), karena tidak mungkin dapat ditemukan algoritma polinomial untuk memecahkannya.
Daftar Pustaka
1. Rinaldi Munir, Diktat Kuliah Strategi
Algoritmik, Departemen Teknik
Informatika Institut Teknologi Bandung,
2005.
2. A. Chu and Y. Lin, Parallelization of
Primes in PPP, 2002.
3. M. Agrawal, N. Kayal, and N. Saxena,
PRIMES is in P, 2002
0 komentar:
Posting Komentar