Computer File
Pembangunan geometric t-spanner network menggunakan algoritma path-greedy
Sebuah geometric network merupakan sebuah graf berbobot di mana bobot pada setiap sisi dinyatakan sebagai jarak Euclidean antara dua buah titik. Salah satu karakteristik dari geometric network adalah dilation, yaitu perbandingan antara jarak pada jaringan dengan jarak Euclidean antara dua buah titik. Geometric network yang mempunyai dilation lebih kecil atau sama dengan t disebut juga sebagai t-spanners. Pada penelitian ini, algoritma Path-Greedy digunakan untuk membangun t-spanner pada Rd. Algoritma Path-Greedy sederhana memilih sepasang titik dengan jarak Euclidean terkecil yang belum pernah dipilih, lalu membuat sebuah sisi yang menghubungkan pasangan titik tersebut apabila nilai dilation kedua titik tersebut lebih besar dari nilai t. Pengembangan algoritma Path-Greedy sederhana mengarah pada dua algoritma berikut: Fast Path-Greedy dan RAM Path-Greedy. Ide utama algoritma Fast Path- Greedy adalah dengan membangun sebuah t-spanner awal untuk mengurangi jumlah sisi yang harus diperiksa dan menggunakan sebuah cluster graph untuk mempercepat penghitungan jarak. Sama seperti Fast Path-Greedy, algoritma RAM Path-Greedy juga menggunakan sebuah t-spanner awal dan sebuah cluster graph. Perbedaan pertama
adalah algoritma RAM Path-Greedy menskalakan semua bobot sisi ke dalam bilangan bulat yang cukup kecil untuk mempercepat penghitungan jarak. Kedua penghitungan cluster centers dilakukan berdasarkan cluster centers sebelumnya untuk mempercepat penghitungan cluster graph. Terakhir, untuk mempercepat penghitungan cluster graph,
sebuah algoritma multiple-sources shortest paths yang pada dasarnya menjalankan algoritma Dijkstra’s single source “secara paralel” dapat dijalankan menggunakan cluster centers tersebut sebagai sumber. Pada penelitian ini, semua algoritma diimplementasikan dengan menggunakan bahasa pemrograman C++. Untuk menilai seberapa baik t-spanner yang dihasilkan, terdapat beberapa ukuran kualitas yang dapat digunakan: size, weight, dilation, degree, diameter, connectivity, genus dan load factor. Penelitian ini juga membandingkan algoritma RAM Path-Greedy dengan algoritma lain yang membangun t-spanner berdasarkan pada karakteristik Well-Separated Pair Decomposition. Kesimpulan yang didapat dari penelitian ini adalah sebagai berikut: Pertama, algoritma RAM Path-Greedy yang merupakan
salah satu pengembangan dari algoritma Path-Greedy adalah algoritma terbaik dibandingkan dengan algoritma Path-Greedy lainnya. Kedua, algoritma RAM Path- Greedy dapat memberikan solusi yang lebih realistis untuk diterapkan pada berbagai infrastruktur dibandingkan dengan algoritma Well-Separated Pair Decomposition.
Kata-kata kunci: Geometric Network, Dilasi, t-Spanner, Path-Greedy, Jaringan, Infrastruktur
Barcode | Tipe Koleksi | Nomor Panggil | Lokasi | Status | |
---|---|---|---|---|---|
skp29679 | DIG - FTIS | Skripsi | INFO WID p/15 | Perpustakaan | Tersedia namun tidak untuk dipinjamkan - Missing |
Tidak tersedia versi lain