Pseudocode Algoritma A * ( A Star Algorithm )

Algoritma A* (A Star Algorithm) - uptechno kali ini akan sedikit menshare mengenai pseudocode dari Algoritma A*. sedikit saja mengenai Algoritma A* adalah salahsatu algoritma yang biasa digunakan untuk menentukan pencarian rute terpendek atau biasa di sebut patchfinding. Tapi jangan terbatasi oleh sesuatu yang biasa digunakan untuk hal itu, manfaatkanlah atau kembangkanlah ilmu yang sudah ada agar menjadi lebih baik. untuk keterangan lebih lanjut mengenai algoritma A* teman – teman bisa mencarinya di google, karena algoritma ini sudah banyak contohnya dan banyak yang memakainya jadi tidak sulit jika ingin mencarinya.

Ok kita lanjutkan ke inti awalnya yaitu untuk pseseudocodenya , bisa anda lihat pada gambar di bawah ini.

Pseudocode Algoritma A*

Jika gambar di atas kurang jelas mungkin sedikit tulisan di bawah ini bisa menjelaskannya maksut dari pseudocode di atas.

Algoritma A*

Function A* (masalah) returns solusi

OPEN ßS

CLOSED ß array kosong

Loop sampai goal detemukan atau sampai tidak ada simpul didalam OPEN

If OPEN = kosong then

Gagal

Else

            BestNode = simpul yang ada di OPEN dengan f minimal

            Pindahkan simpul terbaik tersebut dari OPEN ke CLOSED

If BestNode = goal then

                        Sukses

Else

Bangkitkan semua suksesor BestNode tapi jangan buat pointer

Untuk setiap suksesor kerjakan:

Hitung g(suksesor) = g(BestNode) + actual cost(dari BestNode ke suksesor)

{periksa suksesor}

If suksesor ada di OPEN then {sudah pernah dibangkitkan tapi belum diproses}

OLD = simpul di OPEN yang sama dengan suksesor tersebut

Tambahkan OLD sebagai suksesor BestNode

Buat pointer dari OLD ke BestNode

Bandingkan nilai g(OLD) dengan suksesor g(suksesor)

If g(OLD) lebih baik then

Ubah parent OLD ke BestNode

Ubah nilai g dan f yang ada pada OLD

End

else

If suksesor ada di CLOSED then {sudah pernah dibangkitkan dan sudah diproses}

OLD = simpul di CLOSED yang sama dengan suksesor tersebut Tambahkan OLD sebagai suksesor BestNode

Bandingkan nilai g(OLD) dengan g(suksesor)

If g(OLD) lebih baik then Ubah parent OLD ke BestNode Ubah nilai g dan f yang ada pada OLD Propagasi untuk semua suksesor OLD dengan penelusuran DFS dengan aturan. loop sampai simpul suksesor tidak ada di OPEN atau simpul tidak punya suksesor If suksesor ada di OPEN then Propagasi diteruskan else If nilai g via suksesor lebih baik then Propagasi diteruskan else Propagasi dihentikan end end end else {suksesor tidak ada di OPEN maupun CLOSED} Masukan suksesor ke OPEN Tambahkan suksesor tersebut sebagai suksesornya BestNode Hitung f = g(suksesor) + h(suksesor) end end end end

Sekian yang bisa saya bagikan kali ini , jika ada kesalahan dalam penulisan dan materi yang ada mohon kiranya di koreksi, karena masih dalam tahap belajar menulis. Terimakasih.