Google Scholar

IMPLEMENTASI ALGORITMA PHYSICAL-A* (PHA*) UNTUK MENEMUKAN LINTASAN TERPENDEK
23 Juni 2009

Kadek Ayu Yanti Pawitri , Joko Purwadi, M.Kom 
Program Studi Teknik Informatika Fakultas Teknik
Universitas Kristen Duta Wacana Yogyakarta 2007

Abstrak
Artikel ini membahas tentang implementasi algoritma Physical-A* (PHA*) untuk menemukan lintasan terpendek. Lintasan terpendek (shortest path) adalah lintasan minimum yang diperlukan untuk mencapai suatu titik dari titik tertentu. Pencarian lintasan terpendek (shortest path problem), pada dasarnya adalah penyelesaian masalah untuk menentukan lintasan mana yang akan dilalui sehingga ditemukan lintasan terpendek dari titik awal ke tujuan.
 Permasalahan ini direpresentasikan dalam bentuk graf berbobot dimana setiap verteks digambarkan dengan koordinat 2 dimensi, dan bobot edgenya adalah jarak eucladian diantara dua verteks yang bersesuaian. Seorang mobile agent akan berpindah dari satu verteks ke verteks lainnya untuk menemukan lintasan terpendek dari keadaan awal ke tujuan.
Algoritma PHA* merupakan pengembangan dari algoritma A* dengan memodifikasi fungsi heuristiknya. Algoritma ini ditampilkan sebagai algoritma dua tingkat (two level algorithm) yaitu level atas (high-level) dan level bawah (low-level). Level atas akan memilih verteks yang akan diekspansi dan level bawahnya akan mengarahkan agent menuju verteks tersebut dengan tujuan mengeksplorasinya.


Kata Kunci : graf, algoritma physical A* (PHA*), lintasan terpendek.

 

Download >> IMPLEMENTASI ALGORITMA PHYSICAL-A* (PHA*) UNTUK MENEMUKAN LINTASAN TERPENDEK.pdf