Kuliah di semester enam memang bukan main-main, setiap waktu luang yang saya miliki harus digunakan untuk mengerjakan proyek perangkat lunak. Akibatnya blog ini menjadi kurang terurus. Syukur-syukur kesibukan mengurus proyek itu sudah mulai menurun, dan saya bisa kembali menulis.
Topik yang dibahas kali ini adalah ternary search. Bagi coder pemula, pastinya pernah mendengar istilah binary search. Anda juga mungkin pernah mendengar bahwa jika binary menyatakan dua, maka ternary menyatakan tiga. Jadi yang akan dibahas ini adalah pencarian ternary, yaitu dengan membagi tiga daerah. Kira-kira seperti ini:
Diberikan sebuah fungsi f(x) yang menerima x sebagai bilangan riil. Dijamin grafik untuk f(x) memiliki tepat satu puncak. Cari nilai f(x) maksimal!
Kelemahan dari solusi ini adalah rawan precision error, karena banyak melibatkan urusan EPS. Terdapat solusi yang lebih elegan, yaitu dengan ternary search.
Pseudocode untuk algoritma ini adalah:
Jika Anda tidak ingin berurusan dengan EPS, cukup ganti:
Kompleksitas dari ternary search \(O(\log_{\frac{2}{3}}{N})\), dengan N adalah lebar interval pencarian. Bagaimanapun juga bisa disebut O(log N) dan berjalan dengan cepat.
Anda dapat mencoba soal berikut sebagai latihan:
Topik yang dibahas kali ini adalah ternary search. Bagi coder pemula, pastinya pernah mendengar istilah binary search. Anda juga mungkin pernah mendengar bahwa jika binary menyatakan dua, maka ternary menyatakan tiga. Jadi yang akan dibahas ini adalah pencarian ternary, yaitu dengan membagi tiga daerah. Kira-kira seperti ini:
Masalah
Jangan salah kaprah. Ternary search tidak digunakan untuk mencari suatu nilai dari data-data yang terurut. Permasalahan yang berkaitan dengan ternary search adalah:Diberikan sebuah fungsi f(x) yang menerima x sebagai bilangan riil. Dijamin grafik untuk f(x) memiliki tepat satu puncak. Cari nilai f(x) maksimal!
Solusi Binary Search
Dengan binary search, soal ini dapat diselesaikan dengan cara berikut:EPS <- nilai toleransi yang kecil (misalnya 1e-9)
ki <- MIN;
ka <- MAX;
while ((ka - ki) > EPS)
tgh <- (ki + ka) / 2
if ((tgh - EPS, tgh + EPS) menaik)
ki <- tgh
else if ((tgh - EPS, tgh + EPS) menurun)
ka <- tgh
else
break
return (ki + ka) / 2
Masuk di akal, bila di suatu titik tebakan kita mengarah naik, berarti puncak grafik ada di sebelah kanan. Sementara bila di suatu titik tebakan kita mengarah turun, berarti puncak grafik ada di kiri. Bila tidak naik dan tidak turun, artinya kita sampai pada puncak grafik.
Solusi Ternary Search
Pertama, pilih dua titik dari interval yang diberikan. Idealnya titik 1/3 dan 2/3 dari kiri. Kemudian tentukan titik mana yang lebih tinggi. Tentunya terdapat dua kasus:- Titik 1/3 lebih tinggi, artinya puncak berada di antara titik kiri dengan titik 2/3.
- Titik 2/3 lebih tinggi, artinya puncak berada di antara titik 1/3 dengan titik kanan.
EPS <- nilai toleransi
ki <- MIN
ka <- MAX
while ((ka - ki) > EPS)
t1 <- ki + (ka - ki)/3
t2 <- ki + (ka - ki)*2/3
if (t1 > t2)
ka <- t2
else
ki <- t1
return (ki + ka) / 2
Bisa diperhatikan bahwa operasi yang menggunakan EPS lebih sedikit, sehingga lebih akurat dan elegan.Jika Anda tidak ingin berurusan dengan EPS, cukup ganti:
while ((ka - ki) > EPS)dengan
for i=1..KDengan K adalah suatu bilangan yang menyatakan banyaknya iterasi, tanpa peduli epsilon. Saya biasanya menggunakan K=100. Seharusnya dalam 100 iterasi, akurasinya sudah sangat baik. Cara ini juga kode selalu berhenti dalam 100 langkah, ketimbang menggunakan while yang tidak jelas kapan berhentinya.
Kompleksitas dari ternary search \(O(\log_{\frac{2}{3}}{N})\), dengan N adalah lebar interval pencarian. Bagaimanapun juga bisa disebut O(log N) dan berjalan dengan cepat.
Anda dapat mencoba soal berikut sebagai latihan:
Tidak ada komentar :
Posting Komentar