Dinamic Programing bekerja dengan memecahkan submasalah dan menggunakan hasil mereka subproblem untuk lebih cepat menghitung solusi untuk masalah yang lebih besar. Berbeda dengan paradigma membagi-dan-menaklukkan (yang juga menggunakan ide pemecahan submasalah), pemrograman dinamis biasanya melibatkan memecahkan semua submasalah mungkin daripada sebagian kecil.
Seringkali, algoritma pemrograman dinamis yang divisualisasikan sebagai "mengisi array" di mana setiap elemen array adalah hasil dari subproblem yang nantinya dapat digunakan kembali daripada dihitung ulang. Salah satu cara untuk menghitung angka-angka Fibonacci adalah dengan menggunakan fakta bahwa
fibonacci (n) = fibonacci (n-1) + fibonacci (n-2)
Dan kemudian menulis fungsi rekursif seperti
int fibonacci(int n)
{
if(n == 0)
{
return 0;
}
if(n == 1)
{
return 1;
}
else
{
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
Algoritma ini adalah luar biasa lambat (akan memakan waktu eksponensial untuk menjalankan) karena setiap kali fibonacci (n - 1) dihitung, itu akan menghitung ulang setiap nilai fibonacci (n - 2) ke Fibonacci (0). Jantung pemrograman dinamis adalah untuk menghindari semacam ini perhitungan kembali dengan menyimpan hasil. Dalam kasus nomor fibonacci, lainnya, pendekatan yang lebih sederhana ada, tetapi contoh berfungsi untuk menggambarkan ide dasar.
Salah satu penggunaan pemrograman dinamis adalah masalah komputasi "semua pasangan jalur terpendek" dalam graf berbobot. Meskipun algoritma Dijkstra memecahkan masalah untuk satu titik tertentu, itu akan diperlukan untuk menjalankannya untuk setiap vertex, dan akan menjadi algoritma agak rumit. Pemrograman dinamis menghasilkan sederhana, algoritma bersih (meskipun salah satu yang tidak inheren lebih cepat).
Kuncinya di sini adalah untuk menemukan subproblem yang berguna yang, dengan memecahkan, bisa kita gunakan untuk memecahkan masalah yang lebih besar. Dalam hal ini, ternyata bahwa subproblem berguna adalah untuk mempertimbangkan jalur terpendek untuk setiap pasangan simpul yang melewati hanya k simpul pertama. Untuk mempermudah, kami hanya akan berjumlah masing-masing vertex 1 sampai n, di mana n adalah jumlah simpul. Sekarang, setiap subproblem hanya untuk menemukan jarak dari titik i ke simpul j hanya menggunakan simpul kurang dari k.
Kami akan menyimpan jarak dari semua jalur terpendek dari i ke j yang tidak menggunakan k dalam array dua dimensi, D_k, diindeks oleh awal dan akhir simpul, menyimpan nilai dari jalur terpendek hanya menggunakan simpul bernomor kurang dari k sebagai node intermediate. (Ini OK untuk salah satu simpul untuk nomor lebih besar dari atau sama dengan k.)
D_k [i, j] = panjang jalur terpendek dari i ke j akan melalui simpul menengah
kurang dari k
Sekarang, mari kita mengatakan bahwa kita sudah diproses D_k untuk k dari 1 sampai n. Itu berarti kita memiliki semua jalur terpendek dari dua node i dan j mana jalan yang tidak termasuk simpul setiap label yang lebih besar dari n. Sekarang, kita tahu bahwa setiap jalan untuk simpul i ke j yang mungkin termasuk simpul n + 1 adalah baik akan menjadi sama seperti sebelumnya, atau akan menyertakan vertex n + 1, dalam hal jalan harus menjadi kombinasi dari jalan terpendek dari i ke n + 1 dan dari n + 1 untuk j; kedua jalur ini, tentu saja, menggunakan node intermediate kurang dari n + 1 (yaitu, menggunakan D_n [i, n + 1] dan D_n [n + 1, j].
Kita dapat mengungkapkan definisi D_k dalam bentuk berikut (perhatikan bahwa apa pun di kawat gigi hanya sedang dikelompokkan bersama - D_ {k-1} adalah array jarak untuk-k 1, misalnya).
D_k [i, j] = min (D_ {k-1} [i, j], D_ {k-1} [i, k] + D_ {k-1} [k, j])
Setelah definisi dinyatakan dalam format rekursif ini, harus mudah untuk melihat bagaimana ini bisa dikodekan up - kita hanya mengisi array tiga dimensi dengan baris dan kolom untuk setiap vertex dan kedalaman sama dengan jumlah simpul. Tapi kami benar-benar dapat melakukan sedikit lebih baik dari ini! Perhatikan bahwa kita tidak perlu untuk menjaga sekitar lebih dari array saat ini sedang dihitung dan array terakhir dihitung. (Bahkan, ternyata bahwa semua yang kita perlukan adalah satu array, sehingga kami bisa lolos dengan menggunakan O (| V |. ^ 2) ruang) (By the way, ternyata algoritma ini memiliki sebuah name-- itu disebut algoritma Roy-Floyd atau kadang-kadang algoritma Floyd-Warshall.)
Titik kunci untuk mengambil adalah bahwa menggunakan pemrograman dinamis, kita dapat mengurangi masalah untuk menemukan semua jalur terpendek untuk memecahkan serangkaian submasalah yang dapat digunakan kembali lagi dan lagi untuk memecahkan masalah yang lebih besar. Setiap kali Anda mencoba untuk memecahkan masalah dengan menggunakan pemrograman dinamis, berpikir tentang bagaimana Anda dapat mematahkan masalah menjadi subparts - mungkin Anda benar-benar hanya perlu komputer sejumlah kecil subparts (dalam hal ini Anda mungkin dapat menggunakan membagi-dan Pendekatan -conquer, gabungan semacam la) - tetapi jika Anda menemukan bahwa Anda perlu tahu setiap subproblem mungkin, maka pemrograman dinamis dapat menjadi solusi yang tepat.
Hal lain yang perlu diingat adalah bahwa hal itu sering membantu untuk memecahkan versi sederhana dari masalah yang sama sebelum mencoba untuk mengatasi tugas penuh di tangan. Misalnya, Anda mungkin telah memperhatikan bahwa dalam semua-pasangan terpendek masalah jalan, kita benar-benar memecahkan masalah yang sedikit lebih sederhana: apa adalah jarak dari jalur terpendek dari i ke j. Masalah ini sedikit lebih mudah untuk konsep dan menulis kekambuhan untuk. Tapi sekarang bahwa kita memiliki ide, mudah untuk mengubahnya menjadi solusi untuk masalah yang sebenarnya dalam pertanyaan - kami hanya menambahkan array baru yang menyimpan node menengah, k, di mana jalan terpendek meluas. Dengan cara ini, masalah berkurang untuk menemukan jalan terpendek dari i ke k dan dari k ke j, yang kita dapat lagi mengatasi. (Basis terjadi di sini hanya ketika rute antara dua node adalah jalur langsung yang melewati tidak ada simpul tambahan.)
Selain itu, kode untuk pemrograman dinamis dapat sangat sederhana. Pseudocode untuk contoh di atas dapat ditulis dalam hanya beberapa baris, dan ternyata bahwa kita hanya perlu mengisi array tunggal (selama kita mengisi urutan wajar)
.
/* Note that this is c-like pseudo-code */
int D[n][n];
/* initialize D so that each edge, (i, j), has the correct weight at D[i][j]
* and all other elements of the array are set to INFINITY */
/* n is the number of vertices */
for(int k = 0; k < n; k++)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(D[i][j] > D[i][k] + D[k][j])
{
D[i][j] = D[i][k] + D[k][j];
}
}
}
}
Untuk lebih lanjut, silahkan download Ebooknya disini Download Ebook Dinamic Programing
0 Comment: