Pengantar Pemrograman Dinamis: Subproblem Tumpang Tindih & Substruktur Optimal

Diterbitkan: 2021-02-08

Daftar isi

pengantar

Mari kita asumsikan bahwa kita memiliki pertanyaan untuk menyelesaikan kuadrat dari 25. Jika kita menghadapi pertanyaan ini untuk pertama kalinya, maka kita dapat menyelesaikannya dengan tangan atau menggunakan kalkulator. Tetapi jika kita sudah pernah melihat pertanyaan ini sebelumnya atau memecahkannya sebelumnya, maka ada kemungkinan kita bisa menjawabnya dengan cepat dengan menghafalnya.

Ini membawa kita pada kesimpulan bahwa, jika kita dapat mengingatnya maka kita dapat melewatkannya lain kali. Pemrograman dinamis bekerja pada konsep yang sama, idenya adalah untuk mengingat hasil perhitungan dan menggunakannya di masa depan jika diperlukan.

Prosedur sederhana dari pemrograman dinamis ini menjadikannya senjata yang kuat bagi seorang programmer untuk menaklukkan pertempuran kode yang efisien.

Sebagai contoh, mari kita asumsikan bahwa kita memiliki pertanyaan yang kompleks dan kita selalu memikirkan solusi yang membagi pertanyaan menjadi submasalah. Tapi kita mungkin terjebak dalam situasi di mana kita akan menghitung submasalah beberapa kali. Di sana kami menggunakan pemrograman dinamis untuk solusi optimal.

Pemrograman dinamis memiliki dua konsep:

Submasalah yang tumpang tindih
Substruktur yang optimal

Submasalah yang Tumpang Tindih

Contoh klasik untuk memahami konsep submasalah yang tumpang tindih adalah program untuk mencetak deret Fibonacci.

Logika deret Fibonacci diberikan oleh “fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)”. Dan menjalankan fungsi ini secara mulus dapat dilakukan dengan menggunakan solusi rekursif, dengan kasus dasar fibonacci(0)=0 dan fibonacci(1)=1.

public static int fibonacci(int n){
jika (n== 0 || n== 1 )
kembali n;
kembali fibonacci(n -1 )+fibonacci(n -2 );
}
public static void main(String[] args){
System.out.print( “Bilangan fibonacci ke-4 adalah “ +fibonacci( 4 ));
}

Katakanlah kita perlu mencetak digit fibonacci ke-4, maka pohon rekursi menjadi

fibonacci(4)

/ \

fibonacci(3) + fibonacci(2)

/ \ / \

fibonacci(2) + fibonacci(1) fibonacci(1) + fibonacci(0)

/ \

fibonacci(1) + fibonacci(0)

Perhatikan bahwa fibonacci(4) adalah digit ke-5 dalam deret fibonacci karena kita mulai dari fibonacci(0). Pada pohon rekursi di atas, kita dapat melihat bahwa fibonacci(2) diulang dua kali. Kami telah mengamati duplikasi di pohon rekursi dengan tinggi 4, sekarang bayangkan kami memiliki panggilan rekursif dengan jumlah yang sangat besar, dan selanjutnya, akan ada pohon rekursi dengan ketinggian yang besar. Dan akan ada banyak perhitungan duplikat seperti itu, yang dikenal sebagai submasalah yang tumpang tindih.

Kami memiliki dua metode untuk menangani (i) tabulasi ini, (ii) memoisasi

Mari kita memahaminya dengan menelusuri implementasinya.

Memoisasi

Pemecahan masalah fibonacci menggunakan metode memoization dapat dilakukan seperti gambar di bawah ini

memo int[] statis;
public static int fibonacci(int n){
jika(memo[n]!=-1)
kembalikan memo[n];
jika(n==0 || n==1){
memo[n]=n;
kembali n;
}
memo[n] = fibonacci(n-1)+fibonacci(n-2);
kembalikan memo[n];
}
public static void main(String[] args){
memo=int baru[5];
untuk(int i=0;i<=4;i++)
memo[i]=-1;
System.out.println(“Bilangan fibonacci ke-4 adalah “+fibonacci(4));
}

Dalam kode di atas, kami membuat file log pemeliharaan atau mempertahankan tabel pencarian dan menyimpan nilai hasil yang dihitung. Karena kami telah mengingat semua nilai yang dihitung, kami dapat menggunakannya di masa mendatang jika diperlukan, sehingga menghindari penghitungan duplikat dan submasalah yang tumpang tindih.

Semua logikanya mirip dengan solusi rekursif, tetapi satu-satunya perbedaan yang kami buat adalah kami mencatatnya dalam array memo sebelum kami mengembalikan nilainya ke metode utama. Satu-satunya kendala untuk algoritma ini adalah kita membutuhkan ruang ekstra berukuran O(n), tetapi kita mengoptimalkan solusi rekursif sebelumnya.

Tabulasi

Metode ini sedikit berbeda dari solusi di atas. Memoisasi mengikuti solusi rekursif yang sama. Tetapi dalam tabulasi, kami mengikuti solusi berulang. Ini juga disebut pendekatan bottom-up. Mari kita lihat penerapan pendekatan bottom-up.

public static int fibonacci(int n){
int tabel[]=baru int[n+ 1 ];
untuk (int i= 0 ;i<=n;i++){
jika (i== 0 || i== 1 )
tabel[i]=i;
lain {
tabel[i]=tabel[i -1 ]+tabel[i -2 ];
}
}
kembali tabel[n];
}
public static void main(String[] args){
System.out.println( “Bilangan fibonacci ke-4 adalah “ +fibonacci( 4 ));
}

Seperti yang kita ketahui bahwa fibonacci(n)=fibonacci(n-1)+fibonacci(n-2), Dalam memoisasi kita mulai dengan pemanggilan fungsi fibonacci(4), dan kemudian kita menyadari bahwa kita belum menghitung nilainya, jadi kita telah menghitung nilainya dan kemudian menyimpannya.

Situasi serupa akan dihadapi oleh panggilan rekursif lebih lanjut seperti fibonacci(3), fibonacci(2). Sekarang itu membuat banyak panggilan rekursif menunggu di tumpukan rekursi, tapi bagaimanapun kita melewatkan duplikasi submasalah yang tumpang tindih.

Kami juga memiliki cara untuk menghitung fibonacci dari 0 ke elemen ke-n secara iteratif dan kemudian mengembalikan elemen fibonacci ke-n. Inilah yang telah kami implementasikan dalam kode di atas. Kode ini juga memiliki persyaratan ruang yang sama O(n).

Checkout: Keterampilan untuk menjadi pengembang tumpukan penuh

Substruktur Optimal

Dalam konsep ini, kita dapat memperoleh solusi optimal untuk suatu masalah hanya jika kita telah secara optimal menyelesaikan submasalah yang sesuai.

Dan contoh klasik dari konsep ini adalah mempertimbangkan traversal antara node dalam grafik.

Mari kita asumsikan bahwa kita memiliki banyak akar dari Telangana ke Delhi. Dan jika kita memiliki rute terpendek yang melewati Nagpur dan Gwalior. Kemudian rute terpendek dari Nagpur ke Delhi Delhi harus melewati Gwalior. Sekarang kita dapat membagi masalah kita menjadi submasalah yaitu Telangana ke Nagpur, Nagpur ke Gwalior, Gwalior ke Delhi.

Dan contoh klasik untuk properti ini adalah urutan umum terpanjang di kedua string. Subsequence berbeda dengan substring. Dalam sebuah subsequence, karakter tidak perlu konsekuen dalam string asli.

Jadi idenya adalah untuk menyelesaikannya dengan menyelesaikan subproblemnya secara optimal. Misalkan n adalah panjang dari barisan persekutuan terpanjang.

Jika n=LCS(kentang, tato), maka n=LCS(kentang,tato)+1 (jika karakter terakhir sama), else n=maksimum(LCS(kentang,tato), LCS(kentang, tato).

static int lcs(String s1, String s2, int m, int n ){
int dp[][] = baru int[m+ 1 ][n+ 1 ];
untuk (int i= 0 ; i<=m; i++){
untuk (int j= 0 ; j<=n; j++){
jika (i == 0 || j == 0 )
dp[i][j] = 0 ;
lain jika (s1.charAt(i -1 ) == s2.charAt(j -1 ))
dp[i][j] = dp[i -1 ][j -1 ]+ 1 ;
lain
dp[i][j] = Math.max(dp[i -1 ][j], dp[i][j -1 ]);
}
}
kembali dp[m][n];
}
public static void main(String[] args){
System.out.println( “panjang barisan barisan terpanjang adalah “ +lcs( “kentang” , “tato” , 6 , 6 ));
}

Dalam kode di atas, kami telah menerapkan logika kami menggunakan metode tabulasi dan menghitung panjang dari urutan umum terpanjang yang ada di kedua string.

Baca Juga: Gaji Full Stack Developer di India

Pelajari Kursus Pengembangan Perangkat Lunak online dari Universitas top dunia. Dapatkan Program PG Eksekutif, Program Sertifikat Tingkat Lanjut, atau Program Magister untuk mempercepat karier Anda.

Kesimpulan

Sekarang setelah Anda sadar menggunakan salah satu teknik yang ampuh untuk menaklukkan pertempuran kode yang efisien, coba terapkan pemrograman dinamis untuk masalah lain dan mulailah memperkuat kemampuan Anda untuk mengkodekan pertanyaan menggunakan pemrograman dinamis.

Sebagai kesimpulan, Kursus Pengembang Full Stack adalah ahli yang sangat terampil yang dapat menangani segala sesuatu yang berkaitan dengan pengembangan web. Skill Full Stack Developer inilah yang membedakannya dengan Frontend dan Backend Developer.

Apa itu pemrograman dinamis?

Sebuah program komputer berisi banyak kode berulang. Ini tidak efisien dan dapat memengaruhi kinerjanya. Dalam hal ini, pemrograman dinamis digunakan. Pemrograman dinamis adalah metode pemecahan masalah yang kompleks dengan memecahnya menjadi sub-masalah yang lebih sederhana, menyelesaikan setiap sub-masalah ini hanya sekali, dan menyimpan solusi mereka menggunakan tabel, yang kemudian dicari setiap kali sub-masalah yang serupa muncul kemudian. solusi dari masalah yang kompleks. Algoritma pemrograman dinamis digunakan untuk menyelesaikan berbagai jenis masalah optimasi di bidang riset operasional, estimasi statistik, pengenalan pola, kecerdasan buatan, pembelajaran mesin, biologi komputasi, dan bidang lainnya.

Apa submasalah yang tumpang tindih dalam pemrograman dinamis?

Submasalah yang tumpang tindih adalah konsep yang digunakan ketika submasalah memiliki solusi yang juga digunakan dalam submasalah lain. Tumpang tindih ini menyebabkan subtugas yang sama diselesaikan lebih dari sekali. Masalahnya adalah menemukan cara untuk menyelesaikan subtugas hanya sekali, dan menggunakan solusi itu untuk mendapatkan solusi dari submasalah lainnya. Algoritma pemrograman dinamis memecahkan masalah ini menggunakan memoisasi. Memoisasi adalah teknik di mana kita menyimpan solusi untuk submasalah sehingga kita tidak harus menyelesaikannya lagi.

Apa substruktur optimal dalam pemrograman dinamis?

Substruktur optimal menyiratkan bahwa solusi optimal untuk suatu masalah terkait dengan solusi optimal untuk masalah yang lebih kecil dalam definisi masalah yang sama. Substruktur yang optimal merupakan persyaratan tambahan yang diperlukan untuk memecahkan masalah atau untuk membuktikan bahwa tidak ada solusi. Dengan substruktur yang optimal, kami dapat membuktikan banyak masalah NP-hard. Pendekatan umum untuk menyelesaikan masalah DP adalah dengan menggunakan matriks pemrograman dinamis untuk menyimpan solusi optimal dari submasalah. Matriks pemrograman dinamis dapat digunakan untuk menyelesaikan masalah DP substruktur optimal yang tidak nol.