Berbagai Permasalahan yang Dapat Diselesaikan Dengan Algoritma

Nama : Rian Pebriawan

NPM : 21312026

Kelas : IF 21A

Fakultas        : https://ftik.teknokrat.ac.id/

Universitas    : https://teknokrat.ac.id/

Pada masa sekarang ini, terdapat banyak sekali cara-cara penyelesaian persoalan yang dapat dilakukan oleh komputer. Mulai dari cara penyelesaian persoalan dengan cara yang mengutamakan kemudahan pemikiran manusia, sederhana, pasti menemukan solusi tetapi memiliki kompleksitas algoritma yang sangat besar seperti penyelesaian dengan brute force dan exhaustive search, penyelesaian dengan mengutamakan kecepatan menemukan satu solusi, yang dianggap optimal, sangat tinggi, seperti algoritma greedy, ataupun algoritmaalgoritma lain yang mengutamakan kemangkusan algoritma tetapi memiliki tingkat kerumitan cukup tinggi, seperti BFS, DFS, Backtracking, Branch and Bound dan dynamic programming. Secara ideal, jika ditemukan penyelesaian suatu permasalahan yang cepat, mudah, kemangkusannya tinggi, dan pasti menemukan solusi, pasti algoritma tersebut akan selalu dipakai, akan tetapi sayangnya sampai saat ini hal tersebut belum dapat terjadi. Pada beberapa kasus, kadang diinginkan algoritma yang mudah (seperti pada brute force ataupun greedy), cepat (seperti pada algoritma greedy), dan sedekat mungkin dengan solusi optimum global (seperti pada brute force). Pada makalah ini akan dibahas penyelesaian masalah dengan menggunakan kombinasi dari algoritma brute force dan freedy, memiliki ketepatan solusi yang cukup optimal dan kecepatan yang cukup tinggi.

Penggunaan algoritma yang tepat pada permasalahan yang tepat (atau pada sebuah program) akan sangat menguntungkan bagi pengguna program tersebut. Dengan penggunaan algoritma yang tepat, waktu yang dibutuhkan untuk penyelesaian suatu permasalahan akan semakin tinggi. Sayangnya, sampai saat ini suatu penyelesaian yang paling sederhana, yaitu algoritma brute force, memiliki kemangkusan yang sangat rendah. Sayangnya lagi, algoritma dengan kemangkusan paling tinggi, yaitu algoritma greedy, memiliki ketepatan penyelesaian yang tidak 100% benar. Penggabungan dari kedua algoritma tadi sangat mungkin dapat menghasilkan sebuah algoritma baru yang lebih mangkus dari brute Force dan lebih optimum dari greedy.

Secara umum, algoritma Brute Force dapat dilihat pada “penampilan luar”-nya (pada source code dan kecepatan program) yang pendek, mudah dimengerti dan membutuhkan cukup banyak waktu (terutama pada program yang besar). Atau dengan bahasa lain, brute force adalah sebuah pendekatan yang lempang (straightforward) untuk memecahkan suatu masalah, biasanya didasarkan pada pernyataan masalah (problem statement) dan definisi konsep yang dilibatkan. Sedangkan algoritma greedy dapat dilihat terutama pada kecepatan program yang sangat tinggi, akan tetapi kadang-kadang hasilnya agak mengecewakan karena tidak sesuai dengan solusi optimum yang diharapkan. Atau dengan kata lain, algoritma greedy membentuk solusi langkah per langkah (step by step), dan prinsip greedy adalah “take what you can get now!”. 

Persoalan: Misalkan kita ingin menukarkan uang senilai A dengan sekumpulan uang koin dari berbagai satuan (dengan asumsi tersedia banyak koin untuk setiap satuan, sehingga tidak mungkin terjadi kekurangan koin). Berapa jumlah minimum koin yang diperlukan tersebut? Contoh: koin-koin yang tersedia bernilai 12, 7, 4, dan 2 (dalam jumlah yang banyak untuk tiap satuan). Bagaimana cara menukarkan uang sebanyak 18 dengan koin-koin tersebut? Dengan sedikit pengetahuan, dapat diketahui bahwa jumlah koin yang diperlukan tidak akan lebih jumlah uang dibagi dengan pecahan terkecil koin dan tidak akan kurang dari jumlah uang dibagi dengan pecahan terbesar koin. Jadi bisa dipastikan bahwa jumlah koin yang diperlukan tidak akan lebih dari 9. Untuk memudahkan, dipergunakan sebuah koin maya bernilai 0, sehingga jika hanya dipilih 2 koin (anggap 12 dan 4) sama seperti dipilih S = {0, 0, 0, 0, 0, 0, 0, 4, 12} dengan S adalah himpunan koinkoin yang diambil. Dengan brute force, dapat dicoba semua kemungkinan pilihan, mulai dari S = {0, 0, 0, …, 0}, S = {0, 0, …, 0, 2}, sampai S = {12, 12, 12, …, 12}, dengan rumus kombinasi berulang, berarti harus dicoba sebanyak 59 = 1.953.125 cara, untuk masingmasing cara, harus dihitung jumlah tiap-tiap elemen himpunan, jika sama dengan 18 diambil, jika tidak dibuang. Berarti jumlah perhitungan yang harus dilakukan adalah sebanyak 2 x 59 ≈ 4.000.000 cara. Pada kondisi akhir, akan diperoleh semua kemungkinan pilihan koin yang bisa dijadikan solusi, yaitu S1 = (0, 0, 0, 0, 0, 0, 2, 4, 12) S2 = (0, 0, 0, 0, 0, 0, 4, 7, 7) S3 = (0, 0, 0, 0, 0, 2, 2, 2, 12) S4 = (0, 0, 0, 0, 0, 2, 2, 7, 7) … Sn = (2, 2, 2, 2, 2, 2, 2, 2, 2) Kemudian dipilihlah solusi yang paling sedikit menggunakan koin nyata, atau dengan kata lain dipilih solusi yang paling banyak menggunakan “koin 0”. Sehingga diperoleh dua solusi yaitu: (2, 4, 12) dan (4, 7, 7). Cara kedua, dengan algoritma greedy, akan dipilih satu koin terbesar dan jumlahnya dengan koin sebelumnya yang telah diambil tidak lebih dari 18 (pada kondisi awal, jumlah koin sebelumnya adalah 0). Langkah-langkah algoritma greedy: 1. Ambil koin 12, jumlah = 12 2. Ambil koin 4, jumlah = 16 3. Ambil koin 2, jumlah = 18 Ditemukan solusi, stop. Sehingga diperoleh satu solusi, yaitu (12, 4, 2). Pada kasus umum, jika diketahui bahwa koin-koin yang tersedia adalah k1 < k2 < … < kn dan uang yang akan ditukarkan adalah u, serta m – 1 < u / k1 ≤ m, m adalah bilangan bulat. Berarti banyak koin tidak akan lebih dari m. Sehingga komplesitas algoritma untuk penyelesaian secara brute force adalah O((n+1)m) ≈ O(nm). Sedangkan untuk algoritma greedy, pemilihan bilangan terbesar yang memenuhi tidak akan memakan waktu lebih dari n, serta banyaknya koin yang dipilih tidak akan lebih dari m, berarti kompleksitasnya adalah O(nm). Dari 2 perhitungan diatas, dapat disimpulkan bahwa penyelesaian secara greedy jauh lebih mangkus daripada penyelesaian secara brute force, meski dalam beberapa kasus lainnya yang tidak dituliskan disini, ada kejadian dimana solusi dari algoritma brute force lebih memuaskan daripada solusi dari algoritma greedy (dan tidak mungkin terjadi sebaliknya), atau bahkan solusi ditemukan hanya dengan algoritma brute force saja, tidak dengan greedy, misalnya koin yang tersedia adalah 12 dan 7 saja sedangkan uang yang ingin ditukarkan adalah 14. 

Persoalan: Misalkan kita diberikan beberapa buah barang dengan keuntungan serta beratnya masingmasing, akan tetapi container yang kita miliki hanya dapat memuat sejumlah berat tertentu. Pilih barangbarang yang akan dibawa sehingga keuntungan yang diperoleh maksimum. Contoh: Terdapat 6 benda (labeli 1 sampai 6), dengan wi adalah berat benda ke-i dan pi adalah keuntungan benda ke-i. w1 = 100 p1 = 40 w2 = 50 p2 = 35 w3 = 45 p3 = 18 w4 = 20 p4 = 4 w5 = 10 p5 = 10 w6 = 5 p6 = 2 Kapasitas knapsack K = 100 Tuliskan solusi sebagai X = (x1, x2, …, x6) dengan xi = 0 jika benda ke-i dibawa atau xi = 1 jika benda ke-i tidak dibawa. Penyelesaian dengan brute force: Coba semua kemungkinan X, mulai X = (0, 0, 0, 0, 0, 0), sampai dengan X = (1, 1, 1, 1, 1, 1). Jumlah kemungkinan yang harus dicoba ada 26 = 64 cara. Tiap cara harus dihitung berat totalnya, dan dari semua cara yang berat totalnya tidak melebihi kapasitas knapsack, pilih satu yang keuntungannya paling besar.