Nama : Kevin kurniayuda yanuar
NPM : 21312083
Kelas : IF 21 B
berbagai permasalahan yang dapat
diselesaikan dengan Algoritma.
Penyelesaian Berbagai Permasalahan Algoritma dengan Kombinasi Algoritma Brute Force dan Greedy Anggriawan Sugianto 1, David Susanto 2, Zakka Fauzan Muhammad 3 Laboratorium Ilmu dan Rekayasa Komputasi Program Studi Teknik Informatika, Institut Teknologi Bandung (ITB) Kampus ITB Jl Ganesha No. 10 Bandung 1, 2, 3 Abstrak 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. Kata kunci: brute force, greedy, penyelesaian masalah, kombinasi algoritma
1. Pendahuluan 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.
2. Perbandingan Brute Force dan Greedy 2.1. Karakteristik Brute Force dan 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 [1]. 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! [1] Penyelesaian Persoalan dengan Brute Force dan Greedy Persoalan Penukaran Uang Persoalan: Misalkan kita ingin menukarkan uang senilai A dengan sekumpulan uang koin dari berbagai satuan (dengan asumsi tersedia banyak koin 1
