Berfikir Komputasional adalah cara menyelesaikan permasalahan menggunakan algoritma berfikir yang rasional dan efektif.
Algoritma Greedy dalam konteks yang lebih luas mengenai strategi optimasi berpikir komputasional mencakup beberapa poin kunci sebagai berikut:
1. Definisi Dasar dan Filosofi "Keserakahan"Algoritma Greedy didefinisikan sebagai metode penyelesaian masalah yang selalu memilih keputusan terbaik pada setiap langkah individu, dengan harapan bahwa rangkaian keputusan kecil tersebut akan menghasilkan solusi terbaik secara keseluruhan atau global optimum,. Secara harfiah, istilah greedy berarti "rakus" atau "serakah" karena algoritma ini hanya mengambil keuntungan terbesar yang tersedia saat itu tanpa mempertimbangkan konsekuensi jangka panjang,.
2. Prinsip Kerja dalam Konteks OptimasiDalam spektrum berpikir komputasional, Greedy merupakan salah satu teknik untuk menyelesaikan masalah optimasi, yaitu mencari cara terbaik untuk memecahkan masalah yang memiliki banyak kemungkinan penyelesaian.
Prinsip utamanya adalah:
Lokal Optimal: Membuat keputusan yang paling menguntungkan pada setiap langkah spesifik.Tanpa Menengok ke Belakang (No Backtracking): Pilihan yang sudah diambil bersifat final dan tidak dapat diubah atau dibatalkan di kemudian hari,,.
Penyederhanaan Langkah: Algoritma ini digunakan untuk menyederhanakan proses penyelesaian masalah dengan hanya fokus pada satu pilihan terbaik setiap kali menemukan persimpangan keputusan.
3. Peran algoritma Greedy diposisikan sebagai alternatif dari teknik lain seperti: Brute Force:
Berbeda dengan Brute Force yang mencoba semua kemungkinan (sehingga tidak efisien untuk masalah besar), Greedy jauh lebih cepat karena hanya memilih satu jalur terbaik di setiap langkah,.
Dynamic Programming (DP): Jika Greedy mengambil keputusan instan tanpa melihat masa depan, DP memecah masalah menjadi sub-masalah dan menyimpan hasilnya untuk menjamin solusi optimal global,
Linear Programming (LP): Greedy adalah pendekatan prosedural, sementara LP adalah pemodelan matematika menggunakan fungsi linier dan batasan tertentu untuk optimasi,.
4. Efisiensi dan Jaminan SolusiSecara teknis, algoritma Greedy dikenal sangat efisien dengan kompleksitas waktu yang kecil dan penggunaan memori yang minimal,. Namun, sumber-sumber tersebut menekankan bahwa Greedy tidak selalu menjamin solusi optimal global,. Keputusan terbaik di awal terkadang justru bisa menghalangi tercapainya solusi terbaik di akhir, seperti yang terlihat pada kasus tertentu dalam masalah koin atau masalah tas (0/1 Knapsack),,.
Kelebihan Algoritma Greedy dalam konteks strategi optimasi berpikir komputasional dapat dirangkum ke dalam beberapa poin utama berikut:
Kecepatan dan Efisiensi Waktu: Keunggulan utama algoritma Greedy adalah kecepatannya yang jauh lebih singkat dibandingkan metode lain seperti Brute Force. Hal ini dikarenakan Greedy hanya memilih satu pilihan terbaik di setiap langkah tanpa harus mencoba semua kemungkinan kombinasi. Kompleksitas waktunya biasanya sangat kecil, sering kali berada pada rentang O(NlogN) atau O(N).
Kesederhanaan Implementasi: Algoritma ini dianggap sederhana karena prinsip kerjanya yang lugas: cukup pilih yang terbaik setiap kali menemukan pilihan dan tidak perlu menengok kembali keputusan yang sudah diambil. Strategi ini sangat efektif untuk menyederhanakan langkah-langkah penyelesaian masalah yang kompleks.
Hemat Memori: Dibandingkan dengan Dynamic Programming (DP), Greedy jauh lebih hemat memori. Hal ini terjadi karena Greedy tidak perlu menyimpan tabel hasil perhitungan sub-masalah (memoization/tabulation) yang biasanya membutuhkan ruang penyimpanan besar.Optimalitas pada Masalah Tertentu: Meskipun tidak selalu menjamin solusi global, Greedy selalu menghasilkan solusi optimal pada masalah yang memiliki sifat Greedy Choice Property dan Optimal Substructure.
Contoh nyatanya adalah pada masalah Fractional Knapsack (barang yang boleh dipotong), pemberian uang kembalian dengan sistem pecahan tertentu, serta pengkodean Huffman.Sangat Efektif untuk Masalah Real-Time: Karena sifatnya yang mengambil keputusan instan ("saat ini"), algoritma ini menjadi dasar yang kuat untuk algoritma navigasi seperti Dijkstra dalam mencari jalur terpendek dan penjadwalan aktivitas yang membutuhkan respon cepat.Secara keseluruhan, dalam spektrum strategi optimasi, Greedy diposisikan sebagai solusi yang paling efisien secara sumber daya (waktu dan memori) selama masalah yang dihadapi memang cocok diselesaikan dengan pendekatan langkah demi langkah yang "serakah".
Dalam konteks strategi optimasi berpikir komputasional, 0/1 Knapsack merupakan masalah klasik di mana Dynamic Programming (DP) menjadi solusi utama karena keterbatasan algoritma Greedy,. Berikut adalah pembahasan mengenai 0/1 Knapsack dalam konteks DP berdasarkan sumber yang tersedia:
1. Definisi Masalah 0/1 KnapsackPada masalah 0/1 Knapsack, setiap barang hanya tersedia satu buah dan tidak boleh dipotong atau diambil sebagian,.
Pilihannya hanya dua: mengambil barang tersebut secara utuh (1) atau meninggalkannya (0),. Hal ini berbeda dengan Fractional Knapsack di mana barang boleh dipotong dan bisa diselesaikan secara optimal dengan Greedy,.
2. Mengapa 0/1 Knapsack Membutuhkan DP? Algoritma Greedy sering kali gagal memberikan solusi optimal pada masalah 0/1 Knapsack karena terlalu fokus pada keuntungan lokal (seperti memilih rasio nilai per berat tertinggi) tanpa mempertimbangkan kombinasi barang secara keseluruhan,.
Contoh Kegagalan Greedy: Misalkan kapasitas tas 5 kg dengan barang:A: 1 kg, Nilai $60 (Rasio 60)B: 2 kg, Nilai $100 (Rasio 50)C: 3 kg, Nilai $120 (Rasio 40) Strategi Greedy akan memilih A lalu B (Total Nilai = $160).
Namun, solusi optimal sebenarnya adalah memilih B dan C (Total Nilai = $220).
Dalam kasus ini, DP diperlukan untuk mengevaluasi kombinasi yang lebih baik.
3. Mekanisme Kerja DP pada 0/1 KnapsackDynamic Programming menyelesaikan masalah ini dengan memanfaatkan dua syarat utama: Optimal Substructure (solusi masalah besar dibentuk dari solusi sub-masalah kecil) dan Overlapping Subproblems (menghindari perhitungan berulang pada sub-masalah yang sama).
Evaluasi Pilihan: DP tidak menebak secara instan, melainkan mengevaluasi pilihan untuk setiap barang (i) dan setiap kemungkinan kapasitas (w) menggunakan logika berikut:
DP[i][w]=max(nilai tanpa barang i,nilai dengan barang i)
Penggunaan Tabel (Tabulasi): Hasil dari setiap sub-masalah disimpan dalam sebuah tabel,. Algoritma kemudian memilih kombinasi maksimal dari nilai-nilai yang tersimpan di tabel tersebut untuk memecahkan masalah besarnya.
4. Keunggulan DP dalam Konteks IniMeskipun DP umumnya lebih lambat dan membutuhkan memori lebih besar daripada Greedy, DP dijamin akan menemukan solusi optimal global jika dirancang dengan benar,,.
Dalam konteks 0/1 Knapsack, DP memastikan bahwa tidak ada kombinasi barang yang terlewatkan, sehingga hasil akhirnya selalu yang paling maksimal dibandingkan pendekatan Greedy yang hanya mencari jalur tercepat
Link PDF 1. Berfikir Komputasional Algoritma Greedy, DP dan LP
Link Youtube: Dinamik Programming
Kumpulkan Tugas di sini
Link PDF 1. Berfikir Komputasional Algoritma Greedy, DP dan LP
Link Youtube: Dinamik Programming
Kumpulkan Tugas di sini
