A* Pathfinding ( Algoritma Pencarian Rute A* ) Part 1

Berhubung PA ambil judul yang ada hubungannya ama A* , gak da salahnya untuk dishare :D...
OK..Sebelumnya apa sich A* ( A Star itu ) ??? :-\

A* (dibaca "A bintang"/"A star") adalah algoritma  pencarian graf/pohon yang mencari jalur dari satu titik awal ke sebuah titik akhir yang telah ditentukan. Algoritma A* menggunakan pendekatan heuristik h(x)  yang memberikan peringkat ke tiap-tiap titik x dengan  cara memperkirakan rute terbaik yang dapat dilalui dari titik tersebut. Setelah itu tiap-tiap titk x tersebut dicek  satu-persatu berdasarkan urutan yang dibuat dengan  pendekatan heuristik tersebut. Maka dari itulah algoritma A* adalah contoh dari best-first search. Algoritma ini pertama kali ditemukan pada tahun 1968 oleh Peter Hart, Nils Nilsson dan Bertram Raphael. Dalam tulisan mereka, algoritma ini dinamakan algoritma A. Penggunaan algoritma ini dengan fungsi heuristik yang tepat dapat memberikan hasil yang optimal, maka algoritma inipun disebut A*. Beberapa terminologi dasar yang terdapat pada algoritma ini adalah starting point, simpul (nodes), A, open list, closed list, harga (cost), halangan (unwalkable).

• Starting point adalah sebuah terminologi posisi awal sebuah benda.
• A adalah simpul yang sedang dijalankan algortima pencarian jalan terpendek.
•  Simpul adalah petak-petak kecil sebagai representasi  dari areapathfinding. Bentuknya dapat berupa persegi, lingkaran, maupun segitiga.
• open list adalah tempat menyimpan data simpul yang mungkin diakses dari starting point maupun simpul yang sedang dijalankan.
• Closed list adalah tempat menyimpan data simpul sebelum A yang juga merupakan bagian dari jalur terpendek yang telah berhasil didapatkan.
• Harga (F) adalah nilai yang diperoleh dari penjumlahan nilai G, jumlah nilai tiap simpul dalam jalur terpendek dari starting point ke A, dan H, jumlah nilai perkiraan dari sebuah simpul ke simpul tujuan.
• Simpul tujuan yaitu simpul yang dituju.
• Rintangan adalah sebuah atribut yang menyatakan bahwa sebuah simpul tidak dapat dilalui oleh A.

Prinsip algoritma ini adalah mencari jalur terpendek dari sebuah simpul awal (starting point) menuju simpul tujuan dengan memperhatikan harga (F) terkecil.
A* memperhitungkan cost dari current state ke tujuan denga fungsi heuristic, Algoritma ini juga mempertimbangkan cost yang telah ditempuh selama ini dari initial state ke current state. Jadi jika ada jalan yang telah ditempuh sudah terlalu panjang dan ada jalan lain yang cost-nya lebih kecil tetapi memberikan posisi yang sama dilihat dari goal, jalan yang lebih pendek yang akan dipilih.[8]
Algoritma  A* dapat dijelaskan dengan pseudocode dibawah ini :

1. Masukan node awal ke openlist
2. Loop Langkah – langkah di bawah ini :
    a. Cari node (n) dengan nilai f(n) yang paling rendah dalam open list. Node ini sekarang menjadi current  node.
    b. Keluarkan current node dari openlist dan masukan ke close list
    c. Untuk setiap tetangga dari current node lakukan berikut :
        •  Jika tidak dapat dilalui atau sudah ada dalam close list, abaikan.
        •  Jika belum ada di open list . Buat current node parent dari node tetangga ini. Simpan nilai f,g dan h dari node ini.
        •  Jika sudah ada di open list, cek bila node tetangga ini lebih baik, menggunakan nilai g sebagai ukuran. Jika lebih baik ganti parent dari node ini di openlist menjadi current node, lalu kalkulasi ulang nilai g dan f dari node ini.
    d. Hentikan loop jika :
        • Node tujuan telah ditambahkan ke openlist, yang berate rute telah ditemukan.
        • Belum menemukan node goal sementara open list kosong atau berarti tidak ada rute.
3. Simpan rute. Secara ‘backward’, urut mulai darinode goal ke parent-nya terus sampai mencapai node awal sambil menyimpan node ke dalam sebuah array.

Bersambung ke Part 2