Pendahuluan
Istilah pemrograman dinamis (dynamic programming) tentunya pernah kita dengar secara literatur, istilah ini banyak kita temui pada buku-buku algoritma komputer, riset operasional, ataupun buku yang berhubungan dengan matematika terapan. Sebagian orang juga mengenal Pemrograman dinamis sebagai suatu metode yang berkaitan dengan prinsip optimalisasi dan dapat diaplikasikan pada bidang industri, perbankan, hingga perencanaan network dan aplikasi perjalanan luar angkasa. Aplikasinya yang luas menjadikan pembahasan mengenai pemrograman dinamis menjadi suatu topik yang umum dan menarik. Untuk mencoba mengetahui lebih lanjut tentang pemrograman dinamis, pada artikel ini akan dibahas tentang dasar-dasar teori pemrograman dinamis secara singkat, juga dengan sejarah singkat dari asal mula istilah pemrograman dinamis.
Bioinformatika, sebagai salah satu bidang multidisiplin yang berkembang dan banyak menerapkan metode komputasi, tentunya menjadi bidang yang cukup terbuka terhadap suatu metode seperti metode pemrograman dinamis, lebih lanjut pada tulisan ini diterapkan aplikasi pemrograman dinamis sebagai metode optimalisasi dalam pemecahan masalah, dan dicontohkan pada masalah bilangan Fibonacci dan graf multitahap, pada akhirnya, sebagai penekanan dalam tulisan ini, adalah aplikasi pemrograman dinamis dalam bidang bioinformatika, khususnya pada algoritma Needleman-Wunsch untuk global sequence alignment.
Pemrograman Dinamis
Istilah Pemrograman Dinamis, pertama kali diperkenalkan pada era 1950-an oleh Richard Bellman seorang professor di Universitas Princeton dan juga bekerja pada RAND corporation, perlu diketahui bahwa
Pemrograman Dinamis merupakan sebuah algoritma pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah atau tahapan sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan. Pada penyelesaian metode ini kita menggunakan persyaratan optimasi dan kendala untuk membatasi sejumlah pilihan yang harus dipertimbangkan pada suatu tahap. Algoritma Program Dinamis memiliki karakteristik sebagai berikut:
1. Persoalan dapat dibagi mejadi beberapa tahap, yang pada setiap tahap hanya diambil satu keputusan yang optimal.
2. Masing-masing tahap terdiri dari sejumlah status yang berhubungan dengan tahap tersebut.
3. Hasil keputusan yang diambil pada tahap ditransformasikan dari status yang bersangkutan ke status berikutnya pada tahap berikutnya.
4. Ongkos pada suatu tahap bergantung pada ongkos tahap-tahap sebelumnya dan meningkat secara teratur dengan bertambahnya jumlah tahapan
5. Keputusan terbaik pada suatu tahap bersifat independen terhadap keputusan yang dilakukan tahap sebelumnya.
6. Adanya hubungan rekursif yang mengidentifikasikan keputusan terbaik untuk setiap status pada tahap k memberikan keputusan terbaik untuk tahap sebelumnya.
7. Prinsip optimalitas berlaku pada persoalan tersebut.
Ciri utama dari Program Dinamis adalah prinsip optimalitas yang berbunyi “jika solusi total optimal, maka bagian solusi sampai tahap ke-k juga optimal”.
Dari karakteristik poin ke-4 di atas, kita dapat menyimpulkan bahwa algoritma Program Dinamis dapat diaplikasikan apabila peningkatkan ongkos secara linear dan diskrit sehingga optimasi parsial dapat dilakukan. Dalam menyelesaikan persoalan dengan Program Dinamis, kita dapat menggunakan 2 pendekatan berbeda yaitu :
a. Maju (forward atau up-down) : bergerak mulai dari tahap 1, terus maju ke tahap 2,3,..,n. Urutan variabel keputusan adalah x1,x2,…,xn
b. Mundur (backward atau bottom-up) : bergerak mulai dari tahap n, terus mundur ke tahap n-1, n-2,..,2,1. Urutan variabel keputusan adalah xn xn-1,x2,x1. Adapun kompleksitas waktu pada algoritma ini adalah O(| s1|*|s2|), jika panjang kedua string adalah ‘n’. Kompleksitas ruangnya juga sama jika seluruh matriks disimpan untuk merunut balik untuk mencari optimal alignment. Jika nilai edit distance dibutuhkan, hanya dua baris dari matriks yang dialokasi, matriks tersebut dapat mengalami ‘daur ulang’, dan kompleksitas ruangnya jadi O(n).
Adapun Dynamic programming adalah strategi untuk membangun masalah optimal bertingkat, yaitu masalah yang dapat digambarkan daalam bentuk serangkaian tahapan (stage) yang saling mempengaruhi. Umumnya tiap tahapan mempunyai 4 (empat) variabel yang mempunyai pengaruh, baik langsung maupun tidak langsung terhadap tahapan lainnya dari sistem
Adapun empat variabel tersebut adalah sebagai berikut :
1. Input untuk tahapan n, Xn, yang tergantung dari keputusan yang dibuat pada tahapan terdahulu atau tergantung dari input asal yang tetap pada system
2. Set keputusan pada tahap n, Dn yang menentukan kondisi atau syarat operasi dari tahapan.
3. Output dari tahapan n, Xn-1 yang biasa tergantung dari input pada tahapan n dan keputusan Dn.
4. Hasil dari tahapan n, Rn yang merupakan ukuran bagi konstribusi tahapan n terhadap fungsi tujuan sistem keseluruhan (ongkos, keuntungan, manfaat atau ukuran lain). Biasanya hasil ini merupakan gambaran dari suatu tahapan n dan output pada tahapan n.
