11
BAB 2 TINJAUAN PUSTAKA
Pada bab ini akan dibahas landasan teori yang digunakan dan konsep yang mendukung pembahasan, serta penjlasan mengenai metode yang digunakan.
2.1.
Lintasan Terpendek
Lintasan terpendek merupakan pencarian nilai variable yang diasumsikan dapat menghasilkan nilai yang optimal. Lintasan terpendek memiliki peranan penting dalam penyusunan system. Dengan lintasan terpendek dapat diperoleh hal – hal yang memiliki nilai profit tinggi serta meminimalkan jarak. Lintasan terpendek adalah termasuk bagian dari pada graph. Menentukan rute terpendek merupakan pencarian dari beberapa simpul yang berhubungan. Simpul tersebut sering dipersentasikan dalam bentuk graf berbobot. Graf yang digunakan untuk mencari lintasan tersebut diberikan nilai atau bobot. Bobot disini berfungsi untuk menyatakan jarak. Berbagai pendekatan algoritma yang ditawarkan untuk mendapatkan solusi untuk pencarian jalur terpendek. Salah satunya yaotu Algoritma Floyd Warshall.
2.2.
Graph
Graph pertama kali ditemukan oleh Leonhard Euler, seorang matematikawan kebangsaan Swiss pada tahun 1736. Dimana saat itu Euler berhasil menulis upaya pemecahan Jembatan Koningsberg yang terkenal di Rusia. Graph merupakan sebuah kumpulan yang terdiri dari titik (vertex) dan garis dimana pasangan titik – titik tersebut dihubungkan dengan segmen garis. Verteks ini sering disebut sebagai titik
Universitas Sumatera Utara
12
dan segmen garis disebut sebagai edge. Maka direpresentasikan dengan G = (V,E) (Lipschutz, 2002). Dalam matematika dan ilmu computer, teori graph adalah cabang kajian yang mempelajari sifat – sifat graph. Secara informal, suatu graph adalah himpunan benda – benda yang disebut simpul (vertex atau node) yang terhubung oleh sisi (edge) atau busur (arc). Biasanya graph digambarkan sebagai kumpulan titik – titik (melambangkan simpul) yang dihubungkan oleh garis – garis (melambangkan sisi) atau garis berpanah (melambangkan busur). Suatu sisi dapat menghubungkan suatu simpul dengan simpul yang sama. Sisi yang demikian dinamakan gelang (loop).
A
B D
C E
Gambar 2.1 Graph dengan 5 verteks dan 6 edge
Gambar 2.1 menggambarkan 5 verteks yaitu A, B, C, D dan E serta 6 edge yang menghubungkan antara vertex lainnya seperti AB, AC, BC, dan seterusnya. Graph terbagi atas dua jenis yaitu graph berarah (Directed Graph) dan graph tidak berarah (Undirected Graph). Graph berarah adalah suatu graph yang mana garis – garisnya memiliki arah. Sedangkan graph tidak berarah adalah dimana garis – garis dalam graph tidak memiliku arah.
Universitas Sumatera Utara
13
2.3.
Matriks
Matriks merupakan sekumpulan dari bilangan yang biasa dipakai untuk mengatur data dalam bentuk baris dan kolom (Suarga,2012). Matriks biasanya berbentuk persegi atau persegi panjang yang dirincikan dengan elemen – elemen penyusun yang diapit oleh tanda kurung siku [ ] atau dan tanda kurung biasa ( ). Ukuran sebuah matriks dinyatakan dalam satuan ordo, yaitu banyaknya baris dan kolom dalam matriks tersebut.
Gambar 2.2 Matriks A berukuran 3 x 3
Dalam hal ini, matiks dimanfaatkan untuk membentuk antara nilai – nilai yang berhubungan dengan titik lainnya. Sehingga nilai antara titik A dengan titik B dan seterusnya dapat dilihat dengan jelas.
2.4.
Algoritma Floyd Warshall Algoritma Floyd Warshall adalah salah satu algoritma dari pemograman
dinamis, yaitu metode yang melakukan pemecahan masalah dengan memandang solusi yang akan diperoleh sebagai sauatu keputusan yang saling terkait. Artinya solusi – solusi tersebut dibentuk dari solusi yang berasal dari tahap sebelumnya da nada kemungkinan lebih dari satu solusi (Cormen,2003). Rumus untuk shortestPath (i,j,k) bias ditulis sebagai suatu notasi rekursif sebagai berikut :
Universitas Sumatera Utara
14
[ S(E) = S(r) + E(r) ] (Cormen,2003)
Penjelasan : S(E) = Nilai jarak yang sebenarnya. S(r) = Nilai titik awal. E(r) = Nilai titik akhir.
Jumlah komputasi pada algoritma ini cukup lama dan memerlukan komputasi yang
cukup
besar
pada
resource
komputer.
Algoritma
Floyd
Warshall
membandingkan semua kemungkinan lintasan pada graf untuk setiap sisi dari semua simpul.
Tahapan Algoritma Floyd Warshall : Bentuklah sebuat matriks dari graph yang memiliki bobot. Isi sesuai hubungan antara vertex satu ke vertex lainnya. Bandingkan semua vertex dengan rumus ik + kj < ij, maka nilai ij diganti dengan nilai ik + kj. Setelah dibandingkan terhadap semua vertex, maka didapatkan hasil terkecil.
2.5.
Grafika Komputer
Grafika komputer sering dikenal dengan istilah visualisasi data. Grafika komputer merupakan bagian dari ilmu komputer yang berkaitan dengan pembuatan serta manipulasi gambar (visual) secara digital. Awalnya grafika komputer memiliki bentuk yang masih sederhana yaitu dua dimensi (2D), kemudian berkembang menjadi tiga dimensi (3D), pemrosesan citra (image processing) dan pengenalan pola (pattern recognition). Menurut Hudjuli (2012) bagian dari grafika komputer meliputi: (1) Geometri: mempelajari tentang cara menggambarkan permukaan bidang. Universitas Sumatera Utara 6 (2) Animasi: mempelajari tentang cara menggambarkan dan memanipulasi gerakan. (3) Rendering: mempelajari tentang algoritma untuk menampilkan efek cahaya. (4) Citra (Imaging): mempelajari tentang cara mengambil dan menyunting gambar.
Universitas Sumatera Utara
15
2.5.1. Grafik 3 Dimensi (3D) Menurut Basuki dan Nana (2009) objek tiga dimensi (3D) merupakan kumpulan titiktitik 3D (x, y, z) yang kemudian membentuk luasan-luasan (face) yang digabungakan menjadi satu kesatuan. Face merupakan gabungan titik-titik yang membentuk luasan tertentu atau sering dinamakan dengan sisi.
2.6.
Teknologi WebGl
WebGL singkatan dari Web-based Graphics Library merupakan Platform Application Programming Interfaces (APIs) library grafis 3D yang memungkinkan browser internet untuk membuat adegan 3D dengan cara sederhana dan efisien. Beberapa teknologi selain WebGL yang dapat membangun objek 3D (tiga dimensi), yaitu: Unity 3D, Flash Stage 3D, Silverlight 3D, Direct 3D, OpenGL dan OpenGL ES (Boesch, F. 2013). Kelebihan dari WebGL yaitu WebGL dapat berjalan di banyak browser, seperti: Chrome, Firefox, Safari dan Opera. Selain itu untuk dapat membangun sebuah objek 3D (tiga dimensi) pada WebGL, user tidak perlu menginstal plug-in terlebih dahulu. Teknologi WebGL berawal dari pengembangan OpenGL ES 2.0. Beberapa contoh pengembangan OpenGL antara lain berbasis web, real-time rendering yang memungkinkan pembuatan tiga dimensi (3D) di web, visualisasi scientific dan medical imaging. Pembuatan rendering grafik komputer pada WebGL dapat dibuat dengan hanya menggunakan javascript, web browser, serta HTML5 canvas. WebGL merupakan library grafis yang merupakan standar untuk grafik tiga dimensi (3D) di web browser yang memungkinkan browser untuk membuat adegan tiga dimensi (3D). Elemen yang menyusun bagian dari adegan tiga dimensi (3D) didownload dari server, akan tetapi semua proses untuk mendapatkan gambar dilakukan secara lokal menggunakan hardware grafis client. Beberapa komponen aplikasi WebGL yaitu (Wicaksono, 2012):
Universitas Sumatera Utara
16
- Canvas : tempat komponen objek yang akan diletakkan dan merupakan elemen standar HTML5 yang dapat diakses menggunakan Document Object Model (DOM) melalui JavaScript. - Object : entitas 3D yang membentuk bagian dari adegan itu. - Lights : pencahayaan dalam 3D. - Camera : berfungsi sebagai viewport (untuk melihat dan mengeksplorasi adegan 3D dalam canvas)
Menurut Demeuse, J. (2013), dalam WebGL terdapat : mesh, camera, dan lighting.
WebGl pertama kali diperkenalkan oleh Vladimir Vukicevic seorang software enginner pada tahun 2007, dan pada tahun 2009 WebGL dijadikan standart web yang mulai dikembangkan oleh Khronos Group bersama Opera dan mulai diikuti oleh Google (Chrome), Mozilla (Firefox), Apple (Safari) dan 3D developers lainnya. WebGL memiliki pendekatan client-based rendering dimana unsur – unsur yang membuat bagian dari adegan scene 3D biasanya download dari server, namun semua proses yang diperlukan untuk mendapatkan gambar dilakukan secara local menggunakan hardware grafis klien.
WebGL dirancang untuk web yang dikembangkan dari OpenGL ES 2.0, dirancang sebagai konteks render pada elemen canvas HTML. Gambar 2.3 merupakan gambaran komponen dalam WebGL
Gambar 2.3 Komponen WebGL (Cantor Diego , Jones Brandon, 2012).
Universitas Sumatera Utara
17
2.7.
Google Map
Google Map merupakan peta globe virtual gratis dan online yang disediakan oleh google. Ini merupakan suatu peta yang dapat dilihat dengan menggunakan suatu browser yang akan ditampilkan secara digital. Layanan peta digital gratis tersebut ini hanya menunjukan nama jalan, tidak bias menunjukan nama gunung, sungai, atau yang lainnya. Fungsi Google Maps dapat kita simpulkan untuk membantu seseorang mencari jalan ke lokasi yang ingin dituju, Google Maps juga dilengkapi dengan fasilitas yang menghitung jarak. Sehingga memudahkan kita untuk mengetahui seberaba jauh jalan yang akan dituju.
2.8.
Penelitian Terdahulu
Beberapa penelitian dari peneliti sebelumnya yang menjadi bahan pembelajaran penulis tentang penyelesaian jalur terpendek. Ariani Tyas Sukrisno et al (2010) telah mencoba membangun perancangan Prototye Dynamic Exitc Sign dengan menggunakan algoritma Floyd Warshall Algorithm pada Perancangan Proses Evakuasi Gedung Bertingkat. Ragil Saputra et al (2011) menggunakan algoritma Floyd Warshall untuk merancang Sistem Informasi Geografis Pencarian Rute Optimum Obyek Wisata Kota Yogykarta. Neny Wahyuningdiyah et al (2010) memanfaatkan Metode Ant Colony Optimization Berbasis J2ME untuk melakukan pencarian jarak terpendek pada akses informasi pengiriman barang di Kantor Pos Jemur Sari untuk area Surabaya Timur
Universitas Sumatera Utara
18
Richki Hardi et al (2012) memanfaatkan metode pendekatan Algoritma Graph Travelling Salesman Problem pada sistem tracking antaran paket pada unit pelayanan PT. Pos Indonesia.
Tabel 2.1 Penelitian Terdahulu No
Judul
Pengarang
Tahun
1.
Perancangan Prototye Dynamic Exit Sign dengan mengembangkan Metode Floyd Warshall Algorithm pada Perancangan Proses Evakuasi Gedung Bertingkat
Ariani Tyas Sukrisno, Arief Rahman (Teknik Industri Institut Teknologi Sepuluh November)
2010
2.
Akses Informasi Pengiriman Barang Di Kantor Pos Jemur Sari Untuk Area Surabaya Timur Menggunakan Metode Ant Colony Optimization Berbasis J2ME
Neny Wahyuningdiyah et al
2010
3.
Sistem Informasi Geografis Pencarian Rute Optimum Obyek Wisata Kota Yogyakarta dengan Algoritma Floyd Warshall
Ragil Saputra (Program Studi Teknik Informatika FMIPA Universitas Diponogoro)
2011
4.
Sistem Tracking antaran Paket pada Unit Pelayanan PT. Pos Indonesia Menggunakan metode pendekatan Algoritma Graph Travelling Salesman Problem
Richki Hardi et al
2012
Universitas Sumatera Utara
