Algoritma ini pertama kali diperkenalkan pada 1968 oleh Peter Hart, Nils Nilsson, dan Bertram Raphael. Dalam ilmu komputer, A* (yang disebut dengan “A star”) merupakan salah satu algoritma pencarian graph terbaik yang mampu menemukan jalur dengan biaya pengeluaran paling sedikit dari titik awal yang diberikan sampai ke titik tujuan yang diharapkan (dari satu atau lebih tujuan).
Algoritma A* (Admissible Heuristic) adalah strategi best first search yang menggunakan estimasi solusi biaya terkecil untuk mencapai suatu tujuan dengan jarak tempuh terdekat dan memiliki nilai heuristik yang digunakan sebagai dasar pertimbangan. Heuristik adalah kriteria, metode, atau prinsip-prinsip untuk menentukan pilihan sejumlah alternatif untuk mencapai sasaran dengan efektif.
Nilai heuristik dipergunakan untuk mempersempit ruang pencarian. Metode pencarian A* menghasilkan jalur optimal mulai dari tempat awal kemudian melalui graph menuju tempat yang dituju. Metode ini berdasarkan formula :
f(n) = g(n)+h(n)
Keterangan :
h(n) = biaya estimasi dari node n ke tujuan
g(n) = baya path atau perjalanan
f(n) = solusi biaya estimasi termurah node n untuk mencapai tujuan.
Gambar. Metode A*
langkah perhitungan Metode A*
Algoritma A* secara garis besar dapat dijelaskan seperti berikut:
1. Masukkan node awal ke openlist
2. Loop langkah-langkah dibawah ini:
a. Cari node (n) dengan nilai f(n) yang paling kecil dalam open list, dan node ini sekarang menjadi current node.
b. Keluarkan current node dari openlist dan masukkan ke open list
c. Untuk setiap tetangga dari current node lakukan berikut
1. Jika tidak dapat dilalui atau sudah ada dalam close list , abaikan
2. Jika belum ada di open list buat current node parent dari node tetangga ini, simpan nilai f,g, dan h dari node ini.
3. Jika sudah ada di openlist cek apabila node tetangga ini lebih baik menggunakan nilai g sebagai ukuran. Jika lebih baik ganti parent dari node ini di opentlist menjadi current node, lalu kalkulasikan ulang nilai g dan f dari node ini.
d. Hentikan looping jika:
1. Node tujuan telah ditambah ke openlist yang berarti rute ditemukan
2. Belum menemukan node akhir (tujuan) sementara openlist kosong atau berarti tidak ada rute.
Simpan rute, lalu secara backward urut mulai dari node akhir (tujuan) sampai ke titik awal sambil menyimpan node ke dalam array.
berikut ini contoh perhitungan metode A* menurut Yulani, dan Fahrul Agus:
Gambar. peta contoh perhitungan
Keterangan :
Length = Panjang jarak antara titik awal dan titik akhir
Titik Awal = Dinas Kesehatan
Titik Akhir = Dinas Kebersihan, Pertamanan, dan Pemadam Kebakaran
Cara perhitungan yang dipakai dalam pencarian rute :
F(n) = g(n) + h(n)
Keterangan :
F(n) = Jumlah dari g(n) + h(n), perkiraan jalur terpendek sementara
g(n) = Total jarak yang di dapat dari vertex awal ke vertex akhir
h(n) = Perkiraan jarak dari vertex sekarang yang sedang dikunjungi ke vertex tujuan
1. Jarak 2 node :
N[1][2] = (√ ( (X2 – X1)2 + (Y2-Y1)2 ) )
Langkah 1 :
N[0][123]
g = N[0][123] = 25
N[123][122] :
g = N[123][122] = N[0][123] + N[123][122] = 25 + 79 = 104
h = N[122][86] = (√ ( (117 – 89)2+ (119 – 90)2) ) = 40
f = g + h = 144
Karena hanya ada 1 koneksi maka dipilih N[123][122]
Langkah 2 :
N[122][121] :
g = N[0][123] + N[123][122] + N[122][121] = 25 + 79 + 195 = 299
h = N[121][86] = 39
f = g + h = 338
N[122][116] :
g = N[0][123] + N[123][122] + N[122][116] = 25 + 79 + 136 = 240
h = N[116][86] = 38
f = g + h = 278
Dipilih N[122][116]
Langkah 3 :
N[122][121] : g = 299, h = 39, f = 338
N[116][118] :
g = N[0][123] + N[123][122] + N[122][116] + [116][118] = 25 + 79 + 136 + 942 = 1182
h = N[118][86] = 25
f = g + h = 1233
Dipilh N[122][121]
Langkah 4 :
N[116][118] : g = 1182, h = 25 ,f = 1233
N[121][3] :
g = N[0][123] + N[123][122] + N[122][121] + [121][3] = 25 + 79 + 195 + 508 = 806
h = N[3][86] = 36
f = g + h = 842
N[121][1] :
g = N[0][123] + N[123][122] + N[122][121] + [121][1] = 25 + 79 + 195 + 950 = 1249
h = N[1][86] = 26
f = g + h = 1305
Dipilih N [121][3]
Langkah 5 :
N[116][118] : g = 1182, h = 25 ,f = 1233
N[121][1] : g = 1249, h = 26 ,f = 1305
N[3][67] :
g = N[0][123] + N[123][122] + N[122][121] + [121][3] + [3][67] = 25 + 79 + 195 + 508 + 168 = 975
h = N[67][86] = 26
f = g + h = 1001
Dipilih N [3][67]
Langkah 6 :
N[116][118] : g = 1182, h = 25 ,f = 1233
N[121][1] : g = 1249, h = 26 ,f = 1305
N[67][70] :
g = N[0][123] + N[123][122] + N[122][121] + [121][3] + [3][67] + [67][70] = 25 + 79 + 195 + 508 + 168 + 90 = 1065
h = N[70][86] = 16
f = g + h = 1081
Dipilih N [67][70]
Langkah 7 :
N[116][118] : g = 1182, h = 25 ,f = 1233
N[121][1] : g = 1249, h = 26 ,f = 1305
N[70][69] :
g = N[0][123] + N[123][122] + N[122][121] + [121][3] + [3][67] + [67][70] + [70][69] = 25 + 79 + 195 + 508 + 168 + 90 + 62 = 1127
h = N[69][86] = 5
f = g + h = 1132
Dipilih N [70][69]
Langkah 8 :
N[116][118] : g = 1182, h = 25 ,f = 1233
N[121][1] : g = 1249, h = 26 ,f = 1305
N[69][1] :
g = N[0][123] + N[123][122] + N[122][121] + [121][3] + [3][67] + [67][70] + [70][69] + [69][1] = 25 + 79 + 195 + 508 + 168 + 90 + 62 + 546 = 1673
h = N[1][86] = 26
f = g + h = 1699
Dipilih N [116][118]
Langkah 9 :
N[121][1] : g = 1249, h = 26 ,f = 1305
N[69][1] : g = 1673, h = 26, f = 1699
N[118][119] :
g = N[0][123] + N[123][122] + N[122][116] + N[116][118] + N[118][119] = 25 + 79 + 136 + 942 + 117 = 1299
h = N[119][86] = 4
f = g + h = 1303
Dipilih N [118][119]
Langkah 10 :
N[121][1] : g = 1249, h = 26 ,f = 1305
N[69][1] : g = 1673, h = 26, f = 1699
N[119][1] :
g = N[0][123] + N[123][122] + N[122][116] + N[116][118] + N[118][119] + [119][1] = 25 + 79 + 136 + 942 + 117 + 198 = 1497
h = N[1][86] = 26
f = g + h = 1523
Dipilih N [121][1]
Langkah 11 :
N[69][1] : g = 1673, h = 26, f = 1699
N[119][1] : g = 1497, h = 26, f = 1523
N[1][86] :
g = N[0][123] + N[123][122] + N[122][121] + N[121][1] + [1][86] = 25 + 79 + 195 + 950 + 493 = 1742
h = N[86][86] = 0
f = g + h = 1742
Dipilih N[1][86].
Pencarian rute terpendek berhenti karena sudah sampai node tujuan. Rute yang didapat adalah : 0–123–122–121–1–86 yaitu Titik awal>DK[123] > Jln.Jend Ahmad yani[122] > Jln.Jend Ahmad Yani[121] > Jln.Jend DI Panjaitan[1] > Jln.Kapt Piere Tendean[86].
Dibawah ini akan diperlihatkan tampilan keluaran dari sistem ketika dilakukan pencarian dengan titik awal dan titik akhir yang sama.
Gambar. Hasil perhitungan A*
itulah sedikit penjelasan dari metode A*, semoga dapat membantu.
untuk pembahasan pengukuran jarak suatu tempat dengan GIS penulis jadikan empat bagian, karena pembahasannya yang panjang. jadi agar lebih efisien penulis pecah menjadi empat pembahasan.
sumber:
Yuliani, Agus, Fahrul. (2013), Webgis Pencarian Rute Terpendek Menggunakan Algoritm A Star (A*)
Tidak ada komentar:
Posting Komentar