29
n
x
n
f(x
n
)
f '(x
n
)
x
n+1
0
2.00000
0.18141
1.83229
1.90100
1
1.90100
0.00904
1.64846
1.89552
2
1.89552
2.84668E-5
1.63808
1.89549
3
1.89549
2.862E-10
1.63805
1.89549
Dapat dilihat bahwa metode ini konvergen
dengan sangat cepat, dengan hasil iterasi ke-3
x3 = 1.89549 teliti hingga 9 desimal (x3 = 1.8954942672, akar sebenarnya x = 1.8954942670)
2.11
Pemrograman Dinamis (Dynamic Programming)
Pemrograman dinamis
(dynamic
programming)
adalah
suatu
teknik
pemecahan masalah
(problem
solving)
yang
mencari solusi
untuk suatu
masalah dengan cara
menggabungkan solusi-
solusi
dari
subproblem-subproblem
yang
menyusun
masalah
tersebut.
Metode
ini
biasa
digunakan pada
masalah
optimisasi yang
memiliki optimal
substructure
(substruktur
optimal,
solusi
optimal
dari
keseluruhan
problem
akan
mengandung solusi-solusi optimal
untuk
subproblem-subproblemnya) dan
overlapping
subproblems
(beberapa
dari
subproblem-
subproblem yang
timbul
pada
permasalahan yang
ada
akan
digunakan
lebih
dari
satu
kali).
Metode
ini
ditemukan oleh Richard
Bellman pada
tahun 1953,
sebagai
suatu
metodologi proses
pada
analisis dan
perancangan sistem di
mana
seseorang
perlu
mencari keputusan
yang
terbaik
secara beruntun.
Pada
umumnya,
metode
dynamic
programming
dapat
memecahkan
persoalan
dengan
optimal substructure dalam 3 langkah, seperti disebutkan di bawah ini:
1. Membagi problem yang akan diselesaikan menjadi subproblem-subproblem.
2. Mencari solusi optimal dari subproblem-subproblem tersebut secara rekursif (dengan
menggunakan langkah 1-3 yang disebutkan disini).
 |