Pengertian Algoritma A*
Algoritma A* adalah algoritma yang dikemukakan oleh Hart, Nilsson, dan Raphael pada tahun 1968. Algoritma A* merupakan salah satu algoritma Branch & Bound atau disebut juga sebagai sebuah algoritma untuk melakukan pencarian solusi dengan menggunakan informasi tambahan (heuristik) dalam menghasikan solusi yang optimal.
Penggunaan Fungsi Heuristik
Pada algoritma A*, untuk mempercepat pencarian simpul solusi, maka setiap simpul diberi sebuah nilai ongkos (cost). Dimana, simpul berikutnya yang akan diekspansi tidak lagi berdasarkan urutan pembangkitan (seperti BFS), tetapi simpul yang memiliki ongkos paling kecil (least cost search).
Nilai ongkos pada setiap simpul n menyatakan taksiran ongkos termurah lintasan dari simpul n ke simpul solusi (goal node), yaitu:
F (n) = nilai taksiran lintasan termurah dari simpul status n ke status tujuan
Dengan kata lain, F (n) menyatakan batas bawah (lower bound) dari ongkos pencarian solusi dari status n. Fungsi heuristik yang terdapat pada algoritma A* untuk menghitung taksiran nilai dari suatu simpul dengan simpul yang telah dilalui adalah:
F (n) = g (n) + h (n)
Dimana :
F (n) = ongkos untuk simpul n
g (n) = ongkos mencapai simpul n dari akar
h (n) = ongkos mencapai simpul tujuan dari simpul n
1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar adalah simpul solusi (goal node), maka solusi telah ditemukan. Stop.
2. Jika Q kosong, tidak ada solusi. Stop
3. Jika Q tidak kosong, pilih dari antrian Q simpul n yang mempunyai F (n) paling kecil. Jika terdapat beberapa simpul n yang memenuhi, pilih satu secara sembarang.
4. Jika simpul n adalah simpul solusi, berarti solusi sudah ditemukan, stop. Jika simpul n bukan simpul solusi, maka bangkitkan semua anakanaknya. Jika n tidak mempunyai anak, kembali ke langkah 2.
5. Untuk setiap anak j dari simpul n, hitung F (n), dan masukkan semua anak-anak tersebut ke dalam antrian Q.
6. Kembali ke langkah 2
Algoritma A* adalah algoritma yang dikemukakan oleh Hart, Nilsson, dan Raphael pada tahun 1968. Algoritma A* merupakan salah satu algoritma Branch & Bound atau disebut juga sebagai sebuah algoritma untuk melakukan pencarian solusi dengan menggunakan informasi tambahan (heuristik) dalam menghasikan solusi yang optimal.
Penggunaan Fungsi Heuristik
Pada algoritma A*, untuk mempercepat pencarian simpul solusi, maka setiap simpul diberi sebuah nilai ongkos (cost). Dimana, simpul berikutnya yang akan diekspansi tidak lagi berdasarkan urutan pembangkitan (seperti BFS), tetapi simpul yang memiliki ongkos paling kecil (least cost search).
Nilai ongkos pada setiap simpul n menyatakan taksiran ongkos termurah lintasan dari simpul n ke simpul solusi (goal node), yaitu:
F (n) = nilai taksiran lintasan termurah dari simpul status n ke status tujuan
Dengan kata lain, F (n) menyatakan batas bawah (lower bound) dari ongkos pencarian solusi dari status n. Fungsi heuristik yang terdapat pada algoritma A* untuk menghitung taksiran nilai dari suatu simpul dengan simpul yang telah dilalui adalah:
F (n) = g (n) + h (n)
Dimana :
F (n) = ongkos untuk simpul n
g (n) = ongkos mencapai simpul n dari akar
h (n) = ongkos mencapai simpul tujuan dari simpul n
1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar adalah simpul solusi (goal node), maka solusi telah ditemukan. Stop.
2. Jika Q kosong, tidak ada solusi. Stop
3. Jika Q tidak kosong, pilih dari antrian Q simpul n yang mempunyai F (n) paling kecil. Jika terdapat beberapa simpul n yang memenuhi, pilih satu secara sembarang.
4. Jika simpul n adalah simpul solusi, berarti solusi sudah ditemukan, stop. Jika simpul n bukan simpul solusi, maka bangkitkan semua anakanaknya. Jika n tidak mempunyai anak, kembali ke langkah 2.
5. Untuk setiap anak j dari simpul n, hitung F (n), dan masukkan semua anak-anak tersebut ke dalam antrian Q.
6. Kembali ke langkah 2
Tidak ada komentar:
Posting Komentar