Analisis Dan Desain Algoritma : Algoritma Brute Force, Exhaustive Search, Dan Pendekatan Heuristik
Algoritma Brute Force
Ketika kita dihadapkan dengan suatu problem statement dan diminta untuk menyelesaikan dalam bentuk kode (coding-an), biasanya yang kita lakukan adalah dengan menyelesaikan problem statement tersebut dengan cara paling mudah. Pendekatan ini lazim dikenal sebagai brute force approach atau brute force algorithm.
Algoritma brute force merupakan pendekatan paling mudah dan sederhana ketika menyelesaikan permasalahan. Namun, dibalik kemudahan ini, banyak sumber daya komputasi yang dihabiskan (memori atau waktu eksekusi).
Sebagai contoh, kita diminta untuk memeriksa apakah terdapat elemen pada sebuah list/array yang muncul setidaknya dua kali. Permasalahan ini diselesaikan oleh fungsi yang menerima parameter list/array dengan nilai kembalian boolean. Nilai kembalian fungsi ini adalah true jika terdapat elemen list/array yang muncul lebih dari sekali, dan false sebaliknya.
Solusi dari permasalahan di atas bisa diselesaikan menggunakan pendekatan brute force. Solusi kode dari permasalahan di atas sebagai berikut.
Kode di atas memiliki kompleksitas waktu (time complexity) O(n) dengan kompleksitas ruang (space complexity) O(1). Kompleksitas waktu sebesar O(n) karena kita melakukan iterasi sepanjang list/array, sedangkan kompleksitas ruang sebesar O(1) karena kita hanya mengembalikan nilai boolean yang bersifat konstan.
Algoritma Exhaustive Search
Pada dasarnya, algoritma exhaustive search menggunakan pendekatan brute force untuk menyelesaikan permasalahan. Hanya saja, algoritma exhaustive search menyelesaikan permasalahan kombinatorik, misalnya permasalahan yang berhubungan dengan permutasi dan kombinasi.
Studi kasus yang sering dijadikan contoh penerapan algoritma exhaustive search adalah 1/0 knapsack problem. Studi kasus ini digunakan untuk mencari kombinasi harga maksimal dengan berat tertentu.
Misalnya, kita diberikan list values dan weights dengan values = [60, 100] dan weights = [10, 20], artinya elemen list values yang bernilai 60 memiliki weights 10, dan seterusnya. Kita diminta mencari kombinasi values dengan weights tidak lebih dari 40.
Solusi dalam bentuk kode untuk permasalahan di atas adalah sebagai berikut.
Visualisasi dari permasalahan di atas adalah sebagi berikut.
Lebih lanjut, visualisasi penyelesaian permasalahan di atas dalam bentuk kode adalah sebagai berikut.
Penjelasan gambar di atas adalah sebagai berikut.
- Kita mulai mengeksekusi knapSack(max_weight, weights, value, n) dengan parameter masukan knapSack(40, weights, values, 2), dimana weights dan values adalah list yang telah didefinisikan.
- Permasalahan dipecah menggunakan pendekatan rekursi seperti yang terlihat pada lingkaran nomor 2. Di sebelah lingkaran tersebut, terdapat masing-masing sebuah sub tree yang merepresentasikan 1/0 (diambil atau tidak) elemen dari list value. Sub tree sebelah kiri adalah representasi jika kita mengambil elemen pada list value, dan sub tree sebelah kiri sebaliknya. Jika elemen pada list value diambil, maka nilai max_weights dikurangi dengan nilai elemen list weights dari elemen list value yang berpadanan, dalam hal ini values[1] bernilai 100 dan weights[1] bernilai 20. Jika elemen pada list value tidak diambil, maka nilai max_weights dipertahankan tetap. Selanjutnya, kita menggeser nilai dari n sebesar 1 pada kedua sub tree, sehingga elemen dari list values dan weights yang kita tinjau ikut berubah.
- Permasalahan dipecah lagi pada masing-masing sub tree dengan konsep yang sama : Sub tree sebelah kiri adalah representasi jika kita mengambil elemen pada list value, dan sub tree sebelah kiri sebaliknya. Pada tahap 3 ini, nilai n dikurangi lagi dengan 1, sehingga n bernilai 0. Parameter n yang bernilai 0 ini mengantarkan kita ke base case dimana proses rekursi berhenti ketika max_weights bernila 0 atau n bernilai 0. Parameter n yang bernilai 0 ini secara tidak langsung, juga memberi tahu kita bahwa tidak ada elemen pada kedua list yang bisa kita traverse. Selanjutnya, nilai kembalian ini akan dievaluasi pada parent sub tree menggunakan fungsi max() untuk mengembalikan nilai terbesar.
- Setelah nilai terbesar dari masing-masing sub tree dievaluasi, nilai-nilai tersebut dikembalikan pada fungsi yang ada di langkah 1. Nilai yang dikembalikan sub tree sebelah kiri adalah 160, sedangkan nilai yang dikembalikan sub tree sebalah kanan adalah 60. Kedua nilai ini dievaluasi lagi menggunakan fungsi max(), sehingga fungsi knapSack(40, weights, values, 2) mengembalikan nilai 160.
Kompleksitas waktu untuk penyelesaian knapsack problem menggunakan pendekatan exhaustive search adalah O(2^n), sedangkan kompleksitas ruangnya adalah O(1).
Algoritma Heuristik
Algoritma heuristik adalah algoritma yang diciptakan untuk memangkas sumber daya (memori atau waktu) yang dibutuhkan algoritma exhaustive search untuk menyelesaikan permasalahan
Penyelesaian permasalahan menggunakan algoritma atau pendekatan heuristik tidak membutuhkan pembuktian matematika. Pendekatan heuristik timbul dari intuisi dan tidak perlu memeriksa seluruh solusi. Namun, sebelum menyelesaikan permasalahan menggunakan pendekatan heuristik, ada beberapa faktor yang harus dipertimbangkan, diantaranya :
- Optimality : Ketika beberapa solusi sudah ditemukan, apakah solusi tersebut adalah solusi terbaik? Haruskah mencari solusi lain untuk mendapatkan solusi terbaik?
- Completeness : Ketika beberapa solusi sudah ditemukan, apakah solusi tersebut sudah mencakup semua solusi?
- Accuracy and Precission : Apakah galat/error yang dihasilkan cukup besar? Apakah ada metrik tertentu untuk mengukur galat tersebut?
- Execution Time : Apakah waktu yang dihabiskan pendekatan heuristik lebih banyak dibandingkan dengan waktu yang dihabiskan pendekatan klasik/biasa?
