Dynamic Programming

Dynamic Programming (selanjutnya disebut “DP” saja) merupakan salah satu teknik perancangan algoritma yang dikembangkan untuk menyelesaikan permasalahan yang sangat kompleks dengan memecah permasalahan tersebut menjadi banyak sub-permasalahan. Perbedaan utama DP dengan Divide and Conquer (selanjutnya disebut “D&C”) adalah pada DP kita menggunakan kembali hasil kalkulasi sub-masalah yang telah dilakukan sebelumnya. Apa artinya?

Untuk mempermudah penjelasan, mari kita selesaikan masalah sederhana yang telah kita bahas berkali-kali: perhitungan bilangan fibonacci. Algoritma untuk menyelesaikan perhitungan fibonacci secara naif adalah seperti berikut:

def fibonacci(n):
    if n <= 2:
        hasil = 1
    else:
        hasil = fibonacci(n - 1) + fibonacci(n - 2)

    return hasil

Algoritma fibonacci sederhana seperti di atas dapat dikatakan sebagai algoritma D&C, karena kita membagikan perhitungan fibonacci ke dua fungsi fibonacci, sampai didapatkan nilai hasil terkecilnya. Pemanggilan fungsi fibonacci di atas dapat digambarkan seperti berikut:

Pemanggilan Fungsi Fibonacci

Perhatikan bagaimana f(n−2)$f(n-2)$ dan f(n−3)$f(n-3)$ dikalkulasikan sebanyak dua kali, dan semakin kita masuk ke dalam pohon pemanggilan, kita akan melihat semakin banyak fungsi-fungsi yang dipanggil berkali-kali. Pendekatan DP menghindari kalkulasi fungsi yang berulang kali seperti ini dengan melakukan memoization, yaitu menyimpan hasil kalkulasi fungsi tersebut dan menggunakan nilai yang disimpan ketika perhitungan yang sama dibutuhkan kembali. Dengan menyimpan hasil kalkulasi seperti ini, tentunya jumlah total langkah perhitungan yang harus dilakukan menjadi berkurang.

Misalnya, kita dapat menyimpan hasil kalkulasi dari fungsi fibonacci tersebut pada sebuah dictionary, seperti berikut:

memo = dict()

def fibonacci_dp(n):
    if n in memo.keys():
        return memo[n]
    elif n <= 2:
        hasil = 1
    else:
        hasil = fibonacci_dp(n - 1) + fibonacci_dp(n - 2)
    memo[n] = hasil
    return hasil

Dengan menyimpan hasil kalkulasi dari fungsi yang telah ada, maka proses pemanggilan fungsi akan menjadi seperti berikut:

Pemanggilan Fungsi Fibonacci Dynamic Programming

Seperti yang dapat dilihat, pohon pemanggilan fungsi terpotong setengahnya! Tentunya perhitungan fibonacci akan menjadi sangat efisien dengan menggunakan fungsi yang baru ini.

Pendekatan lain dalam menghitung fibonacci lagi, yang masih adalah DP, yaitu dengan menghitung nilai fibonacci dari bawah pohon (pada kode sebelumnya kita melakukan perhitungan dari atas pohon):

def fibonacci_dp_bu(n):
   memo = dict()
   for i in range(1, n + 1):
       if i <= 2:
           hasil = 1
       else:
           hasil = memo[i - 1] + memo[i - 2]
       memo[i] = hasil
   return memo[n]

Untuk melihat efek langsung dari ketiga fungsi tersebut, coba jalankan ketiga fungsi tersebut untuk n yang sama, dan lihat perbedaan waktu eksekusinya! Sebagai latihan tambahan, hitung juga kompleksitas dari ketiga fungsi perhitungan fibonacci tersebut.

Mari kita rangkum hal yang telah kita pelajari mengenai DP sejauh ini:

1. DP menyelesaikan masalah dengan memecah masalah menjadi sub-permasalahan.
2. Setiap solusi dari sub-permasalahan yang telah didapatkan disimpan untuk digunakan kembali jika terdapat sub-permasalahan yang sama. Teknik ini dikenal dengan nama memoization.
3. DP tidak harus menggunakan rekursif. Pemecahan sub-permasalahan juga dapat dilakukan dengan iterasi maupun kalkulasi sederhana.

Contoh Aplikasi Dynamic Programming: Text Justification

Kegunaan utama dari DP adalah untuk menyelesaikan masalah optimasi. Permasalahan optimasi artinya permasalahan yang mencari nilai terbaik, baik maksimal maupun minimal, dari sebuah solusi. Salah satu contoh paling praktis dalam penerapan DP model ini adalah algoritma untuk membuat teks rata tengah. Bagaimana cara kerja algoritma ini? Mari kita lihat masalah yang ingin diselesaikan terlebih dahulu.

Pada aplikasi pengolah kata seperti Microsoft Word, biasanya terdapat fitur untuk menentukan kemerataan teks yang ada pada paragraf, seperti yang nampak pada gambar di bawah:

Fitur Pemerataan Teks pada Microsoft Word

Bagaimana kita menentukan kemerataan teks? Secara umum, kemerataan sebuah teks ditentukan oleh beberapa hal berikut:

1. Ukuran dari halaman, yang tentunya akan mempengaruhi berapa lebar maksimal dari sebuah teks.
2. Ukuran setiap kata yang ada dalam teks, untuk menghitung berapa banyak kata yang dapat dimasukkan ke dalam satu baris teks.
3. Ukuran spasi dalam teks, seperti ukuran kata, untuk menghitung jumlah kata yang dapat dimasukkan ke dalam teks.
4. Ukuran karakter-karakter khusus seperti ”!”, ”?”, ”,”,”.”, dan lainnya. Meskipun biasanya berukuran kecil, karakter khusus tetap berperan dalam mengisi ruang tulisan.

Dengan melakukan kalkulasi sederhana dari teks, tentunya kita bisa saja melakukan pemerataan teks dengan mudah. Misalnya, untuk menghitung total teks yang dapat masuk ke dalam sebuah baris tulisan, kita dapat menggunakan persamaan berikut:

ukuran halaman←total ukuran kata+total ukuran spasi+total ukuran simbol$$\text{ukuran halaman}\leftarrow \text{total ukuran kata}+\text{total ukuran spasi}+\text{total ukuran simbol}$$

Sehingga untuk membuat sebuah teks menjadi rata penuh (justified) kita dapat memasukkan setiap kata, spasi, dan simbol satu demi satu sampai kita memenuhi sebuah baris. Jika kata selanjutnya tidak lagi memiliki ukuran yang cukup, maka kita dapat menambahkan spasi di tengah-tengah kata sebelumnya sampai baris penuh, dan lalu berpindah baris.

Secara sederhana, algoritma naif untuk melakukan rata penuh teks adalah seperti berikut:

1. Ambil satu elemen dalam teks, baik berupa kata, simbol, maupun spasi. Masukkan elemen ini ke dalam baris.

2. Hitung ukuran baris sekarang.

3. Ambil satu elemen lagi dalam teks, dan hitung ukurannya.

4. Tambahkan ukuran baris sekarang dengan ukuran elemen berikutnya. Hasil pengukuran ini selanjutnya akan disebut “Ukuran Baris Selanjutnya” atau UBS.

5. Cek nilai UBS:

   1. Jika UBS masih lebih kecil dari lebar halaman, kembali ke langkah 1

   2. Jika UBS sudah lebih dari lebar halaman:

      1. Tambahkan spasi di antara setiap kata dalam baris sampai ukuran baris sama dengan lebar halaman.

Secara kasar, algoritma di atas dapat diimplementasikan seperti kode berikut (yang jelas tidak dapat dijalankan):

def naive_justify(text, page_size):
    next = text.get_next()
    total_size = 0
    next_total_size = total_size + next.size()

    lines = [[next]]
    current_line = 0

    while(!text.empty()):
        while(next_total_size < page_size):
            total_size = next_total_size
            next = text.get_next()
            lines[current_line].push(next)
            next_total_size = total_size + next.size()

        while total_size != page_size:
            add_space(lines[current_line])

        current_line = current_line + 1

Hasil algoritma di atas kurang optimal, karena ketika terdapat kata-kata yang panjang dalam sebuah kalimat, kita terpaksa harus memotong baris terlalu cepat, dan akhirnya menambahkan banyak spasi. Contoh eksekusi dari algoritma di atas dapat dilihat pada gambar berikut:

Hasil Algoritma Pemerataan Teks Sederhana

Perhatikan bagaimana teks “Dynamic Programming”, “dikembangkan untuk”, dan “memecah permasalahan” memiliki spasi yang sangat lebar. Menggunakan DP, kita dapat menghasilkan pemerataan teks yang lebih optimal.

Berdasarkan algoritma sebelumnya yang kita kembangkan, dapat dilihat bagaimana optimasi dari rata penuh sebuah teks terdapat pada kapan kita melakukan pergantian baris. Jika kita mengganti baris terlalu cepat (jumlah kata masih sedikit), maka secara otomatis kita harus menambahkan banyak spasi, yang menyebabkan teks tidak enak dilihat. Untuk mendapatkan jumlah kata yang optimal dalam sebuah baris, kita akan melakukan perhitungan tingkat “keburukan” sebuah kata dalam teks, jika kata tersebut dijadikan pengganti baris. Kita kemudian dapat mencari tingkat keburukan setiap kata yang ada dalam teks, dan mengambil kata yang memiliki tingkat keburukan terendah sebagai tanda berganti baris.

Pengukuran tingkat keburukan teks sendiri tentunya ditentukan oleh jumlah ruang kosong yang ada dari teks sampai ke ujung halaman. Misalnya, pada gambar di bawah kita dapat melihat contoh ruang kosong dari teks sampai ke ujung halaman:

Tingkat Keburukan Teks

Pada gambar di atas, blok berwarna merah berarti tingkat keburukannya tinggi, dan blok berwarna hijau berarti tingkat kebukurannya rendah. Untuk mendapatkan nilai keburukan yang paling kecil dalam sebuah teks, tentunya kita harus menghitung seluruh kombinasi nilai keburukan dari elemen-elemen yang ada dalam teks. Perhitungan kombinasi nilai keburukan ini tentunya merupakan masalah yang tepat untuk algoritma DP, karena setiap perhitungan nilai keburukan pada dasarnya adalah sebuah sub-masalah!

Jadi sekarang kita telah menemukan sub-masalahnya: mencari nilai keburukan dari sebuah elemen. Bagaimanakah kita dapat menggunakan teknik DP untuk menyelesaikan masalah ini? Ketika menghitung kombinasi dari nilai keburukan dari setiap elemen, secara tidak langsung kita akan membangun sebuah Directed Acyclic Graph, seperti yang tampak pada gambar berikut:

DAG dalam Teks

dengan setiap k$k$ merepresentasikan tingkat keburukan dari elemen tersebut. Menggunakan informasi tersebut, kita dapat mencari nilai minimal dari total seluruh nilai keburukan yang ada pada sebuah teks untuk mendapatkan titik penggantian baris yang paling tepat. Untuk merangkum, berikut adalah langkah-langkah untuk algoritma yang sedang kita kembangkan:

1. Ambil setiap elemen dari dalam teks.
2. Untuk setiap elemen yang ada, lakukan: 1. Hitung nilai keburukan dari elemen terhadap elemen-elemen lain dalam teks. 2. Hitung total nilai keburukan yang ada pada elemen yang sedang dicari.
3. Tentukan nilai keburukan minimum dari nilai keburukan seluruh elemen yang telah dihitung pada langkah 2.
4. Ambil elemen yang memiliki nilai keburukan minimum.
5. Ganti baris pada elemen dengan nilai keburukan minimum.

Perhitungan nilai keburukan sendiri dapat dilakukan dengan menggunakan rumus sederhana berikut:

keburukan(i,j)={ukuran baris>lebar halaman(lebar halaman−ukuran baris)3∞$$\begin{array}{r}keburukan(i,j)=\{\begin{array}{ll}\text{ukuran baris}>\text{lebar halaman}& \mathrm{\infty }\\ (\text{lebar halaman}-\text{ukuran baris}{)}^3\end{array}\end{array}$$

dengan i$i$ dan j$j$ sebagai awal dan akhir dari kata yang ingin dihitung tingkat keburukannya. Jika dijadikan kode program, algoritma tersebut dapat dituliskan seperti berikut:

def length(word_lengths, i, j):
    return sum(word_lengths[i- 1:j]) + j - i + 1


def break_line(text, L):
    # wl = lengths of words
    wl = [len(word) for word in text.split()]

    # n = number of words in the text
    n = len(wl)

    # total badness of a text l1 ... li
    m = dict()
    m[0] = 0

    s = dict()

    for i in range(1, n + 1):
        sums = dict()
        k = i
        while (length(wl, k, i) <= L and k > 0):
            # badness calculation
            sums[(L - length(wl, k, i))**3 + m[k - 1]] = k
            k -= 1
        m[i] = min(sums)
        s[i] = sums[min(sums)]

    return s

Perlu dicatat bahwa kode di atas belum mengikut sertakan spasi dalam perhitungan, dan juga belum membangun kembali baris-baris yang telah dipecah menjadi sebuah teks (paragraf).

Kesimpulan

Secara sederhana, teknik DP dapat dikatakan adalah sebuah teknik brute force yang pintar. Kita memecah-mecah masalah menjadi sub-masalah, dan menyelesaikan seluruh sub-masalah tersebut. Perbedaan utama dari DP dengan D&C adalah DP melakukan penyimpanan hasil penyelesaian sub-masalah sehingga kita tidak perlu menyelesaikan sub-masalah yang sama berulang kali.

source: http://dev.bertzzie.com/

November 16, 2022 Tags : Algoritms , seputar IT , tips Programming

Subscribe by Email

Follow Updates Articles from This Blog via Email