Pemrograman Dinamis: Apa Artinya, Cara Kerjanya, dan Sumber Belajar

Pemrograman dinamis adalah konsep yang dikembangkan oleh Richard Bellman, seorang matematikawan, dan ekonom.

Saat itu, Bellman sedang mencari cara untuk memecahkan masalah pengoptimalan yang kompleks. Masalah pengoptimalan mengharuskan Anda memilih solusi terbaik dari serangkaian opsi.

Contoh masalah optimisasi adalah masalah Travelling salesman. Tujuannya adalah untuk menemukan rute terpendek agar penjual dapat mengunjungi setiap kota tepat satu kali dan kembali ke kota awal.

Pendekatan Bellman untuk masalah ini adalah memecahnya menjadi sub-masalah yang lebih kecil dan menyelesaikan sub-masalah dari yang terkecil ke yang terbesar. Dia kemudian menyimpan hasil dari sub-masalah dan menggunakannya kembali untuk menyelesaikan sub-masalah yang lebih besar. Ini adalah ide utama di balik pemrograman dinamis.

Apa itu Pemrograman Dinamis?

Pemrograman dinamis memecahkan masalah optimisasi dengan memecahnya menjadi sub-masalah yang lebih kecil, menyelesaikan setiap sub-masalah satu kali, dan menyimpan solusinya sehingga dapat digunakan kembali dan digabungkan untuk menyelesaikan masalah yang lebih besar. Masalah diselesaikan dari yang terkecil hingga yang terbesar, memungkinkan solusi untuk digunakan kembali.

Bagaimana Pemrograman Dinamis Bekerja?

Memecahkan masalah menggunakan pemrograman dinamis melibatkan langkah-langkah berikut:

1. Tentukan Sub-masalah : Masalah besar dibagi menjadi sub-masalah kecil.
2. Memecahkan Sub-masalah : Ini melibatkan pemecahan sub-masalah yang teridentifikasi, yang dapat dilakukan dengan menggunakan rekursi atau iterasi.
3. Simpan Solusinya : Solusi untuk sub-masalah disimpan agar dapat digunakan kembali.
4. Bangun solusi untuk Masalah Asli : Solusi untuk masalah besar dibangun dari sub-masalah yang telah dihitung.

Untuk melihat aksinya, kami menghitung angka Fibonacci ke-6, F(6), menggunakan proses ini.

Pertama, tentukan sub-masalah yang perlu dipecahkan.

F(n) = F(n-1) + F(n-2) untuk n > 1

Oleh karena itu: F(6) = F(5) + F(4)

F(5) = F(4) + F(3)

F(4) = F(3) + F(2)

F(3) = F(2) + F(1)

F(2) = F(1) + F(0)

F(1) = 1

F(0) = 0

Langkah kedua melibatkan pemecahan setiap sub-masalah menggunakan fungsi rekursif atau proses iteratif. Kami memecahkan sub-masalah dari yang terkecil hingga terbesar, menggunakan kembali hasil dari sub-masalah yang lebih kecil. Ini memberi kita yang berikut:

F(0) = 0

F(1) = 1

F(2) = F(1) + F(0) = 1 + 0 = 1

F(3) = F(2) + F(1) = 1 + 1 = 2

F(4) = F(3) + F(2) = 2 + 1 = 3

F(5) = F(4) + F(3) = 3 + 2 = 5

F(6) = F(5) + F(4) = 5 + 3 = 8

Saat kami menyelesaikan setiap sub-masalah, kami menyimpan solusi dalam array atau tabel sehingga dapat digunakan kembali dalam menyelesaikan sub-masalah yang lebih besar seperti:

Setelah semua sub-masalah diselesaikan, kami menggunakan solusi untuk membangun solusi untuk masalah asli.

Dalam kasus ini, solusi untuk masalah awal adalah bilangan Fibonacci ke-6, yang ditemukan dengan menjumlahkan hasil F(5) dan F(4), sub-masalah yang diidentifikasi dari masalah terbesar. Hasilnya memberi kita 8.

Di mana dan Mengapa Pemrograman Dinamis Digunakan?

Pemrograman dinamis digunakan di area di mana kita memiliki masalah yang dapat dibagi menjadi sub-masalah yang lebih kecil, dan solusinya digunakan untuk menyelesaikan masalah yang lebih besar.

Bidang-bidang ini termasuk ilmu komputer, ekonomi, matematika, dan teknik. Dalam ilmu komputer, ini digunakan untuk memecahkan masalah yang melibatkan urutan, grafik, dan nilai bilangan bulat dan dalam pemrograman kompetitif.

Di bidang ekonomi, ini digunakan untuk memecahkan masalah optimisasi di bidang keuangan, produksi, dan alokasi sumber daya. Dalam matematika, pemrograman dinamis digunakan dalam teori permainan, statistik, dan probabilitas, di mana ia digunakan untuk memecahkan masalah pengoptimalan.

Dalam teknik, digunakan untuk memecahkan masalah dalam alokasi sumber daya, penjadwalan, manufaktur, komunikasi, dan sistem kontrol.

Ada beberapa keuntungan menggunakan pemrograman dinamis untuk menyelesaikan masalah optimisasi:

1. Efisiensi : Pemrograman dinamis dapat lebih efisien daripada algoritme pengoptimalan lainnya karena menghindari penghitungan ulang masalah serupa beberapa kali.
2. Memecahkan Masalah Besar : Pemrograman dinamis ideal untuk masalah pengoptimalan besar yang tidak mungkin diselesaikan menggunakan metode lain. Ini karena memecah masalah menjadi masalah yang lebih kecil yang mengurangi kerumitannya.
3. Solusi Optimal : Algoritma pemrograman dinamis dapat menemukan solusi optimal untuk suatu masalah jika sub-masalah dan tujuan didefinisikan dengan benar.
4. Kesederhanaan: Algoritme pemrograman dinamis mudah diterapkan dan dipahami, terutama jika masalahnya dapat didefinisikan dalam urutan tertentu.
5. Ekstensibilitas: Algoritma pemrograman dinamis dapat dengan mudah diperluas untuk menyelesaikan masalah yang lebih kompleks dengan menambahkan sub-masalah tambahan dan memodifikasi tujuan masalah.

Dalam memecahkan masalah pengoptimalan, pemrograman dinamis adalah alat yang sangat berguna untuk memastikan efisiensi dalam solusi.

Pendekatan yang Digunakan dalam Pemrograman Dinamis

Dalam pemrograman dinamis, dua pendekatan digunakan untuk menyelesaikan masalah optimisasi. Ini adalah pendekatan top-down dan pendekatan bottom-up.

Pendekatan atas ke bawah

Pendekatan ini juga dikenal sebagai memoisasi. Memoisasi adalah teknik pengoptimalan yang terutama digunakan untuk membuat program komputer lebih cepat dengan menyimpan hasil pemanggilan fungsi di cache dan mengembalikan hasil yang di-cache saat dibutuhkan daripada menghitungnya lagi.

Pendekatan top-down melibatkan rekursi dan caching. Rekursi melibatkan fungsi yang menamakan dirinya dengan versi yang lebih sederhana dari masalah sebagai argumennya. Rekursi digunakan untuk memecah masalah menjadi sub-masalah yang lebih kecil dan menyelesaikan sub-masalah.

Setelah sub-masalah diselesaikan, hasilnya di-cache dan digunakan kembali setiap kali masalah serupa terjadi. Top-down mudah dipahami dan diterapkan dan hanya memecahkan sub-masalah satu kali. Kelemahannya, bagaimanapun, adalah membutuhkan banyak memori karena rekursi. Hal ini dapat menyebabkan kesalahan stack overflow.

Pendekatan dari Bawah ke Atas

Pendekatan bottom-up, juga dikenal sebagai tabulasi, menghilangkan rekursi, menggantikannya dengan iterasi, sehingga menghindari kesalahan stack overflow.

Dalam pendekatan ini, masalah besar dipecah menjadi sub-masalah yang lebih kecil, dan solusi untuk sub-masalah tersebut digunakan untuk menyelesaikan masalah yang lebih besar.

Sub-masalah yang lebih kecil pertama-tama diselesaikan dari yang terbesar ke terkecil, dan hasilnya disimpan dalam matriks, larik, atau tabel, oleh karena itu dinamakan tabulasi.

Hasil yang disimpan memecahkan masalah yang lebih besar yang bergantung pada sub-masalah. Hasil dari masalah asli kemudian ditemukan dengan memecahkan sub-masalah terbesar menggunakan nilai yang telah dihitung sebelumnya.

Pendekatan ini memiliki keuntungan karena hemat memori dan waktu dengan menghilangkan rekursi.

Contoh Soal Yang Bisa Diselesaikan Dengan Pemrograman Dinamis

Berikut ini adalah beberapa masalah pemrograman yang dapat diselesaikan dengan menggunakan pemrograman dinamis:

#1. Masalah ransel

Ransel adalah tas yang terbuat dari kanvas, nilon, atau kulit yang biasanya diikat di bagian belakang dan digunakan oleh tentara dan pejalan kaki untuk membawa perbekalan.

Dalam masalah ransel, Anda diberikan sebuah ransel, dan mengingat daya dukungnya, Anda diminta untuk memilih item, masing-masing dengan nilainya. Pilihan Anda harus sedemikian rupa sehingga Anda mendapatkan nilai total maksimum barang yang diambil dan berat barang kurang dari atau sama dengan kapasitas ransel.

Contoh soal knapsack diberikan di bawah ini:

Bayangkan Anda sedang melakukan perjalanan hiking dan memiliki ransel dengan kapasitas 15 kilogram. Anda memiliki daftar barang yang dapat Anda bawa, beserta nilai dan beratnya, seperti yang ditunjukkan pada tabel di bawah ini:

Pilih sebagian barang yang akan dibawa sedemikian rupa sehingga nilai total barang dimaksimalkan sedangkan berat totalnya kurang dari atau sama dengan kapasitas ransel, yaitu 15 kilogram.

Aplikasi dunia nyata dari masalah knapsack melibatkan pemilihan sekuritas untuk ditambahkan ke portofolio untuk meminimalkan risiko dan memaksimalkan keuntungan dan menemukan cara yang paling tidak boros untuk memotong bahan mentah.

#2. Masalah Penjadwalan

Masalah penjadwalan adalah masalah pengoptimalan di mana tujuannya adalah untuk menetapkan tugas secara optimal ke sekumpulan sumber daya. Sumber daya dapat berupa mesin, personel, atau sumber daya lain yang digunakan untuk menyelesaikan tugas.

Contoh masalah penjadwalan diberikan di bawah ini:

Bayangkan Anda adalah manajer proyek yang bertanggung jawab untuk menjadwalkan serangkaian tugas yang harus diselesaikan oleh tim karyawan. Setiap tugas memiliki waktu mulai, waktu berakhir, dan daftar karyawan yang memenuhi syarat untuk menyelesaikannya.

Berikut adalah tabel yang menjelaskan tugas dan karakteristiknya:

Tetapkan setiap tugas kepada karyawan untuk meminimalkan waktu penyelesaian total.

Masalah penjadwalan dapat ditemui di industri manufaktur ketika mencoba mengoptimalkan alokasi sumber daya seperti mesin, bahan, peralatan, dan tenaga kerja.

Hal ini juga dapat ditemui di bidang kesehatan dengan optimalisasi penggunaan tempat tidur, personel, dan perbekalan kesehatan. Industri lain di mana masalah ini dapat terjadi adalah manajemen proyek, manajemen rantai pasokan, dan pendidikan.

#3. Masalah Salesman Keliling

Ini adalah salah satu masalah pengoptimalan yang paling banyak dipelajari yang dapat diselesaikan dengan menggunakan pemrograman dinamis.

Masalah salesman keliling menyediakan daftar kota dan jarak antara setiap pasangan kota. Anda diharuskan untuk menemukan rute terpendek yang mengunjungi setiap kota tepat satu kali dan kembali ke kota asal.

Contoh masalah salesman keliling diberikan di bawah ini:

Bayangkan Anda adalah seorang wiraniaga yang perlu mengunjungi sekumpulan kota dalam waktu sesingkat mungkin. Anda memiliki daftar kota yang perlu Anda kunjungi dan jarak antara setiap pasangan kota, seperti yang ditunjukkan pada tabel di bawah ini:

Masalah penjual keliling dapat ditemui di industri rekreasi saat mencoba merencanakan rute untuk turis, logistik saat merencanakan pengiriman barang, transportasi saat merencanakan rute bus, dan di industri penjualan, antara lain.

Jelas, pemrograman dinamis memiliki banyak aplikasi dunia nyata, yang membantu mempelajarinya lebih lanjut.

Pertimbangkan sumber daya berikut untuk menjelaskan pengetahuan Anda tentang pemrograman dinamis.

Sumber daya

Pemrograman Dinamis oleh Richard Bellman

Pemrograman Dinamis adalah sebuah buku oleh Richard Bellman, yang datang dengan pemrograman dinamis dan mengembangkannya pada tahap awal.

Pratinjau	Produk	Peringkat	Harga
	Pemrograman Dinamis (Buku Dover tentang Ilmu Komputer)	Belum ada peringkat	$17,29	Beli di Amazon

Buku ini ditulis dengan cara yang mudah dipahami yang hanya membutuhkan pengetahuan dasar matematika dan kalkulus untuk memahami teksnya. Dalam buku tersebut, Bellman memperkenalkan teori matematika dari proses pengambilan keputusan bertingkat yang merupakan kunci dalam pemrograman dinamis.

Buku ini kemudian mengkaji masalah bottleneck dalam proses produksi multistage, teorema keberadaan dan keunikan, serta persamaan persediaan yang optimal.

Hal terbaik tentang buku ini adalah bahwa Bellman menawarkan contoh banyak masalah kompleks di bidang-bidang seperti logistik, teori penjadwalan, teori komunikasi, ekonomi matematika, dan proses kontrol dan menunjukkan bagaimana pemrograman dinamis dapat memecahkan masalah tersebut.

Buku ini tersedia dalam versi Kindle, hardcover, dan paperback.

Mata Kuliah Magister Algoritma Pemrograman Dinamis

Kursus Magister Algoritma Pemrograman Dinamis oleh Udemy ini ditawarkan oleh Apaar Kamal, seorang insinyur perangkat lunak di Google, dan Prateek Narang, yang juga bekerja dengan Google.

Kursus ini dioptimalkan untuk membantu pembelajar unggul dalam kompetisi pemrograman yang menampilkan banyak masalah yang membutuhkan pemrograman dinamis.

Selain dari pesaing pemrograman, kursus ini ideal untuk pemrogram yang ingin meningkatkan pemahaman mereka tentang algoritme dan orang-orang yang mempersiapkan wawancara pemrograman dan putaran pengkodean online.

Kursus, yang berdurasi lebih dari 40 jam, mencakup pemrograman dinamis secara mendalam. Kursus pertama menawarkan penyegaran pada konsep-konsep seperti rekursi dan backtracking.

Ini kemudian mencakup pemrograman dinamis dalam teori permainan, string, pohon & grafik, eksponen matriks, bitmask, kombinatorik & urutan, masalah partisi, dan pemrograman dinamis multi-dimensi, di antara banyak konsep lainnya.

Esensi Pemrograman Kompetitif, Master Algoritma

Udemy menawarkan Kursus Penting Pemrograman Kompetitif oleh Prateek Narang dan Amal Kamaar yang mencakup pemrograman dinamis, matematika, teori bilangan, dan struktur data lanjutan & algoritme dengan cara yang berguna dan relevan bagi pemrogram kompetitif.

Kursus ini menawarkan penyegaran pada struktur data dan algoritme sebelum mempelajari algoritme dan teknik yang lebih kompleks yang berguna dalam pemrograman kompetitif.

Kursus ini mencakup pemrograman dinamis, matematika, teori permainan, pencocokan pola, Bitmasking, dan segudang algoritma canggih yang digunakan dan diuji dalam kompetisi pemrograman.

Kursus Udemy dibagi menjadi 10 modul dan 42 bagian dan menyediakan banyak soal latihan setelah setiap bagian. Kursus terlaris ini harus dimiliki oleh siapa saja yang tertarik dengan pemrograman kompetitif.

Kata Akhir

Pemrograman dinamis adalah keterampilan yang bermanfaat bagi programmer mana pun untuk belajar meningkatkan pemecahan masalah mereka dari masalah dunia nyata. Oleh karena itu, pemrogram harus mempertimbangkan melalui sumber daya yang disarankan untuk menambahkan alat penting ini ke kotak peralatan mereka.

Selanjutnya, Anda dapat memeriksa bahasa pemrograman untuk digunakan dalam ilmu data.