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

Kadek Ayu Yanti Pawitri (Prog. Studi Teknik Informatika Fakultas Teknik Universitas Kristen Duta Wacana), Joko Purwadi, M.Kom (Prog. Studi Teknik Informatika Fakultas Teknik Universitas Kristen Duta Wacana)

Abstract


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 PDF