PERANGKAT LUNAK PERMAINAN SEEKING PATH DENGAN ALGORITMA ALL-PAIRS SHORTEST-PATH FLOYD WARSHALL
SKRIPSI
Oleh:
HARRIS KRISTANTO NIM.1144076
PROGRAM STUDI TEKNIK INFORMATIKA SEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN KOMPUTER STMIK TIME MEDAN 2015
ABSTRAK
Pada kehidupan sehari-hari sering ditemukan permasalahan dalam menentukan jalur mana yang harus dilalui agar jarak yang ditempuh paling minimum ataupun biaya transportasi yang diperlukan paling minimum. Permasalahan seperti ini dapat diselesaikan dengan menggunakan algoritma shortest path, dimana daerah (kota) diwakili oleh vertex dan jarak atau biaya yang diperlukan diwakili oleh edge pada sebuah graph. Problema all-pairs shortest-path ditujukan untuk mencari shortest path dari semua pasangan simpul pada sebuah graph. Salah satu contoh penerapan problema ini yaitu dalam pembuatan tabel jarak terpendek antara semua pasangan kota dari suatu peta jalan. Algoritma Floyd-Warshall menggunakan bantuan struktur matriks, operasi perkalian matriks dan konsep dynamic programming untuk mencari all-pairs shortest path. Perangkat lunak mampu menampilkan proses kerja dari algoritma FloydWarshall secara terperinci tahap demi tahap. Selain itu, perangkat lunak juga menyediakan teori-teori yang berhubungan dengan algoritma Floyd-Warshall.
Kata kunci: Floyd Warshall, shortest path, all-pairs shortest-path
i
ABSTRACT
In life we often found problems in determining the path which must be passed in order that the minimum distance or transport costs required minimum. Such problems can be solved by using a shortest path algorithm, in which area (city) represented by the vertex and the distance or cost required is represented by edge on a graph. Problems all-pairs shortest-path aimed to find the shortest path from every pair of vertices in a graph. As an example of this problem is in the manufacture of table shortest distance between all pairs of cities of a roadmap. Floyd-Warshall algorithm using support matrix structure, matrix multiplication operations and the concept of dynamic programming to find the all-pairs shortest path. The software is able to display the working process of the Floyd-Warshall algorithm in detail step by step. In addition, the software also provides the theories related to the Floyd-Warshall algorithm.
Keywords: Floyd Warshall, shortest path, all-pairs shortest-path
ii
KATA PENGANTAR
Puji dan syukur penulis panjatkan kepada Tuhan Yang Maha Esa, atas berkat rahmat dan karunia-Nya sehingga penulis dapat menyelesaikan Skripsi ini dengan mengambil judul “PERANGKAT LUNAK PERMAINAN SEEKING PATH DENGAN ALGORITMA ALL-PAIRS SHORTEST-PATH FLOYD WARSHALL”. Penyusunan laporan skripsi ini merupakan salah satu syarat yang harus dipenuhi penulis guna mendapatkan gelar Strata-1 Program Studi Teknik Informatika pada STMIK TIME Medan. Pada kesempatan ini, penulis ingin menyampaikan ucapan terima-kasih yang sebesar-besarnya kepada semua pihak yang telah membimbing dan membantu dalam penyusunan laporan skripsi ini, terutama kepada: 1.
Bapak Dian Noviandri, ST, M.Kom, selaku Dosen Pembimbing I yang telah membantu dan membimbing penulis dalam menyelesaikan skripsi ini.
2.
Bapak Hendri, M.Kom, selaku Dosen Pembimbing II yang telah membantu dan membimbing penulis dalam menyelesaikan skripsi ini.
3.
Bapak Simon Kanggali, selaku Ketua Yayasan STMIK TIME Medan.
4.
Bapak Prof. Chainur Arsyid, SH, selaku Ketua BPH STMIK TIME Medan.
5.
Bapak Prof. Harlem Marpaung, Ph.D, selaku Ketua STMIK TIME Medan.
6.
Bapak Jackri Hendrik, ST, M.Kom, selaku Pembantu Ketua I STMIK TIME Medan.
7.
Bapak Hendri, M.Kom, selaku Ketua Program Studi Teknik Informatika STMIK TIME Medan.
iii
8.
Seluruh staff dosen-dosen serta rekan-rekan Mahasiswa STMIK TIME Medan, yang telah banyak memberikan ilmu pengetahuan kepada penulis selama perkuliahan.
9.
Orang tua tercinta dan saudara-saudara yang senantiasa mendukung dan memberikan bantuan moril maupun material kepada penulis. Akhir kata, dengan penuh kerendahan hati penulis menyadari bahwa isi
skripsi dan teknik penulisan skripsi ini masih jauh dari kesempurnaan dan masih memerlukan perbaikan untuk menyempurnakannya baik dari segi tata bahasa manapun materi yang terkandung didalamnya. Oleh karena itu, setiap kritik dan saran akan diterima dengan senang hati agar dapat dijadikan bahan perbaikan untuk penulisan selanjutnya. Akhir kata, puji dan syukur penulis ucapkan kepada Tuhan Yang Maha Esa, semoga kita selalu dalam lindungan dan rahmat karuniaNya.
Medan,
April 2015
Penulis,
Harris Kristanto
iv
DAFTAR ISI ABSTRAK ..............................................................................................................
i
ABSTRACT .............................................................................................................. ii KATA PENGANTAR ............................................................................................. iii DAFTAR ISI ............................................................................................................ v DAFTAR GAMBAR ............................................................................................... vii DAFTAR TABEL ................................................................................................... viii DAFTAR LAMPIRAN ........................................................................................... ix BAB I
PENDAHULUAN ............................................................................ 01 1.1. Latar Belakang Masalah ............................................................ 01 1.2. Identifikasi Masalah .................................................................. 03 1.3. Batasan Masalah ....................................................................... 03 1.4. Tujuan Dan Manfaat Penelitian ................................................ 04 1.5. Sistematika Penulisan ............................................................... 04
BAB II
LANDASAN TEORI ....................................................................... 06 2.1. Perangkat Lunak (software) ...................................................... 06 2.2. Permainan Seeking Path ............................................................ 7 2.3. Algoritma ................................................................................... 7 2.4. All-Pairs Shortest Path ............................................................. 8 2.4.1. Graph ............................................................................... 10 2.4.2. Jenis-jenis Graph ............................................................. 12 2.4.3. Istilah-istilah Dasar Dalam Graph .................................. 15 2.4.4. Shortest Path ................................................................... 18 2.4.5. Algoritma Floyd-Warshall .............................................. 20
BAB III
METODE PENELITIAN ............................................................... 22 3.1. Tempat Dan Jadwal Penelitian .................................................. 22 3.2. Kerangka Kerja .......................................................................... 22 3.2.1. Pengumpulan Data .......................................................... 23 3.2.2. Analisa Sistem ................................................................ 24 3.2.3. Perancangan Sistem ........................................................ 24 3.2.4. Pembangunan Sistem ...................................................... 25
v
3.2.5. Uji coba sistem ................................................................ 25 BAB IV
ANALISIS DAN PERANCANGAN .............................................. 26 4.1. Analisa ...................................................................................... 26 4.1.1. Analisa Proses Kerja Algoritma Floyd-Warshall ............ 26 4.1.2. Analisa Kebutuhan .......................................................... 33 4.2. Perancangan .............................................................................. 34 4.2.1. Perancangan Tampilan .................................................... 35 4.2.1.1 Form ‘Main’ ........................................................ 35 4.2.1.2 Form ‘Pilih User’ ................................................ 37 4.2.1.3 Form ‘Permainan’ ................................................ 38 4.2.1.4 Form ‘High Score’ .............................................. 39 4.2.1.5 Form ‘About’ ...................................................... 40 4.3. Perancangan Database .............................................................. 41
BAB V
HASIL DAN PEMBAHASAN ....................................................... 42 5.1. Hasil ........................................................................................... 42 5.1.1. Spesifikasi Perangkat Keras dan Perangkat Lunak ......... 42 5.1.2. Tampilan Hasil ................................................................ 43 5.2. Pembahasan ............................................................................... 48 5.3. Algoritma ................................................................................... 48
BAB V1
KESIMPULAN DAN SARAN ....................................................... 50 6.1. Kesimpulan ................................................................................ 50 6.2. Saran .......................................................................................... 50
DAFTAR PUSTAKA .............................................................................................. 52 LAMPIRAN
vi
DAFTAR GAMBAR Gambar 2.1.
Contoh Tiga Buah Graph .................................................................. 11
Gambar 2.2.
Contoh Graph Berarah dan Graph Ganda Berarah ........................... 14
Gambar 3.1.
Kerangka Kerja ................................................................................. 23
Gambar 4.1.
Proses Penentuan Nilai Awal Matriks .............................................. 28
Gambar 4.2.
Proses Perhitungan Nilai Shortest Path Floyd Warshall .................. 29
Gambar 4.3.
Proses Penentuan Shortest Path Floyd Warshall .............................. 30
Gambar 4.4.
Contoh Graph Berarah ...................................................................... 31
Gambar 4.5.
Rancangan Form ‘Main’ ................................................................... 36
Gambar 4.6.
Rancangan Form ‘Pilih User’ ........................................................... 37
Gambar 4.7.
Rancangan Form ‘Permainan’ .......................................................... 38
Gambar 4.8.
Rancangan Form ‘High Score’ ......................................................... 39
Gambar 4.9.
Rancangan Form ’About’ ................................................................. 40
Gambar 5.1.
Tampilan Form Awal ‘Main’ ............................................................ 43
Gambar 5.2.
Tampilan Form ‘Pilih User’ .............................................................. 44
Gambar 5.3.
Tampilan Form ’Tambah User Baru’ ............................................... 44
Gambar 5.4.
Tampilan Form ’Permainan’ ............................................................. 45
Gambar 5.5.
Tampilan Form ’Permainan Menang’ ............................................... 46
Gambar 5.6.
Tampilan Form ’Pemberitahuan Permainan Berakhir’ ..................... 46
Gambar 5.7.
Tampilan Form ’High Score’ ............................................................ 47
Gambar 5.8.
Tampilan Form ’About’ ..................................................................... 47
vii
DAFTAR TABEL Tabel 2.1
Perbandingan Jenis-jenis Graph ........................................................... 15
Tabel 3.1
Jadwal Penelitian .................................................................................. 22
Tabel 4.1
Matriks D(0) .......................................................................................... 31
Tabel 4.2
Matriks D(1) .......................................................................................... 32
Tabel 4.3
Matriks D(2) .......................................................................................... 32
Tabel 4.4
Matriks D(3) .......................................................................................... 32
Tabel 4.5
Matriks D(4) .......................................................................................... 33
Tabel 4.6
Matriks D(5) .......................................................................................... 33
Tabel 4.7
Tabel HighScore ................................................................................... 41
Tabel 4.8
Tabel UserList ...................................................................................... 41
viii
DAFTAR LAMPIRAN Lampiran 1. CD Program Lampiran 2. Daftar Riwayat Hidup Mahasiswa Lampiran 3. Surat Keputusan Dosen Pembimbing Skripsi Lampiran 4. Kartu Bimbingan Dosen I Lampiran 5. Kartu Bimbingan Dosen II Lampiran 6. Listing Program
ix
BAB I PENDAHULUAN
1.1.
Latar Belakang Masalah Pada kehidupan sehari-hari sering ditemukan permasalahan dalam
menentukan jalur mana yang harus dilalui agar jarak yang ditempuh paling minimum ataupun biaya transportasi yang diperlukan paling minimum. Permasalahan seperti ini dapat diselesaikan dengan menggunakan algoritma shortest path, dimana daerah (kota) diwakili oleh vertex dan jarak atau biaya yang diperlukan diwakili oleh edge pada sebuah graph. Persoalan lintasan terpendek merupakan salah satu persoalan optimasi yang menggunakan graph berbobot, dimana bobot pada setiap sisi graph tersebut dapat digunakan untuk menyatakan jarak antar kota, waktu pengiriman pesan, ongkos pembangunan, dan sebagainya. Algoritma yang digunakan untuk mencari suatu solusi dalam menentukan lintasan terpendek dari suatu graph disebut pathing algorithm. Saat ini terdapat banyak sekali algoritma yang digunakan untuk menyelesaikan persoalan lintasan terpendek diantaranya algoritma Floyd-Warshall yang memungkinkan untuk menentukan semua pasangan lintasan terpendek untuk semua pasangan simpul. Ardiansyah dan Hakim (2012) mengembangkan sebuah aplikasi untuk menentukan jalur terpendek menggunakan algoritma Floyd di lokasi wisata Purbalingga, dimana aplikasi yang dibuat dapat menunjukkan jalur terpendek untuk menuju setiap area pada lokasi wisata tersebut. Novandi (2007) melakukan perbandingan antara algoritma Djikstra dan algoritma Floyd-Warshall dalam penentuan lintasan terpendek. Namun, aplikasi yang dibuat tidak menyediakan
1
2
fitur permainan yang memungkinkan pemakai untuk menyelesaikan persoalan secara manual. Oleh karena itu, penulis bermaksud untuk membuat sebuah aplikasi yang menyediakan fitur permainan yang menerapkan algoritma Floyd-Warshall. Permainan ini diberi nama permainan Seeking Path yang merupakan sebuah permainan pencarian jalur dari sumber ke tujuan dengan sasaran untuk memperoleh jarak terpendek yang ditempuh. Permainan ini akan dilengkapi dengan sebuah fasilitas hint yang dapat digunakan untuk membantu pemain dalam menentukan langkah selanjutnya yang harus dilalui untuk mencapai tujuan. Fasilitas hint ini akan dijalankan dengan menggunakan algoritma Floyd-Warshall untuk mencari solusi jarak terpendek dari sumber ke tujuan. Kelebihan dari penerapan algoritma Floyd-Warshall ini jika dibandingkan dengan algoritma lainnya seperti algoritma Djikstra adalah algoritma Floyd-Warshall dapat mencari semua pasangan jalur terpendek (all-pairs shortest path) untuk semua pasangan titik yang terdapat pada graph dalam sekali proses, sehingga dengan penerapan algoritma ini maka memungkinkan untuk pemain untuk mencari jarak terpendek pada saat permainan dijalankan hingga setengah jalan, tanpa harus memproses ulang algoritmanya. Berdasarkan uraian di atas, maka penulis bermaksud untuk merancang sebuah perangkat lunak yang mampu untuk menerapkan algoritma Floyd-Warshall dalam mencari solusi lintasan terpendek pada permainan Seeking Path. Oleh karena itu, penulis mengambil skripsi dengan judul “Perangkat Lunak Permainan Seeking Path dengan Algoritma All-Pairs Shortest-Path Floyd-Warshall”.
3
1.2.
Identifikasi Masalah Adapun permasalahan yang muncul dalam kehidupan sehari-hari yaitu:
1. Bagaimana menentukan jalur yang harus dilalui agar memenuhi persyaratan tertentu seperti jarak yang ditempuh paling minimum. 2. Bagaimana menerapkan algoritma Floyd-Warshall untuk mencari solusi jarak terpendek pada permainan Seeking Path.
1.3.
Batasan Masalah Pembatasan permasalahan dalam membuat perangkat lunak ini adalah
sebagai berikut: 1. Permainan akan dimainkan dengan menggunakan batasan waktu, dimana waktu akan berkurang 1 detik per kenaikan level dan sisa waktu akan diakumulasikan ke level berikutnya, dengan waktu awal dimulai dari 30 detik. 2. Permainan terdiri dari tiga jenis tingkat kesulitan yaitu: a. Level 1 sampai level 10 merupakan tingkat kesulitan ‘Mudah’ dengan jumlah kotak sebesar 12 x 12. b. Level 11 sampai level 20 merupakan tingkat kesulitan ‘Sedang’ dengan jumlah kotak sebesar 14 x 14. c. Level 21 sampai level 30 merupakan tingkat kesulitan ‘Sulit’ dengan jumlah kotak sebesar 16 x 16. 3. Perangkat lunak mendukung proses pengisian nama user baru. 4. Permainan juga menyediakan fasilitas hint untuk memberitahukan kepada user mengenai arah gerakan yang benar.
4
1.4.
Tujuan dan Manfaat Penulisan Tujuan penyusunan skripsi ini adalah membuat suatu perangkat lunak
permainan yang menerapkan algoritma Floyd-Warshall dalam menentukan lintasan terpendek.
Manfaat dari penyusunan skripsi ini adalah: 1. Perangkat lunak dapat digunakan sebagai sarana penghibur yang cukup menarik. 2. Laporan skripsi dapat digunakan untuk membantu pemahaman mengenai proses penentuan jalur terpendek yang dapat dilalui dengan menggunakan algoritma Floyd-Warshall.
1.5.
Sistematika Penulisan Agar pembahasan lebih sistematika, maka tulisan ini dibuat dalam enam
bab, yaitu : BAB I
PENDAHULUAN Dalam bab ini berisi tentang latar belakang pemilihan judul, identifikasi masalah, batasan masalah, tujuan dan manfaat, dan sistematika penulisan.
BAB II
LANDASAN TEORI Dalam bab ini berisi tentang uraian-uraian teori dasar yang terkait dengan masalah yang diteliti dan dijabarkan dari studi pustaka dan dibahas secara singkat.
5
BAB III
METODE PENELITIAN Dalam bab ini berisi tentang tempat dan jadwal penelitian, kerangka kerja, metode pengumpulan data, analisa sistem, perancangan sistem, pembangunan sistem, uji coba sistem dan implementasi sistem.
BAB IV
ANALISA DAN PERANCANGAN Dalam bab ini berisi tentang pembahasan mengenai proses kerja dan perancangan tampilan antarmuka.
BAB V
HASIL DAN PEMBAHASAN Dalam bab ini berisi tentang algoritma dan implementasi dari perangkat lunak.
BAB VI
KESIMPULAN DAN SARAN Dalam bab ini berisi tentang kesimpulan dan saran-saran yang diambil penulis setelah menyelesaikan skripsi.
BAB II LANDASAN TEORI
2.1.
Perangkat Lunak (Software) Perangkat lunak (software) dapat diartikan sebagai:
1. Instruksi-instruksi dalam program komputer yang bila dieksekusi akan memberikan fungsi dan unjuk kerja yang diinginkan. 2. Struktur data yang membuat program mampu memanipulasi suatu informasi. 3. Dokumen-dokumen yang menjelaskan operasi dan pemakaian suatu program. Jadi, perangkat lunak adalah program komputer, struktur data, dan dokumentasi yang berkaitan, yang menyediakan metode logika, prosedur atau kontrol yang diminta. Perangkat lunak (software) memiliki beberapa karakteristik yang membedakannya dengan perangkat keras (hardware) antara lain: 1. Perangkat lunak dikembangkan dan direkayasa, bukan dirakit seperti perangkat keras. Meskipun ada beberapa kesamaan pengertian antara kedua istilah tersebut, tetapi pada dasarnya berbeda. 2. Perangkat lunak dibuat berdasarkan sistem yang sifatnya berbeda-beda, sedangkan perangkat keras dibuat berdasarkan rakitan komponen yang sudah ada. 3. Perangkat lunak tidak bisa rusak kecuali adanya kesalahan dari pembuat program (programmer), sedangkan tingkat kerusakan perangkat keras sangat tinggi.
6
7
2.2.
Permainan Seeking Path Menurut Costkyan, permainan (game) adalah sebuah bentuk dari seni di
mana pemain-pemain membuat keputusan untuk mengatur sumber-sumber melalui
token-token
game
dalam
pencarian
suatu
sasaran
(goal)
(http://www.ummi.ac.id/ti/konvert_pdf.php?kode=VGxFOVBRPT0=). Permainan Seeking Path adalah sebuah permainan pencarian jalur dari sumber ke tujuan dengan sasaran untuk memperoleh jarak terpendek yang ditempuh. Permainan ini akan dilengkapi dengan sebuah fasilitas hint yang dapat digunakan untuk membantu pemain dalam menentukan langkah selanjutnya yang harus dilalui untuk mencapai tujuan.
2.3.
Algoritma Algoritma adalah suatu kumpulan terhingga (finite set) dari instruksi yang
terdefinisi dengan baik (well-defined instructions) untuk menyelesaikan beberapa pekerjaan dimana diberikan state awal (initial state) dan akan dihentikan pada saat ditemukan state akhir (end-state) yang dikenal. Algoritma dapat diimplementasikan dalam pembuatan program komputer. Kesalahan dalam merancang algoritma untuk menyelesaikan suatu problema dapat menyebabkan program gagal dalam implementasinya. Konsep dari suatu algoritma sering diilustrasikan dengan mengambil contoh sebuah resep, walaupun banyak algoritma yang jauh lebih kompleks. Algoritma sering memiliki beberapa langkah perulangan (iterasi) atau memerlukan pengambilan keputusan seperti logika (logic) atau perbandingan (comparison) sampai pekerjaan diselesaikan. Menerapkan suatu algoritma secara
8
benar belum tentu dapat menyelesaikan problema. Hal ini dikarenakan adanya kemungkinan algoritma tersebut rusak atau cacat, atau penerapannya tidak cocok (tidak tepat) untuk menyelesaikan problema. Sebagai contoh, sebuah algoritma hipotesis untuk membuat sebuah salad kentang akan gagal jika tidak terdapat kentang. Suatu pekerjaan dapat diselesaikan dengan menggunakan algoritma yang berbeda dengan kumpulan instruksi (set of instructions) yang berbeda dengan perbedaan waktu akses, efisiensi tempat, usaha dan sebagainya. Sebagai contoh, diberikan dua buah resep yang berbeda untuk membuat salad kentang, resep pertama mengupas kulit kentang terlebih dahulu sebelum memasak kentang tersebut, sementara resep lainnya dilakukan dengan langkah yang terbalik, dan kedua resep akan mengulangi kedua langkah tersebut dan akan dihentikan pada saat salad kentang siap untuk dimakan. Algoritma adalah hal yang mendasar untuk komputer dalam memproses informasi, karena sebuah program komputer adalah sebuah algoritma yang memberitahukan kepada komputer langkah-langkah spesifik yang akan dijalankan (dalam urutan spesifik) untuk melakukan pekerjaan tertentu, misalnya menghitung gaji karyawan atau mencetak rapor murid. Oleh karena itu, algoritma dapat dianggap sebagai beberapa operasi sekuensial (terurut) yang dapat dijalankan oleh sebuah sistem lengkap Turing. (Munir, 2005: 495)
2.4.
All-Pairs Shortest Path Problema ini ditujukan untuk mencari shortest path dari semua pasangan
simpul pada sebuah graph. Salah satu contoh penerapan problema ini yaitu dalam
9
pembuatan tabel jarak terpendek antara semua pasangan kota dari suatu peta jalan. Seperti pada problema single-source shortest path, diberikan sebuah graph berbobot dan berarah G = (V, E) dengan fungsi bobot w : E R yang memetakan sisi ke sebuah nilai riil. Sasarannya adalah untuk setiap pasangan simpul u, v V, dicari sebuah jalur terpendek (berbobot paling minimum) dari u ke v, dimana bobot dari sebuah jalur adalah penjumlahan dari bobot sisi-sisinya. Hasil dari problema ini berupa sebuah tabel dimana nilai pada baris u dan kolom v merepresentasikan bobot shortest path dari u ke v. Cara termudah untuk menyelesaikan problema ini adalah dengan menjalankan algoritma single-source shortest path sebanyak V kali, sekali untuk setiap simpul sebagai simpul awal. Jika semua sisi berbobot positif, maka algoritma Djikstra dapat digunakan. Sedangkan, jika ada sisi yang berbobot negatif maka algoritma Djikstra tidak dapat digunakan. Untuk menyelesaikannya, dapat menggunakan algoritma Bellman-Ford yang lebih lambat. Cara lainnya yang memiliki waktu eksekusi yang lebih baik adalah dengan menggunakan algoritma Johnson dan Floyd-Warshall. Tidak seperti algoritma single-source shortest path yang kebanyakan menggunakan representasi adjacency-list, algoritma all-pairs shortest path ini menggunakan representasi adjacency matriks. Input dari algoritma berupa matriks W berukuran n x n yang merepresentasikan nilai bobot sisi dari sebuah graph berarah G = (V, E) dengan n buah simpul. (Cormen, et. al., 1990: 550) Nilai dari setiap elemen W = (wij) adalah:
(u, v) =
0
; jika i = j.
bobot dari sisi (i, j)
; jika i j dan (i, j) E.
; jika i j dan (i, j) E.
10
2.4.1. Graph Secara matematis, graph G dapat didefinisikan sebagai berikut: Graph G didefinisikan sebagai pasangan himpunan (V, E), ditulis dengan notasi G = (V, E), yang dalam hal ini V adalah himpunan tidak kosong dari simpul-simpul (vertices atau nodes) dan E adalah himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul. (Munir, 2005: 356) Definisi ini menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi, sebuah graph dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada, minimal satu. Graph yang hanya mempunyai satu buah simpul tanpa sebuah sisi pun dinamakan graph trivial. (Munir, 2005: 356) Simpul pada graph dapat dinomori dengan huruf, seperti a, b, c, …, v, w, …, atau dengan bilangan asli 1, 2, 3, … ataupun dengan gabungan keduanya. Sedangkan sisi yang menghubungkan simpul u dengan simpul v dinyatakan dengan pasangan (u, v) atau dinyatakan dengan lambang e1, e2, …. Dengan kata lain, jika e adalah sisi yang menghubungkan simpul u dengan simpul v, maka e dapat ditulis sebagai : e = (u, v) Secara geometri graph digambarkan sebagai sekumpulan noktah (simpul) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis (sisi). (Munir, 2005: 356) Beberapa contoh graph dapat dilihat pada gambar 2.1.
11
1
1 e1
2
3 e6
e5
e4
e1
e3
e2
2
3
1 e4
e7
e3
e2
2
e6
e5
4
4
4
(a) G1
(b) G2
(c) G3
3 e7
Gambar 2.1 Tiga buah graph (a) graph sederhana, (b) graph ganda, dan (c) graph semu Sumber: Munir, 2005: 356 Gambar 2.1 memperlihatkan tiga buah graph, G1, G2 dan G3. G1 adalah graph dengan himpunan simpul V dan himpunan sisi E adalah: G1 adalah graph dengan himpunan simpul V dan himpunan sisi E, yaitu: V = { 1, 2, 3, 4 } E = { (1, 2), (1, 3), (2, 4), (3, 4) } G2 adalah graph dengan himpunan simpul V dan himpunan sisi E, yaitu: V = { 1, 2, 3, 4 } E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4) } himpunan ganda = { e1, e2, e3, e4, e5, e6, e7 } G3 adalah graph dengan himpunan simpul V dan himpunan sisi E yaitu : V = { 1, 2, 3, 4 } E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3) } himpunan ganda = { e1, e2, e3, e4, e5, e6, e7, e8 } Pada graph G2, sisi e3 = {1, 3} dan sisi e4 = {1, 3} dinamakan sisi ganda (multiple edges atau paralel edges) karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3. Pada graph G3, sisi e8 = (3, 3) dinamakan
e8
12
gelang atau kalang (loop) karena berawal dan berakhir pada simpul yang sama. (Munir, 2005: 356)
2.4.2. Jenis-Jenis Graph Graph dapat dikelompokkan menjadi beberapa kategori bergantung pada sudut pandang pengelompokannya. Pengelompokan graph dapat dipandang berdasarkan ada tidaknya sisi ganda atau sisi kalang, berdasarkan jumlah simpul atau berdasarkan orientasi arah pada sisi. Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graph, maka secara umum graph dapat digolongkan menjadi dua jenis : 1. Graph sederhana (simple graph). Graph yang tidak mengandung gelang maupun sisi ganda dinamakan graph sederhana.
Gambar
2.1
(a)
adalah
contoh
merepresentasikan jaringan komputer. Simpul
graph
sederhana
yang
menyatakan komputer,
sedangkan sisi menyatakan saluran telepon untuk berkomunikasi. Saluran telepon dapat beroperasi pada dua arah. Pada graph sederhana, sisi adalah pasangan tak terurut (unordered pairs). Jadi, menuliskan sisi (u, v) sama saja dengan (v, u). Atau dapat juga mendefinisikan graph sederhana G = (V, E) terdiri dari himpunan tidak kosong simpul-simpul dan E adalah himpunan pasangan tak terurut yang berbeda yang disebut sisi. 2. Graph tak sederhana (unsimple graph). Graph yang mengandung sisi ganda atau gelang dinamakan graph tak sederhana (unsimple graph). Ada dua macam graph tak sederhana, yaitu graph ganda (multigraph) dan graph semu (pseudograph). Graph ganda
13
adalah graph yang mengandung sisi ganda. Sisi ganda yang menghubungkan sepasang simpul bisa lebih dari dua buah. Gambar 2.1 (b) merupakan contoh graph ganda. Sisi ganda dapat diasosiasikan sebagai pasangan tak terurut yang sama. Atau dapat juga mendefinisikan graph ganda G = {V, E} terdiri dari himpunan tidak kosong simpul-simpul dan E adalah himpunan ganda (multiset) yang mengandung sisi ganda. Pada jaringan telekomunikasi, sisi ganda pada graph G2 dapat diandaikan sebagai saluran telepon tambahan apabila beban komunikasi data antar komputer sangat padat. Setiap graph sederhana juga adalah graph ganda, tetapi tidak setiap graph ganda merupakan graph sederhana. Graph semu adalah graph yang mengandung gelang (loop), Gambar 2.1 (c) adalah graph semu (termasuk bila memiliki sisi ganda sekalipun). Sisi gelang pada graph G3 dapat dianggap sebagai saluran telepon tambahan yang menghubungkan komputer dengan dirinya sendiri (mungkin untuk tujuan diagnostik). Graph semu lebih umum daripada graph ganda, karena sisi pada graph semu dapat terhubung ke dirinya sendiri. Jumlah simpul pada graph dapat disebut sebagai kardinalitas graph dinyatakan dengan n = |V| dan jumlah sisi dinyatakan dengan m = |E|. Pada contoh gambar 2.1 diatas, graph G1 mempunyai n = 4 dan m = 4, sedangkan graph G2 mempunyai n = 3 dan m = 4. (Munir, 2005: 357) Berdasarkan orientasi arah pada sisi graph, maka secara umum graph dapat dibedakan atas 2 jenis :
14
1. Graph tak berarah (undirected graph). Graph yang sisinya tidak mempunyai orientasi arah disebut graph tak berarah. Pada graph tak berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Jadi, (u, v) = (v, u) adalah sisi yang sama. Tiga buah graph pada Gambar 2.1 adalah graph tak berarah. Pada jaringan telepon, sisi pada graph menyatakan bahwa saluran telepon dapat beroperasi pada dua arah. 2. Graph berarah (directed graph atau digraph). Graph yang setiap sisinya diberikan orientasi arah disebut sebagai graph berarah. Sisi berarah dapat juga disebut sebagai busur (arc). Pada graph berarah (u, v) dan (v, u) menyatakan dua buah busur yang berbeda, dengan kata lain (u, v) (v, u). Untuk busur (u, v), simpul u dinamakan simpul asal (initial vertex) dan simpul v dinamakan simpul terminal (terminal vertex). (Munir, 2005: 358) 1
2
1
3
4
2
3
4
Gambar 2.2 (a) Graph Berarah, (b) Graph Ganda Berarah Sumber: Munir, 2005: 359 Gambar 2.2 (a) adalah contoh graph berarah. Pada graph G4 dapat dibayangkan sebagai saluran telepon yang tidak dapat beroperasi dua arah. Saluran hanya beroperasi pada arah yang ditunjukkan oleh anak panah. Jadi, sebagai contoh, saluran telepon (1,2) tidak sama dengan saluran telepon (2,1). Graph berarah sering dipakai untuk menggambarkan aliran proses, peta lalu lintas suatu kota (jalan searah atau dua arah) dan sebagainya. Pada graph berarah,
15
gelang diperbolehkan, tetapi sisi ganda tidak. Definisi graph dapat diperluas sehingga mencakup graph ganda berarah (directed multigraph). Pada graph ganda berarah, gelang dan sisi ganda diperbolehkan ada. Contoh graph ganda berarah dapat dilihat pada gambar 2.2 (b). Perbandingan antara jenis-jenis graph dapat diringkas dalam tabel 2.1 berikut ini. Tabel 2.1 Perbandingan jenis-jenis graph Jenis
Sisi
Sisi ganda
Sisi gelang
Graph sederhana
Tak berarah
Tidak
Tidak
Graph ganda
Tak berarah
Ya
Tidak
Graph semu
Tak berarah
Ya
Ya
Graph berarah
Berarah
Tidak
Ya
Graph ganda berarah
Berarah
Ya
Ya
Sumber: Munir, 2005: 359
2.4.3. Istilah-Istilah Dasar dalam Graph Di bawah ini akan didefinisikan beberapa terminologi (istilah) yang berkaitan dengan graph dan sering dipakai. 1. Bertetangga (Adjacent) Dua buah simpul pada graph tak berarah G dikatakan bertetangga bila keduanya terhubung langsung dengan sebuah sisi. Dengan kata lain, u bertetangga dengan v jika (u, v) adalah sebuah sisi pada graph G. Pada graph berarah, sisi disebut busur,. Jika (u, v) adalah busur,maka u dikatakan bertetangga dengan v dan v dikatakan sebagai tetangga dari u.
16
2. Bersisian (Incident) Untuk sembarang sisi e = (u, v), sisi e dikatakan bersisian dengan simpul u dan simpul v. 3. Graph Kosong (Null Graph atau Empty Graph) Graph yang himpunan sisinya merupakan himpunan kosong disebut sebagai graph kosong dan ditulis sebagai Nn, yang dalam hal ini n adalah jumlah simpul. 4. Lintasan (Path) Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graph G adalah barisan berselang-selng simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1, e2, v2, …, vn – 1,en, vn sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2), …, en = (vn – 1, vn) adalah sisi-sisi dari graph G. Jika graph yang ditinjau adalah graph sederhana, maka cukup menuliskan lintasan sebagai barisan simpul-simpul saja : v0, v1, v2, …, vn – 1, vn, karena antara dua buah simpul berurutan di dalam lintasan tersebut hanya ada satu sisi. Pada graph yang mengandung sisi ganda, harus ditulis lintasan sebagai barisan berselang-seling antara simpul dan sisi menghindari kerancuan sisi manan dari sisi-sisi ganda yang dilalui. Simpul dan sisi yang dilalui di dalam lintasan boleh berulang. Sebuah lintasan dikatakan lintasan sederhana (simple path) jika semua simpulnya berbeda (setiap sisi yang dilalui hanya satu kali). Lintasan yang berawal dan berakhir pada simpul yang sama disebut lintasan tertutup (closed path), sedangkan lintasan yang tidak berawal dan berakhir pada simpul yang sama disebut
17
lintasan terbuka (open path). Panjang lintasan adalah jumlah sisi dalam lintasan tersebut. 5. Siklus (Cycle) atau Sirkuit (Circuit) Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus. Panjang sirkuit adalah jumlah sisi di dalam sirkuit tersebut. Sebuah sirkuit dikatakan sirkuit sederhana (simple circuit) jika setiap sisi yang dilalui berbeda. 6. Terhubung (Connected) Keterhubungan dua buah simpul adalah penting di dalam graph. Dua buah simpul u dan simpul v dikatakan terhubung jika terdapat lintasan dari u ke v. Jika dua buah simpul terhubung maka pasti simpul yang pertama dapat dicapai dari simpul yang kedua. Dua simpul terminal pada jaringan komputer hanya dapat berkomuniksi bila keduanya terhubung. Jika setiap pasang simpul di dalam graph terhubung, maka graph tersebut dikatakan graph terhubung. Secara formal, definisi graph terhubung adalah sebagai berikut : “Graph tak berarah G disebut graph terhubung (connected graph) jika untuk setiap pasang simpul u dan v di dalam himpunan V terdapat lintasan dari u ke v (yang juga harus berarti ada lintasan dari u ke v). Jika tidak, maka G disebut graph tak terhubung (disconnected graph)”. Graph yang hanya terdiri atas satu simpul saja (tidak ada sisi) tetap dikatakan terhubung, karena simpul tunggalnya terhubung dengan dirinya sendiri. Pada graph berarah, definisi graph terhubung dirumuskan sebagai berikut : “Graph berarah G dikatakan terhubung jika graph tak berarahnya terhubung (graph tak berarah dari G diperoleh dengan menghilangkan arahnya)”.
18
Keterhubungan dua buah simpul pada graph berarah dibedakan menjadi terhubung kuat dan terhubung lemah. Dua simpul, u dan v pada graph berarah G disebut terhubung kuat (strongly connected) jika terdapat lintasan berarah dari u ke v, dan juga sebaliknya lintasan berarah dari v ke u. Jika u dan v tidak terhubung kuat tetapi tetap terhubung pada graph tak berarahnya, maka u dan v dikatakan terhubung lemah (weakly connected). Kedua hal tersebut (terhubung kuat dan terhubung lemah) melahirkan definisi graph terhubung kuat berikut : “Graph berarah G disebut graph terhubung kuat (strongly connected graph) apabila untuk setiap pasang simpul sembarang vi dan vj di G terhubung kuat. Kalau tidak, G disebut graph terhubung lemah. (Munir, 2005: 364)
2.4.4. Shortest Path Seorang pengendara sepeda motor ingin menemukan rute terpendek yang dapat dilalui dari Chicago ke Boston. Diberikan sebuah peta jalan dari Amerika Serikat dimana setiap daerah yang dapat dilalui dengan jalur darat dengan jarak tertentu ditandai / dihubungkan, bagaimana cara menentukan rute terpendek ini ? Salah satu cara yang dapat dilakukan adalah dengan menjabarkan semua rute yang mungkin dari Chicago ke Boston, menghitung jarak dari setiap rute tersebut dan mengambil rute dengan jarak terpendek dari kumpulan rute tersebut. Cara ini sangat tidak efisien dan akan memakan waktu yang sangat lama dalam mencari solusi rute terpendek tersebut karena bisa terdapat banyak sekali rute yang dapat dilalui dari Chicago ke Boston.
19
Cara lainnya yang lebih efisien adalah dengan menerapkan algoritma shortest path pada graph. Dalam sebuah problema shortest path, diberikan sebuah graph berbobot dan berarah G = (V, E), dengan fungsi bobot w : E R memetakan sisi (edge) dengan nilai bobot riil. Bobot dari path p = {v0, v1, ..., vk} adalah penjumlahan bobot dari setiap sisinya seperti ditunjukkan oleh rumusan berikut: k
w(p) = ∑ w(vi-1,vi) i=1
Kemudian, didefinisikan bobot shortest path dari u ke v dengan rumusan berikut: (u, v) =
min{w(p) : u v}
; jika terdapat path dari u ke v.
; jika tidak terdapat path.
Shortest path dari simpul u ke simpul v dapat didefinisikan sebagai sembarang path p dengan bobot w(p) = (u, v). Dalam contoh pencarian rute dari Chicago ke Boston, peta jalan dapat dimodelkan sebagai sebuah graph dimana simpul mewakili daerah, sisi mewakili jalan antar daerah yang dapat dilalui dan bobot sisi mewakili jarak jalan. Sasarannya adalah menemukan shortest path dari Chicago ke Boston. (Cormen, et. al., 1990: 514) Algoritma shortest path ini dapat diterapkan untuk mencari solusi dari beberapa variasi dari shortest path seperti: 1. Single-destination shortest path Problema ini ditujukan untuk mencari shortest path dari sebuah simpul tujuan t yang telah ditentukan dari setiap simpul v. Problema ini dapat diselesaikan dengan membalikkan arah dari setiap sisi pada graph, sehingga penyelesaian problema ini sama persis dengan problema single-source shortest path.
20
2. Single-pair shortest path Problema ini ditujukan untuk mencari shortest path dari u ke v untuk simpul u dan v yang ditentukan. Problema ini disebut juga dengan problema singlesource shortest path. 3. All-pairs shortest path Problema ini ditujukan untuk mencari shortest path dari u ke v untuk setiap pasangan simpul u dan v. Problema ini dapat diselesaikan dengan menerapkan algoritma single-source shortest path sekali dari setiap simpul, tetapi ada algoritma spesifik lain yang dapat menyelesaikan problema ini dengan lebih cepat. (Cormen, et. al., 1990: 515)
2.4.5. Algoritma Floyd-Warshall Algoritma ini menerapkan konsep dynamic programming dalam mencari all-pairs shortest-path dari sebuah graph. Algoritma ini memiliki kompleksitas waktu sebesar O(V3). Proses kerja dari algoritma ini adalah sebagai berikut: 1. Algoritma proses perhitungan shortest path. Floyd-Warshall(d, n) 1.
for k 1 to n
2. 3.
for j 1 to n for i 1 to n
4.
dij(k) = min(dij(k-1), dik(k-1) + dkj(k-1))
5.
if choose dik(k-1) + dkj(k-1) then pred(i,j) = k
2. Algoritma proses penentuan rute dari shortest path. Path(i, j)
21
1.
if pred(i, j) = nil then return output(i, j)
2. 3.
else
4.
path(i, pred(i, j))
5.
path(pred(i, j), j)
Konsep dasar dari algoritma shortest path Floyd Warshall: 1. Jika yang diambil dij(k-1), maka shortest path-nya adalah edge (i, j) itu sendiri. 2. Jika yang diambil dik(k-1) + dkj(k-1), maka shortest path-nya bukan edge (i, j), melainkan hubungan lainnya yang merupakan gabungan dari beberapa edge. 3. Nilai dij(k) terakhir yang dihasilkan merupakan solusi all pairs shortest path.
BAB III METODE PENELITIAN
3.1.
Tempat dan Jadwal Penelitian Penelitian dimulai dari bulan Desember 2014 dan berakhir pada bulan
April 2015. Lokasi yang diambil penulis sebagai tempat penelitian adalah perpustakaan STMIK TIME dan rumah peneliti. Berikut ini dijabarkan jadwal penelitian yang dapat dilihat pada Tabel 3.1. Tabel 3.1 Jadwal Penelitian Waktu Kegiatan
Desember 2014 1
2
3
4
Januari 2015 1
2
3
Februari 2015 4
1
2
3
4
Maret 2015 1
2
3
April 2015 4
1
2
3
4
Identifikasi Masalah Pengumpulan Data Analisa Sistem Perancangan Sistem Pembangunan Sistem Uji Coba Sistem Penulisan Skripsi
3.2.
Kerangka Kerja Adapun tahapan dan langkah-langkah pengembangan perangkat lunak ini
dapat digambarkan dalam bentuk diagram alir seperti diperlihatkan pada Gambar 3.1.
22
23
Identifikasi Masalah
Pengumpulan Data
Analisa Sistem
Perancangan Sistem
Pembangunan Sistem
Uji Coba Sistem
Penulisan Skripsi
Gambar 3.1 Kerangka Kerja
3.2.1. Pengumpulan Data Di tahap pertama, penulis mengumpulkan data yang diperlukan dalam penyusunan skripsi. Data tersebut dikumpulkan dari buku dan sumber-sumber lainnya di internet. Gambar yang diperlukan dalam pembuatan perangkat lunak diambil dari
24
gambar themes Microsoft Power Point versi 2007 yang diubah warna latarnya dan juga beberapa gambar yang bersumber dari internet dan di-edit dengan menggunakan aplikasi Adobe Photoshop C.S versi 5.0. Selain itu, juga digunakan beberapa gambar yang diunduh dari internet.
3.2.2. Analisa Sistem Setelah dipelajari, penulis memilih dan menetapkan algoritma Floyd Warshall sebagai algoritma yang akan digunakan dalam menyelesaikan masalah shortest path. Penulis juga melakukan analisa ulang terhadap data sebelumnya, untuk menyimpulkan lebih rinci masalah yang akan diselesaikan serta tujuan penelitian dari penulis.
3.2.3. Perancangan Sistem Dalam tahap desain pada siklus hidup pengembangan sistem, penganalisa sistem menggunakan informasi yang terkumpul sebelumnya untuk mencapai desain sistem yang diinginkan. Penganalisa menggunakan teknik flowchart dan perancangan layar tertentu untuk menjamin keefektifan input sistem. Perangkat lunak untuk menentukan shortest path dengan algoritma Floyd Warshall ini dirancang dengan menggunakan bahasa pemrograman Microsoft Visual Basic 2010 dengan menggunakan beberapa objek dasar seperti : 1. Label, yang digunakan untuk menampilkan keterangan. 2. ComboBox, yang digunakan untuk menyediakan pilihan node awal dan node akhir. 3. Button, yang digunakan sebagai tombol eksekusi.
25
4. PictureBox, yang digunakan untuk menampilkan graph hasil. 5. SaveFileDialog, yang digunakan untuk menampilkan dialog save. 6. OpenFileDialog, yang digunakan untuk menampilkan dialog open. 7. TextBox, yang digunakan untuk menampilkan hasil proses perhitungan.
3.2.4. Pembangunan Sistem Dalam tahap kelima pada siklus hidup pengembangan sistem, penganalisa mengembangkan suatu perangkat lunak awal yang diperlukan. Teknik terstruktur yang digunakan untuk merancang dan mendokumentasikan perangkat lunak adalah pseudocode. Penganalisa sistem menggunakan perangkat ini untuk memprogram apa yang perlu diprogram. Rancangan tampilan dari perangkat lunak untuk menentukan shortest path dengan algoritma Floyd Warshall ini dapat dirincikan sebagai berikut: 1. Form ‘Splash Screen’. 2. Form ‘Awal’. 3. Form ‘Permainan’. 4. Form ‘Mengenai’.
3.2.5. Uji Coba Sistem Sebelum sistem dapat digunakan, maka harus dilakukan pengujian terlebih dulu, sehingga dapat menghemat biaya jika mengetahui adanya masalah sebelum sistem tersebut dijalankan. Sebagian besar pengujian dilakukan oleh pemrogram sendiri, selaku penganalisa sistem.
BAB IV ANALISA DAN PERANCANGAN
4.1.
Analisa Algoritma Floyd-Warshall dapat digunakan untuk menentukan shortest
path dari semua pasangan simpul yang terdapat pada graph ataupun disebut dengan problema all-pairs shortest path yang merupakan pengembangan dari problema single-source shortest path.
4.1.1. Analisa Proses Kerja Algoritma Floyd-Warshall Algoritma Floyd-Warshall menerapkan konsep dynamic programming, yaitu menyelesaikan problema dengan mencari dan mengkombinasikan solusi dari subproblema-subproblema yang terdapat dalam problema tersebut. Pengembangan dari algoritma dynamic programming dapat dibagi menjadi 4 langkah yang dilakukan secara berurutan, yaitu: 1. Kenali struktur dari sebuah solusi optimal (Characterize the structure of an optimal solution). 2. Secara berulang menetapkan nilai dari sebuah solusi optimal (Recursively define the value of an optimal solution). 3. Hitung nilai dari sebuah solusi optimal dengan pola bottom-up (Compute the value of an optimal solution in a bottom-up fashion). 4. Cari sebuah solusi optimal dari informasi yang telah dihasilkan (Construct an optimal solution from computed information).
26
27
Langkah ke-1 sampai langkah ke-3 merupakan dasar dari solusi dynamic programming pada suatu masalah. Langkah 4 dapat diabaikan hanya jika nilai dari solusi optimal dibutuhkan. Ketika mengerjakan langkah ke-4, terkadang memerlukan informasi tambahan selama proses perhitungan pada langkah ke-3 untuk memudahkan pencarian solusi optimal. Berdasarkan langkah dari algoritma dynamic programming di atas, maka proses pencarian shortest path dari algoritma Floyd-Warshall dapat dibagi menjadi beberapa bagian, yaitu: 1. Langkah pertama: Kenali struktur dari all-pairs shortest path. Semua subpath dari shortest path yang diperoleh pada problema all-pairs shortest path juga merupakan shortest path juga. Kenali juga bentuk representasi graph yang digunakan untuk merepresentasikan graph input. Algoritma Floyd-Warshall ini menggunakan bentuk representasi adjacency-matrix sebagai bentuk representasi graph-nya. Pada langkah ini, ditentukan besar orde dari matriks D yang akan digunakan untuk menghitung nilai shortest path. Jumlah orde dari matriks D adalah sebesar n, dimana n adalah jumlah simpul yang terdapat dalam graph input. 2. Langkah kedua: Hitunglah nilai dari matriks D(0) = (dij) yang berorde n x n. Matriks D(0) ini merupakan nilai awal yang akan digunakan untuk menghitung nilai shortest path pada langkah selanjutnya. Proses penentuan nilai dari matriks D(0) ini menggunakan rumusan berikut: 0 ; jika i = j dij(0) =
w {bobot sisi (i, j)} ; jika i j dan ada sisi (i, j) ; jika i j dan tidak ada sisi (i, j)
28
Proses kerja dari langkah ini dapat dilihat pada gambar 4.1 berikut: Mulai
Untuk i = 1 sampai n
Untuk j = 1 sampai n
i=j
Ya
Tidak
Ya
Ada sisi (i, j)
dij(0) = 0
Tidak
dij(0) = w(i, j)
dij(0) =
Selesai
Gambar 4.1 Proses Penentuan Nilai Awal dari Matriks D = (dij) pada Algoritma Floyd-Warshall Dalam proses perancangan perangkat lunak, matriks D = (dij) menggunakan struktur data array tiga dimensi (i, j, k). Untuk nilai tak terhingga, diasumsikan bahwa nilai tersebut lebih besar dari nilai terbesar yang diperbolehkan saja. Dalam hal ini, nilai tersebut lebih besar daripada 100 dan diambil nilai 101 untuk mewakili nilai tak terhingga tersebut dalam perangkat lunak. 3. Langkah ketiga: Hitunglah nilai shortest path dari graph input. Pada langkah ini diperlukan sebuah simpul intermediate k sebagai penengah antara dua buah simpul i dan j yang terdapat dalam graph. Simpul k merupakan simpul yang berada dalam himpunan set simpul {i, …, j}. Simpul k ini dapat digunakan
29
ataupun tidak, tergantung dari nilai yang diperoleh. Jika jalur yang melalui simpul k ini memiliki nilai yang lebih kecil daripada nilai dari sisi (i, j), maka jalur dari simpul k ini yang digunakan. Jika tidak, maka sisi (i, j) yang digunakan. Proses perhitungan dimulai dari pasangan simpul asal dan tujuan dan dipersempit hingga didapatkan kumpulan simpul yang membentuk jalur terpendek (shortest path). Dalam algoritma, nilai k merupakan jumlah perulangan perhitungan yang harus dilakukan terhadap setiap sisi (i, j) pada graph. Proses kerja dari perhitungan nilai shortest path ini dapat dilihat pada gambar 4.2 berikut: Mulai
Untuk k = 1 sampai n
Untuk j = 1 sampai n
Untuk i = 1 sampai n
dij(k) = min(dij(k-1), dik(k-1) + dkj(k-1))
Jika nilai dik(k-1) + dkj(k-1) yang dipilih
Tidak
Ya
pred(i,j) = k
pred(i,j) = null
Shortest path = kumpulan nilai dij(n)
Selesai
Gambar 4.2 Proses Perhitungan Nilai Shortest Path pada Algoritma FloydWarshall
30
4. Langkah keempat: Tentukan jalur (rute) dari shortest path. Untuk menyelesaikan langkah ini, diperlukan nilai dari variabel pred(i,j) yang dihasilkan pada proses sebelumnya, dimana nilai dari variabel ini menunjukkan simpul sebelumnya yang menghubungkan sisi (i, j) ini (simpul pendahulu). Untuk itu, perlu dirancang sebuah algoritma rekursif yang memanggil nilai dari variabel pred(i,j) hingga variabel tersebut bernilai null (kosong), yang berarti bahwa proses pencarian telah mencapai simpul awal (simpul asal) sehingga proses telah selesai. Proses kerja dari langkah ini dapat dilihat pada gambar 4.3 berikut: Mulai
pred(i, j) = 0
Ya
Tidak
j = pred(i, j)
Path = sisi (i, j)
i = pred(i, j)
Selesai
Gambar 4.3 Proses Penentuan Shortest Path pada Algoritma Floyd-Warshall
Contoh : Misalkan diketahui sebuah graph berarah seperti terlihat pada gambar 4.4 berikut:
31
2
4
3 8
1
3
7 -4
1
2
5
-5
4
6
Gambar 4.4 Contoh Graph Berarah Proses kerja dari algoritma Floyd-Warshall dalam mencari all-pairs shortest path dari graph berarah di atas adalah sebagai berikut: 1. Hitung nilai matriks D(0) : Tabel 4.1 Matriks D(0) j
1
2
3
4
5
1
0
3
8
-4
2
0
1
7
3
4
0
4
2
-5
0
5
6
0
i
2. Hitung nilai matriks D(1) sampai D(5) dengan menggunakan rumusan dij(k) = min(dij(k-1), dik(k-1) + dkj(k-1)) :
32
Tabel 4.2 Matriks D(1) j
1
2
3
4
5
1
0
3
8
-4
2
0
1
7
3
4
0
4
2
5
-5
0
-2
5
6
0
i
Tabel 4.3 Matriks D(2) j
1
2
3
4
5
1
0
3
8
4
-4
2
0
1
7
3
4
0
5
11
4
2
5
-5
0
-2
5
6
0
i
Tabel 4.4 Matriks D(3) j
1
2
3
4
5
1
0
3
8
4
-4
2
0
1
7
3
4
0
5
11
4
2
-1
-5
0
-2
5
6
0
i
33
Tabel 4.5 Matriks D(4) j
1
2
3
4
5
1
0
3
-1
4
-4
2
3
0
-4
1
-1
3
7
4
0
5
3
4
2
-1
-5
0
-2
5
8
5
1
6
0
i
Tabel 4.6 Matriks D(5) j
1
2
3
4
5
1
0
1
-3
2
-4
2
3
0
-4
1
-1
3
7
4
0
5
3
4
2
-1
-5
0
-2
5
8
5
1
6
0
i
Matriks D(5) di atas merupakan solusi dari all-pairs shortest path, dimana nilai dari baris ke-i dan kolom ke-j merupakan shortest path dari node-i ke node-j. Contoh nilai pada i = 1 dan j = 2 yaitu sebesar 1 merupakan nilai shortest path dari node 1 ke node 2.
4.1.2. Analisa Kebutuhan Kebutuhan yang harus dipenuhi oleh permainan yang akan dibangun ini dapat dirincikan sebagai berikut:
34
1. Permainan terdiri dari tiga jenis tingkat kesulitan yaitu: a. Level 1 sampai level 10 merupakan tingkat kesulitan ‘Mudah’ dengan jumlah kotak sebesar 12 x 12. b. Level 11 sampai level 20 merupakan tingkat kesulitan ‘Sedang’ dengan jumlah kotak sebesar 14 x 14. c. Level 21 sampai level 30 merupakan tingkat kesulitan ‘Sulit’ dengan jumlah kotak sebesar 16 x 16. 2. Permainan akan dimainkan dengan menggunakan batasan waktu, dimana waktu akan berkurang 1 detik per kenaikan level dan sisa waktu akan diakumulasikan ke level berikutnya, dengan waktu awal dimulai dari 30 detik. 3. Nilai ditentukan dengan menghitung total panjang path yang diperoleh. Nilai yang diperoleh merupakan kelipatan dari level. Cara perhitungannya adalah: {nSize x nSize} – {Panjang path} + 10
4.2.
Perancangan Perangkat lunak permainan Seeking Path dengan algoritma All-Pairs
Shortest-Path Floyd-Warshall ini dirancang dengan menggunakan bahasa pemrograman Microsoft Visual Basic 2010 dengan menggunakan beberapa objek dasar seperti : 1. Label, yang digunakan untuk menampilkan keterangan dan nama simpul. 2. Button, yang digunakan sebagai tombol eksekusi. 3. Picturebox, yang digunakan untuk menampilkan simpul graph. 4. Save file dialog, yang digunakan untuk menampilkan dialog save. 5. Open file dialog, yang digunakan untuk menampilkan dialog open.
35
6. Textbox, yang digunakan untuk menampilkan hasil proses perhitungan. 7. Combobox, yang digunakan untuk menyediakan pilihan.
4.2.1. Perancangan Tampilan Rancangan tampilan dari perangkat lunak permainan Seeking Path dengan algoritma All-Pairs Shortest-Path Floyd-Warshall ini dapat dirincikan sebagai berikut: 1. Form ‘Main’. 2. Form ‘Pilih User’. 3. Form ‘Permainan’. 4. Form ‘High Score’ 5. Form ‘About’.
4.2.1.1 Form ‘Main’ Form ini merupakan form pembuka (awal) dari perangkat lunak dan juga form inti dari perangkat lunak yang berfungsi untuk menghubungkan form-form yang ada pada perangkat lunak. Rancangan tampilan dari form ‘Main’ ini dapat dilihat pada gambar 4.5 berikut:
36
Permainan Seeking Path 1 Pilih User
2
Bermain
High Score 3 About 4 Keluar
5
Gambar 4.5 Rancangan Form ‘Main’ Keterangan : 1 : Link Label, berfungsi untuk menampilkan form Pilih User. 2 : Link Label, berfungsi untuk menampilkan form Permainan. 3 : Link Label, berfungsi untuk menampilkan form High Score. 4 : Link Label, berfungsi untuk menampilkan form About. 5 : Link Label, berfungsi untuk menutup aplikasi.
37
4.2.1.2 Form ‘Pilih User’ Form ‘Pilih User’, yang berfungsi sebagai tempat pemilihan nama pemain. Rancangan tampilan dari form ‘Pilih User’ ini dapat dilihat pada gambar 4.6 berikut ini:
Daftar User
1
Tambah
Hapus
Pilih
2
3
4
Batal
5
Gambar 4.6 Form Pilih User Keterangan: 1. Listbox user, yang digunakan untuk menampilkan daftar user yang tersimpan dalam database. 2. Tombol Tambah, yang digunakan untuk menampilkan form tambah user. 3. Tombol Hapus, yang digunakan untuk menghapus user. 4. Tombol Pilih, yang digunakan untuk memilih user. 5. Tombol Batal, yang digunakan untuk menutup form dan kembali ke form Main.
38
4.2.1.3 Form ‘Permainan’ Form ini berfungsi untuk menampilkan tempat permainan seeking path. Solusi dari permainan ini merupakan proses penentuan shortest path dengan menggunakan algoritma Floyd-Warshall. Rancangan tampilan dari form ‘Permainan’ dapat dilihat pada gambar 4.7 berikut :
1
3
2
Permainan Seeking Path Level
Sisa Waktu
Nilai
4
Hint
Restart
7
Keluar
5
Gambar 4.7 Rancangan Form ’Permainan’ Keterangan : 1 : Daerah tampilan informasi mengenai level permainan sekarang.
6
39
2 : Daerah tampilan informasi mengenai nilai yang diperoleh pemain sekarang. 3 : Daerah tampilan informasi mengenai sisa waktu permainan. 4 : Areal permainan. 5 : Tombol ’Restart’, berfungsi untuk mengulang permainan. 6 : Tombol ‘Keluar’, berfungsi untuk menutup form dan kembali ke form ’Main’. 7 : Tombol ‘Hint’, berfungsi untuk menampilkan bantuan kepada user mengenai langkah shortest path.
4.2.1.4 Form ‘High Score’ Form ‘High Score’, yang berfungsi untuk menampilkan sepuluh nilai tertinggi yang diperoleh pemain. Rancangan tampilan dari form ‘High Score’ ini dapat dilihat pada Gambar 4.8 berikut ini. High Score Nama
Level
Nilai
1
Hapus Semua
2
Gambar 4.8 Rancangan Form High Score
Keluar
3
40
Keterangan : 1 : Tabel tampilan 10 nilai tertinggi. 2 : Tombol ‘Hapus Semua’ untuk mengosongkan daftar nilai tertinggi. 3 : Tombol ’Keluar’, berfungsi untuk menutup form dan kembali ke form ’Main’.
4.2.1.5 Form ‘About’ Form ‘About’ berfungsi untuk menampilkan data pribadi dari pembuat perangkat lunak. Rancangan tampilan dari form ‘About’ dapat dilihat pada Gambar 4.9.
2
4 3
Tutup Form
1
Gambar 4.9 Rancangan Form About Keterangan: 1 : Tombol ‘Tutup Form’, berfungsi untuk menutup form dan kembali ke form ‘Main’. 2 : Daerah tampilan nama perangkat lunak. 3 : Daerah tampilan data pribadi pembuat perangkat lunak. 4 : Daerah tampilan gambar perangkat lunak.
41
4.2.2 Perancangan Database Database yang digunakan akan dirancang dengan menggunakan aplikasi Microsoft Access 2007. Tabel yang dirancang dapat dirincikan sebagai berikut: 1. Tabel HighScore yang digunakan untuk menyimpan data 10 nilai tertinggi dari user. Tabel 4.7 menunjukkan struktur tabel HighScore pada database. Tabel 4.7 Tabel HighScore
2. Tabel UserList yang digunakan untuk menyimpan data user yang terdaftar dalam sistem. Tabel 4.8 menunjukkan struktur tabel UserList pada database. Tabel 4.8 Tabel UserList
BAB V HASIL DAN PEMBAHASAN
5.1.
Hasil Berikut dijabarkan spesifikasi dari perangkat keras dan perangkat lunak
yang digunakan untuk menjalankan aplikasi permainan Seeking Path dan tampilan output dari sistem.
5.1.1. Spesifikasi Perangkat Keras dan Perangkat Lunak Perangkat keras dan perangkat lunak yang digunakan untuk menjalankan aplikasi permainan Seeking Path dengan algoritma All-Pairs Shortest-Path FloydWarshall ini memiliki spesifikasi sebagai berikut : 1.
Processor Intel Core 2 Duo 2,93 GHz
2.
Memory 1 GB.
3.
Monitor dengan resolusi 1028 768 pixel.
4.
Harddisk kapasitas 100GB
5.
Keyboard
6.
Mouse Perangkat lunak ini direkomendasikan untuk dijalankan di sistem operasi
Microsoft
Windows
XP.
Software
pendukung
Microsoft.NET Framework 4.0.
42
yang
digunakan
yaitu
43
5.1.2. Tampilan Hasil Untuk
menjalankan
aplikasi
permainan
Seeking
Path
dengan
menggunakan metode Floyd Warshall, maka dapat mengklik file ‘Shortest Path.exe’ sehingga sistem akan menampilkan tampilan awal berikut.
Gambar 5.1 Tampilan Awal
Untuk bermain permainan Seeking Path dengan Menggunakan Metode Floyd Warshall, maka pertama kali harus memilih nama user terlebih dahulu dengan mengklik link ‘Pilih User’, sehingga sistem akan menampilkan form Nama User berikut.
44
Gambar 5.2 Tampilan Nama User Pemakai dapat mengisi nama user baru dan mengklik tombol ‘OK’ untuk menyimpan data nama user ke dalam database. Untuk memilih nama user, maka pemakai dapat memilih pada daftar nama dan mengklik tombol ‘Pilih’ sehingga sistem akan menyimpan nama user yang dipilih ke dalam memori sementara dan menutup form Pilih User serta kembali ke tampilan awal. Untuk menambah user baru, maka pemakai dapat mengklik tombol ‘Tambah’ sehingga sistem akan menampilkan input box Tambah User seperti terlihat pada gambar berikut.
Gambar 5.3 Tampilan Tambah User
45
Setelah itu, pemain dapat bermain permainan Seeking Path dengan mengklik link ‘Permainan’, sehingga sistem akan menampilkan form Permainan berikut.
Gambar 5.4 Tampilan Permainan Pemain dapat menggerakkan mobil ke kiri, ke kanan, ke atas dan ke bawah dengan menekan tombol ‘A’ untuk bergeser ke kiri, ‘D’ untuk bergeser ke kanan, ‘W’ untuk bergeser ke atas dan ‘S’ untuk bergeser ke bawah. Pemain harus menyelesaikan permainan dalam waktu 30 detik, yaitu menggerakkan mobil menuju ke kotak kanan atas. Apabila pemain berhasil menggerakkan mobil mencapai posisi sudut kanan atas maka pemain akan memenangkan level yang bersangkutan dan permainan akan dilanjutkan ke level berikutnya. Tampilan form ketika pemain berhasil memenangkan permainan dapat dilihat pada gambar 5.5.
46
Gambar 5.5 Tampilan Ketika Berhasil Memenangkan Permainan Apabila pemain tidak berhasil menggerakkan mobil menuju ke sudut kanan atas dalam batasan waktu yang ditentukan maka permainan berakhir. Sistem akan menampilkan pesan pemberitahuan seperti terlihat pada gambar berikut.
Gambar 5.6 Tampilan Pesan Pemberitahuan Permainan Berakhir
47
Apabila permainan berakhir ataupun pemakai mengakhiri permainan, maka sistem akan menampilkan form High Score seperti terlihat pada gambar berikut.
Gambar 5.7 Tampilan High Score Terakhir, pemain dapat menampilkan informasi mengenai pembuat perangkat lunak dengan mengklik link ‘Mengenai’ sehingga sistem akan menampilkan form About seperti terlihat pada gambar berikut.
Gambar 5.8 Tampilan About
48
5.2.
Pembahasan Beberapa informasi yang dapat diperoleh dari hasil konstruksi perangkat
lunak, yaitu: 1. Metode Floyd Warshall dapat digunakan untuk mengecek solusi yang mungkin dari titik awal ke titik tujuan. 2. Aplikasi dapat digunakan untuk memainkan permainan Seeking Path pada sebuah komputer. Sedangkan, kelemahan dari aplikasi permainan Seeking Path dengan menggunakan metode Floyd Warshall ini yaitu: 1. Software tidak dapat dimainkan pada jaringan komputer ataupun internet. 2. Software tidak menyediakan fasilitas perancangan tempat bermain (board), sehingga pemakai tidak dapat merancang board yang diinginkan.
5.3.
Algoritma Algoritma yang digunakan untuk merancang perangkat lunak pemahaman
penentuan All-Pairs Shortest-Path pada Graph dengan algoritma Floyd-Warshall ini dapat dibagi menjadi 3 bagian besar yaitu: 1. Algoritma Penentuan Nilai Matriks D(0). 2. Algoritma Perhitungan Nilai Matriks D(1) – D(n). 3. Algoritma Ekstrak Path. Algoritma ini digunakan untuk melakukan proses pencarian all-pairs shortest path dengan menggunakan bantuan konsep dynamic programming. Algoritma ini dapat dibagi menjadi 3 bagian lagi, yaitu:
49
1. Algoritma Penentuan Nilai Matriks D(0), yang dapat dijabarkan sebagai berikut: Untuk I = 1 sampai JlhNode Untuk J = 1 sampai JlhNode Jika I = J maka ArrD(0, I, J) 0 Jika tidak, maka Jika [ada hubungan antara I dan J] maka ArrD(0, I, J) Ambil nilai dari hubungan I dan J Jika tidak, maka ArrD(0, I, J) 32000
2. Algoritma Perhitungan Nilai Matriks D(1) – D(n), yang dapat dijabarkan sebagai berikut: Untuk A = 1 sampai JlhNode Untuk B = 1 sampai JlhNode Jika ArrD(nStep - 1, A, nStep) = 32000 Or ArrD(nStep - 1, nStep, B) = 32000 maka nHitung 32000 Jika tidak, maka nHitung ArrD(nStep - 1, A, nStep) + ArrD(nStep - 1, nStep, B)
Jika nHitung < ArrD(nStep - 1, A, B) maka Pred(A, B) nStep ArrD(nStep, A, B) nHitung Jika tidak, maka ArrD(nStep, A, B) ArrD(nStep - 1, A, B)
3. Algoritma Ekstrak Path, yang dapat dijabarkan sebagai berikut: Function FPath(pnAwal, pnAkhir) Jika Pred(pnAwal, pnAkhir) = 0 maka FPath "(" + pnAwal + "," + pnAkhir + ")" Jika tidak, maka FPath FPath + FPath(pnAwal, Pred(pnAwal, pnAkhir)) FPath FPath + FPath(Pred(pnAwal, pnAkhir), pnAkhir)
BAB VI KESIMPULAN DAN SARAN
6.1.
Kesimpulan Setelah selesai mengkonstruksi perangkat lunak, penulis dapat mengambil
beberapa kesimpulan berikut: 1. Aplikasi menyediakan sebuah interface untuk bermain permainan Seeking Path dengan algoritma All-Pairs Shortest-Path Floyd-Warshall pada sebuah komputer. 2. Metode Floyd-Warshall dapat digunakan untuk mengecek solusi yang mungkin dari titik awal ke titik tujuan. 3. Perangkat lunak permainan Seeking Path dapat dibuat dengan menggunakan bahasa pemrograman Microsoft Visual Basic.NET 2010, namun animasi yang dihasilkan masih kurang bagus dan kurang menarik.
6.2.
Saran Penulis
ingin
memberikan
beberapa
saran
sehubungan
dengan
pengembangan perangkat lunak, seperti: 1. Aplikasi dapat dikembangkan dengan merancang permainan agar dapat dimainkan pada jaringan komputer ataupun internet. 2. Perangkat lunak dapat dikembangkan menjadi perangkat lunak berbasis multimedia dengan menambahkan efek animasi dan suara. 3. Dipertimbangkan untuk menambahkan metode pencarian lain yang terdapat dalam teori graph.
50
51
4. Kualitas animasi pergerakan mobil dapat ditingkatkan dengan menggunakan aplikasi Adobe Flash.
DAFTAR PUSTAKA
Cormen, H., Leiserson, E., Rivest, L., 1990, Introduction to Algorithms, Mc Graw Hill Book Company. Munir, R., 2005, Matematika Diskrit, Informatika Bandung. Munir, R., dan Lidia L., 2002, Algoritma dan Pemrograman, Edisi Kedua. Putra, R., 2005, The Best Source Code Visual Basic, PT. Elex Media Komputindo, Jakarta. Ramadhan, A., 2004, 36 Jam Belajar Komputer Visual Basic 6.0, PT. Elex Media Komputindo, Jakarta. en.wikipedia.org/wiki/Floyd–Warshall_algorithm, tanggal akses 17 Januari 2015. www.fet2005.cs.buap.mx/ADA/floyd-warshall.ppt, tanggal akses 17 Januari 2015. www.astahost.com/floyd-warshall-shortest-path-graphs-t17498.html, tanggal akses 17 Januari 2015. www.cse.ust.hk/faculty/golin/COMP271Sp03/Notes/MyL15.pdf, tanggal akses 17 Januari 2015. www.cs.rpi.edu/~musser/gp/algorithm-concepts/floyd-warshall-screen.pdf, akses 17 Januari 2015.
tanggal
en.wikipedia.org/wiki/Johnson's_algorithm, tanggal akses 17 Januari 2015. www.boost.org/doc/libs/1_35_0/libs/graph/doc/johnson_all_pairs_shortest.html, tanggal akses 17 Januari 2015. www.cs.arizona.edu/classes/cs445/spring07/ShortestPath3.prn.pdf, tanggal akses 17 Januari 2015. www.cs.rpi.edu/~musser/gp/algorithm-concepts/johnson-screen.pdf, tanggal akses 17 Januari 2015. cs.nyu.edu/courses/summer04/G22.1170-001/8a-ShortestPaths-More.ppt, akses 17 Januari 2015.
52
tanggal
