ANALISIS KINERJA ALGORITMA PEMROGRAMAN DINAMIK PADA MASALAH MULTISTAGE GRAPH Wawan Setiawan Universitas Negeri Malang E-mail :
[email protected] Pembimbing: (I) Dra. Susy Kuspambudi Andaini, M. Kom, (II) Dra. Sapti Wahyuningsih, M. Si Abstrak : Tujuan pengkajian ini adalah untuk mengetahui kinerja algoritma pemrograman dinamik dan implementasinya dalam bentuk program. Penerapan program juga dilakukan untuk mengetahui hasil dari program. Bentuk ppengkajian algoritma pemrograman dinamik berupa penerapan manual, analisis kinerja yang berupa analisis waktu eksekusi (running time) dan penerapan menggunakan program yang didesain menggunakan algoritma tersebut. Berdasar analisis, algoritma pemrograman dinamik menunjukkan solusi yang optimal beserta semua alternatif solusi dari masalah multistage. Pada analisis running time algoritma pemrograman dinamik relatif besar yaitu (( − 2) ).
Kata Kunci: Algoritma, Multistage, Pemrograman Dinamik, Running Time
Perkembangan dunia industri yang semakin maju tidak pernah lepas dari masalah sarana produksi, transportasi, ongkos produksi, dan lain lain. Masalah-masalah itu muncul seiring berkembangnya suatu industri. Untuk mengatasi masalah tersebut dan mendapatkan keuntungan yang maksimal tidaklah mudah, untuk itu perlu pemetaan antara biaya yang dikeluarkan dan kegiatan perusahaan. Pemetaan ini adalah dasar untuk mengambil keputusan. Jika salah dalam hal pengambilan keputusan maka perusahaan tersebut mengalami kerugian. Masalah perusahaan bermacam-macam, salah satunya adalah masalah yang berkaitan dengan biaya transportasi. Rencana penerbangan (flight planning) adalah salah satu masalah yang berkaitan dengan transportasi. Masalah ini sering dialami oleh perusahaan penerbangan. Dalam penerbangan sebuah pesawat udara, perencanaan harus dibuat secara terperinci. Perencanaan harus dibuat demi keselamatan penerbangan tersebut. Menurut Brandon (2009:41) ada aspek penting terkait keselamatan (safety-critical aspects) yang harus diperhatikan dalam flight planning. Aspek tersebut adalah perhitungan bahan bakar (fuel calculation). Perhitungan bahan bakar diperlukan untuk memastikan bahwa pesawat udara dapat sampai di tujuan dengan selamat. Masalah multistage (multistage problem) adalah masalah yang terdiri dari tahapantahapan. Salah satu masalah multistage adalah masalah flight planning. Flight planning memiliki tahapan-tahapn seperti pemilihan ketinggian, pemilihan kecepatan, dan pemilihan rute. Masing-masing tahapan memiliki sejumlah status yang harus dipilih sehingga diperoleh keputasan dari tiap-tiap tahapan. Rangkaian keputusan dari tiap-tiap tahapan adalah keputusan yang diambil pada masalah multistage. Algoritma pemrograman dinamik adalah algoritma yang dapat digunakan untuk menyelesaikan masalah yang berkaitan dengan lintasan terpendek (shortest path). Tidak semua masalah yang berkaitan dengan penentuan lintasan terpendek dapat diselesaikan dengan algoritma pemrograman dinamik, hanya masalah yang memenuhi karakteristik yang dapat diselesaikan. Karakteristik tersebut adalah berbentuk multistage graph. Perencanaan penerbangan adalah masalah perusahaan yang berkaitan dengan penentuan biaya transportasi yang terdiri dari tahapan-tahapan sehingga masalah tersebut dapat dikatagorikan kedalam
masalah yang berbentuk multistage. Berdasarkan hal tersebut, masalah perencanaan penerbangan dapat diselesaiakan menggunakan algoritma pemrograman dinamik. Masalah multistage dapat diselesaiakan dengan berbagai macam cara, salah satunya menggunakan algoritma yang sudah ada seperti algoritma pemrograman dinamik, A* ataupun pencarian heuristic lainnya. Namum algoritma tersebut belum tentu memberikan hasil yang maksimum. Untuk itu perlu diperhatikan keefektifan dari algoritma tersebut. Dalam banyak hal, keefektifan suatu algoritma ditentukan salah satunya dengan menentukan waktu jalan (running time). Waktu jalan program (running time) adalah besaran waktu yang dibutuhkan program untuk melakukan eksekusi. Besaran ini menunjukkan seberapa lama program menyelesaikan masalah. Semakin besar nilai running time suatu program maka semakin tidak efektif. Pengkajian algoritma pemrograman dinamik (dynamic programming) dalam hal kinerja dan penerapannya pada masalah multistage perlu dikaji karena kita belum mengetahui apakah algoritma ini efektif untuk menyelesaikan multistage problem. Masalah yang menyangkut analisis algoritma sangat luas, untuk itu diperlukan pembatasan. Salah satu yang paling dominan adalah kompleksitas ruang . bentuk kompleksitas ruang ini adalah running time yaitu untuk menentukan waktu eksekusi suatu algoritma. (Rinaldi, 2010:9). Running time algoritma digunakan untuk mengetahui lama suatu program untuk menyelesaikan eksekusi. Bentuk running time ini adalah suatu fungsi dengan variabel n yang menunjukkan besaran waktu untuk jumlah data sebanyak n data. Untuk menentukan nilai running time tidak mudah, perlu perhitungan pada tiap-tiap langkah pengambilan keputusan. Pengambilan keputusan ataupun penugasan memiliki aturan tersendiri dalam perhitungannya seperti yang dijelaskan oleh Alfred V. Aho and Ullman Jeffrey D. Berdasarkan aturan pehitungan running time maka dapat ditentukan besaran running time suatu algoritma sehingga dapat dibandingkan keefektifan suatu algoritma. METODE Rancangan analisis kinerja lagoritma ini merupakan bagian dari pengujian keefektifan suatu algoritma. Berikut tahapan analisis algoritma yang dialakukan: 1. Menerapkan secara manual algoritma untuk menyelasaikan masalah multistage. Penerapan dilakukan untuk mengetahui proses perhitungan dan membandingkannya dengan Algoritma pembanding dalam hal ini adalah algoritma A*. 2. Melakukan analisis karakteristik masalah multistage untuk algoritma pemrograman dinamik. Analisis ini dilakukan untuk mengetahui hubungan syarat karakteristik dengan algoritma. 3. Menentukan nilai kompleksitas ruang. Kompleksitas ruang dalam hal ini adalah waktu jalan (running time) ditentukan berdasarkan aturan perhitungan waktu jalan dan disederhanakan menggunakan aturan rule of sum ataupun atauran penjumlahan yang lain. Notasi yang digunakan untuk perhitungan adalah notasi big-O. 4. Penentuan perangkat untuk mendesain program dimulai dari menentukan spesifikasi komputer yang digunakan sampai softwere yang digunakan. 5. Mendesain flowchart menggunakan algoritma pemrograman dinamik dengan aturan flowchart sederhana. 6. Penerapan program untuk menyelesaikan masalah multistage dari masalah yang sederhana sampai jumlah titik maksimum yang dapat diselesaikan program. 7. Melakukan analisis pada penerapan program untuk kasus out of memory. Kasus dimana program tidak mampu menyelesaikan eksekusi yang dikarenakan kondisi memori yang berlebih pada kompilator.
HASIL DAN PEMBAHASAN 1. Penerapan Algoritma pemrograman dinamik
Gambar 3.3. Graph berarah Flight Planning rute Hong Kong – Los Angeles Penyelesaian per tahap dengan pemrograman dinamik maju untuk persoalan yang digambarkan oleh Gambar 4 diberikan sebagai berikut: Tahap 1: ( )= ) ( Tabel 3.1. Tahap 1 Pemrograman dinamik Maju untuk Solusi Optimum ( )= Solusi Optimun s Titik 0 f1 (s) x1 * Titik 1 6 6 Titik 0 Titik 2 8 8 Titik 0 Titik 3 10 10 Titik 0 Catatan: xk* adalah nilai xk yang meminimumkan fk(s,xk). Tahap 2: ( ) = min + ( ) Tabel 3.2. Tahap 2 Pemrograman dinamik Maju untuk Solusi Optimum x2 ( , )= Solusi Optimun + ( ) s Titik 1 Titik 2 Titik 3 F2 (s) X2 * Titik 4 86 78 70 70 Titik 3 Titik 5 85 77 69 69 Titik 3 Titik 6 87 79 71 71 Titik 3 Tahap 3: ( ) = min + ( ) Tabel 3.3. Tahap 3 Pemrograman dinamik Maju untuk Solusi Optimum x3 ( , )= Solusi Optimun + ( ) s Titik 4 Titik 5 Titik 6 F3 (s) X3 * Titik 7 105 114 121 105 Titik 4 Titik 8 100 94 93 93 Titik 6 Tahap 3: ( ) = min + ( ) Tabel 3.4. Tahap 4 Pemrograman dinamik Maju untuk Solusi Optimum x4 ( , )= + ( ) Solusi Optimun s Titik 7 Titik 8 F4 (s) X4 *
Titik 9
106
94
93
Titik 8
Dari pemrograman dinamik maju, solusi optimal untuk kasus Flight Planning tersebut, yang merupakan lintasan terpendek dari titik 0 ke titik 9 adalah titik 0titik3 titik 6 titik 8 titik 9.
Gambar 3.4. Rute solusi graph 1. Analisis Berdasarkan Proses Karakteristikkan struktur solusi optimal Karakteristik pertama mensyaratkan bahwa persoalan dapat dibagi menjadi beberapa tahap yang hanya diambil satu keputusan, ini berarti selalu ada satu keputusan (xk) yang akan diambil pada tiap-tiap tahap. Karakteristik kedua mensyaratkan tiap-tiap tahap terdiri dari sejumlah status (state/bobot sisi/ “s”) yang berhubungan pada tahap tersebut sebagai perubah keputusan. Berdasarkan karakteristik pertama dan kedua diperoleh state (s) dan xk sebagai keputusan yang diambil. Karakteristik ketiga mensyaratkan hasil yang didapat pada tahap bersangkutan ditransformasikan ke status pada tahap berikutnya sehingga muncul ( ) sebagai pertimbangan pengubah keputusan pada tahap yang berikutnya Karakteristik keempat mensyaratkan cost pada suatu tahap meningkat secara teratur (steadily) berdasarkan jumlah tahapan, berarti cost atau dalam hal ini bobot sisi selalu meningkat dari tahap 1 ke tahap 2 dan berikutnya secara teratur membentuk fk untuk k= 1, 2, …, n Karakteristik kelima mensyaratkan cost bergantung pada cost pada tahap sebelumnya dan cost pada tahap yang bersangkutan dalam hal ini s (state). Berdasarkan pada karakteristik ini berarti ( )= ( ), = 1, 2, . . , (rekuren) + Karakteristik keenam menunjukkan bahwa keputusan yang diambil adalah keputusan terbaik (nilai fk yang terkecil) dan bersifat independen dari keputusan sebelumnya. Keputusan yang baru tidak ada pengaruhnya denga keputusan yang sebelumnya. Dari karakteristik ini dapat kita bentuk dari rekurens sebelumnya menjadi ( )= ( ) , = 1, 2, . . , (rekuren) + Karakteristik ketujuh menunjukkan bahwa keputusan terbaik untuk setiap status pada tahap k memberikan keputusan terbaik untuk setiap status pada tahap k + 1, dengan kata lain semua kuputusan yang sudah diambil adalah keputusan terbaik dan pengubah keputusan pada tahap berikutnya yang memenihi nilai minimum dari rekurens juga merupakan keputusan terbaik. Karakteristik kedelapan menunjukkan Prinsip optimalitas berlaku, berarti bahwa jika kita bekerja dari tahap k ke tahap k + 1, kita dapat menggunakan hasil optimal dari tahap k tanpa harus kembali ke tahap awal
Misalkan x1, x2, ..., xn adalah titik-titik yang dikunjungin pada tahap k (k = 1, 2, .., n), maka rute yang dilalui adalah x1 x2 … xn, yang dalam hal ini xn adalah titik tujuan dan x1 adalah titik awal. Tahap (k) adalah proses memilih titik tujuan berikutnya (ada n tahap), sementara status (s) yang berhubungan dengan masing-masing tahap adalah titik-titik dalam graph.
Definisikan secara rekursif nilai solusi optimal Nilai keputusan terbaik dapat dinyatakan dengan relasi rekurens berikut: ( ) = (basis) ( ) = min ( ) , = 1, 2, 3 (rekuren) + yang dalam hal ini peubah xk menyatakan peubah keputusan pada tahap k (k = 1,2,3), csxk menyatakan bobot (cost) lokal dari sisi s ke xk Hitung nilai solusi optimal fk(s, xk) menyatakan total kumulatif bobot lintasan dari s ke xk, dan fk(s) merupakan nilai minimum dari fk(s, xk). Konstruksi solusi optimal Nilai fk(s, xk) yang minimum sampai pada fn(s, xn) menunjukkan nilai lintasan terpendek. Berdasarkan rekurensi ini disusun runtutan xk yang memenuhi nilai minimum yaitu x1 x2 … xn Berdasarkan analisis proses diatas dapat disimpulkan bahwa penyusunan langkahlangkah penyelesaian menggunakan pemrograman dinamik tidak terlalu rumit namun memberikan hasil yang optimal. Mengkaji ulang penyusunan langkahlangkah proses ini harus memenuhi kaarakteristik diatas, dengan kata lain algoritma ini hanya terbatas pada masalah yang memenuhi karakteristik diatas. Untuk algoritma A* penghitungan tidak terpaku pada karakteristik diatas. Semua masalah yang dapat dibentuk tree dapat diselesaikan karena pada dasarnya A* menggunakan model pohon pencari untuk menentukan solusi masalah multy stage. 2. Kelebihan dan kelemahan Algoritma pemrograman dinamik Penggunaan algoritma ini untuk menyelesaikan masalah multy stage menghasilkan rute yang minimal sesuai dengan prinsip optimalitas bahwa jika kita bekerja dari tahap k ke tahap k + 1, kita dapat menggunakan hasil optimal dari tahap k tanpa harus kembali ke tahap awal. Hasil keputusan pada tahap k adalah keputusan yang optimal dan hasil keputusan pada tahap k-1 juga optimal, hasil keputusan yang optimal ini dijamin optimal sampai pada tahap 1 dan karena keputusan ini bersifat independen berarti keputusan ke-k, k-1, k-2, …, 1 adalah keputusan yang optimal. Kelemahan dari algoritma ini, untuk penghitungan mencari nilai ( ) = min ( ) , = 1, 2, … dilakukan sebayak jumlah titik yang + ada pada tahap yang bersangkutan. Dengan kata lain jika jumlah maksimum titik pada tiap tahap besar maka penghitungan ini juga akan banyak dan demikian sebaliknya, jika jumlah maksimum titik pada tiap tahap kecil maka perhitungan ini semakin sedikit. Lainhalnya dengan A*, algoritma ini melakukan perhitungan iterasi sebanyak titik yang terhubung dengan titik yang terpilih. Dengan kata lain semakin banyak titik yang terdekat dengan titik terpilih, algoritma ini akan melakukan iterasi semakin banyak tanpa menghiraukan tahapan. 3. Analisis Berdasarkan hasil / Solusi Solusi dari algoritma ini dijamin akan menghasilkan solusi optimal untuk setiap masalah yang memenuhi karakteristik diatas. Dan berdasarkan penghitungan manual hasil ini juga menunjukkan hal yang sama yaitu solusi optimal dengan lintasan
terpendek. Berbeda dengan algoritma A*, hasil yang ditawarkan sama dengan solusi pemrograman dinamik. Namun ada sedikit perbedaan pada penghitungan pencarian nilai terkecil pada tahap perulangan di masing-masing algoritma. Pada pemrograman ( ) , = 1, 2, … hanya dinamik pencarian nilai ( ) = min + dilakukan pada titik yang terletak pada tahap berikutnya, jadi tidak mengulang ke titik pada tahap sebelumnya namun berbeda dengan A* yang menghitung setiap titik yang terhubung dengan titik yang terpilih, jadi titik yang belum terpilih adalah titik titik yang juga dihitung dan digunakan sebagai pembading pada pengambilan keputusan 4. Analisis efisiensi algoritma pemrograman dinamik pencarian kompleksitas waktu atau running time pada algoritma pemrogaman dinamik menggunakan notasi big-O dijelaskan sebagai berikut: langkah 1 dan langkah 2 kalimat penugasan memerlukan waktu O(1). Langkah 3 Kalimat pengulangan yang digunakan untuk mencari titik yang terpilih sebanyak jumlah tahap, yaitu sebanyak k. namun tahap 1 ditentukan memilih x1, jd pengulangan hanya dilakukan sebanyak k-1 dengan kata lain waktu yang dibutuhkan O(k-1). Langkah 4 Pencarian titik terhubung xk s dengan xk dilakukan pengulangan sebanyak titik pada tahap sebelumnya. Karena tidak diketahui jumlah titik pada tahap sebelumnya maka jumlah yang digunakan adalah maksimum dari jumlah titik pada tiap-tiap tahap. Jumlah yang dimaksud adalah sebanyak |v|-2, banyaknya titik maksimum dikuranya titik awal dan titik akhir. Jadi kemungkinan terburuk yang bisa digunakan sebagai pengganti waktu jalan langkah ini adalah |v|-2 jadi waktu jalan langkah ini memerlukan O(|v|-2). Langkah 5 Pada langkah ini dilakukan perintah penugasan untuk menjumlah jarak awal dengan bobot sisi titik yang terhubung pada tahap berikutnya, penugasan ini memerlukan waktu O(1). Setelah penugasan, dilakukan pemilihan nilai minimum fk(x) memerlukan waktu O(|v|-2). Langkah 6 Proses penyimpanan pada langkah mengunakan pemilihan kondisional statement if … then … , namun karena kondisi penyimpanan ini hanya dilakukan pada satu kondisi yang diminta maka waktu yang dibutuhkan sebanyak O(1). Karena langkah 4, langkah 5 dan langkah 6 berada dalam pengulangan langkah 3 maka langkah 4, langkah 5 dan langkah 6 dianggap sebagai blok yang masing-masing memerlukan waktu jalan sebanyak O(|v|-2), O(|v|-2) dan O(1). Langkah ini berada pada kedalaman iterasi yang sama sehingga aturan untuk penjumlahan (rule of sum) dapat digunakan sehingga diperoleh waktu jalan yang baru yaitu O(max((|v|-2),(|v|2),(1))) = O(|v|-2). Langkah 3 memerlukan waktu jalan O(k-1) yang didalam body langkah 3 berisi langkah 4, langkah 5 dan langkah 6 maka waktu jalan keseluruhan langkah 3 adalah O(k-1)×O(|v|-2) = O((k-1) (|v|-2))=O(k|v|-2k-|v|+2) Dari analisis penghitungan waktu jalan (running time) algoritma Pemrograman dinamik diatas adalah O(k|v|-2k-|v|+2). Langkah 7 (menyusun solusi) memerlukan waktu yang cukup banyak, karena untuk menghitung waktu running dibutuhkan kemungkinan terjelek maka langkah ke-7 ini mempunyai waktu running sebesar banyak titik maksimum pada tahap dipangkatkan dengan jumlah tahap – 2. Jadi diperoleh O((|v|-2)k-2).
Berdasarkan langkah 1 sampai dengan langkah 7 diperoleh waktu running sebesar O(k|v|-2k-|v|+2+((|v|-2)k-2)). Menurut aturan penjumlahan yang lain Jika g(n)≤f(n) untuk n diatas n0 maka O(f(n)+g(n)) adalah sama dengan O(f(n). misalkan g(n)= k|V|-2k-|V|+2 dan f(n)= (|V|-2)k-2. g(n)= k|V|-2k-|V|+2 < (|V|-2)k-2 =f(n). sehingga diperoleh O(k|V|-2k|V|+2+((|V|-2)k-2))=O((|V|-2)k-2) Berdasarkan langkah 1 sampai dengan langkah 7 diperoleh O((|V|-2)k-2) (|V|-2)k-2= |V| k-2 + k-2C1 |V| k-3(-2)1+ + …+ (-2) k-2 Menurut atauran penjumlahan yang lain Jika g(n)≤f(n) untuk n diatas n0 maka O(f(n)+g(n)) adalah sama dengan O(f(n). sehingga diperoleh O((|V|-2)k-2) =O( |V| k-2 ). Agar dapat dibandingkan, bentuk masukan pada algoritma pemrograman dinamik haruslah sama dengan algoritma A* yaitu sebanyak n titik. |V| adalah maksimal jumlah titik pada tahap, yaitu sebesar ≤ | | ≤ − 2, dengan n adalah banyak titik total dan k adalah jumlah tahap. k adalah jumlah tahap, yaitu sebesar 3 ≤ k ≤ n dengan n adalah banyak titik total dan k adalah jumlah tahap. Berdasarkan kasus terburuk dari nilai |V| dan k maka diperoleh | | = − 2 dan k = n sehingga didapatkan O( |V| k-2 ) = (( − 2) ). Penghitungan waktu jalan (running time) algoritma Pemrograman dinamik secara keseluruhan adalah (( − 2) ).. Untuk menggambarkan waktu jalan ini bisa dilihat pada tabel dibawah ini: Tabel 3.5. Tabel kecepatan eksekusi 3 4 5 6 Thp 2 jml titik 2 5 10 14 22 O( |v|k-2) 1 ms 5 ms 100 ms 2744 ms 234256 ms Table diatas menyatakan kecepatan eksekusi masalah dengan satuan ms (microsecond) dari algoritma program dinamik untuk kasus terburuk. KESIMPULAN 1. Dari segi kinerja dapat disimpulkan sebagai berikut: a. Algoritma pemrograman dinamik memberikan semua alternatif solusi yang mungkin dari hasil pencarian yang memenuhi kriteria minimum dan memenuhi prinsip optimalitas. b. Algoritma pemrograman dinamik memiliki waktu running yang cukup besar yaitu (( − 2) ), sedangkan algoritma A* memerlukan O(n2). 2. Dari segi penerapan dapat disimpulkan sebagai berikut: a. Penggunaan program untuk menyelesaiakan masalah multistage menghasilkan solusi yang terbaik dengan solusi alternatif (jika terdapat lebih dari satu solusi) b. Proses pencarian lintasan terpendek dari program dapat dilakukan meskipun jumlah titik lebih dari 37 dengan catatan solusi yang ada pada masalah tersebut tidak sebanyak nk-2, n adalah jumlah titik pada setiap tahap dan k adalah jumlah tahap. SARAN Menggunakan algoritma pemrograman dinamik untuk menyelesaikan masalah multistage merupakan salah satu cara yang dapat dilakukan, namun algoritma ini memiliki solusi yang cukup banyak sehingga alternatif solusi yang ditawarkan ini dapat menyebabkan kondisi out of memory yang dikarenakan terlalu banyak solusi yang di tawarkan. Untuk itu penulis menyarankan agar menggunakan algoritma ini
jika masalah tersebut memiliki bobot sisi yang berbeda. Jika menemui masalah yang memiliki bobot sisi yang sama maka lebih baik menggunakan algoritma yang lain seperti A* , Djiktra atau yang lainnya. DAFTAR PUSTAKA Aho, Alfred V. and Jeffrey D. Ullman. Foundation of Computer Science Hariyanto, Bambang. 2003. Struktur Data.Bandung:informatika Bandung. Kinerja, Wikipedia.
. (online) URL:
http://wikipedia.org/, diakses 12 februari 2012. Munir, Rinaldi. Bahan Kuliah ke-13: Program Dinamik (Dynamic Program). 2004. ITB. Bandung. Rinaldi. 2010. Program dinamik (online), URL: http://wwwinformatika.org/~rinaldi/stmik/20102011/makalah_2010/makalahSTMIK2010-062.pdf.html, diakses 13 mei 2010. Vatter, Vince. 2004. Graph, Flow, and the Ford-Fulkersen Algorithm(online), URL: http://www.math.dartmouth.edu/~vatter/teaching/summer04/flow.pdf diakses 24 september 2011.
Artikel Ilmiah oleh Wawan Setiawan ini Telah diperiksa dan disetujui oleh
Malang,
Mei 2013
Pembimbing I
Dra. Susy Kuspambudi Andaini, M. Kom NIP. 19590419 198812 2 001
Malang,
Mei 2013
Pembimbing II
Dra. Sapti Wahyuningsih, M. Si NIP. 19621211 198812 2 001
Malang,
Mei 2013
Penulis
Wawan Setiawan NIM 907312410079
