Pencarian Jarak Terpendek Dengan Algoritma A*


~ Happy chinese new year ~ Malam ini penuh dengan semarak kembang api yang tidak berhenti dari tadi.  Maklum saja, beberapa menit lagi, tahun Kelinci akan berganti menjadi tahun Naga.  Sembari menikmati dentuman kembang api, saya menyempatkan diri untuk menulis mencurahkan isi hati.  Topik yang saya pilih kali ini adalah mengenai algoritma.  Banyak sekali software engineer yang terbiasa mengimplementasikan business logic, tapi tidak berkutik bila dihadapi dengan ‘soal-soal algoritma’ (termasuk saya!).  Yang saya maksud ‘soal-soal algoritma’ disini adalah persoalan dimana si programmer harus mencari jarak terpendek dari satu node ke node lainnya.

Sebagai contoh, saya mengambil gambar-gambar dari scenario Wombat dan ingin menghasilkan program seperti berikut ini:

Tampilan Hasil Akhir Program

Tampilan Hasil Akhir Program

Pada program tersebut, terdapat sebuah binatang Wombat, sebuah daun, dan batu-batu sebagai penghalang.  Wombat dapat berpindah-pindah dari satu kotak ke kotak lainnya, asalkan tidak dihalangi oleh batu.  Pertanyaannya adalah bagaimana supaya Wombat dapat mencari jalan untuk menuju ke daun dengan melewati jumlah kotak seminimal mungkin (mencari jarak terpendek)???

Salah satu cara untuk menyelesaikannya adalah dengan menggunakan algoritma A* (baca: A star).  Pada algoritma ini, setiap kotak yang mungkin akan dilalui oleh Wombat harus dihitung nilai cost-nya.  Nilai cost tersebut umumnya disebut fungsi f(x).  Nilai f(x) merupakan penjumlahan dari fungsi g(x) dan fungsi h(x).  Secara matematika ditulis f(x) = g(x) + h(x).

Nilai fungsi g(x) adalah nilai cost dari node awal hingga ke node yang saat ini akan dihitung cost-nya.

Nilai fungsi h(x) adalah sebuah nilai heuristic (sebuah perkiraan) yang menerka cost yang dibutuhkan untuk mencapai node tujuan mulai dari node yang saat ini akan dihitung cost-nya.

Saya akan membuat sebuah program Java sederhana, dengan class diagram seperti berikut ini:

UML Class Diagram

UML Class Diagram

Implementasi algoritma A* dapat dilihat pada class Algoritma.  Project NetBeans yang berisi implementasi kode program yang ada dapat di-download di sini.  Source code pada project tersebut sudah diberi dokumentasi sehingga dapat dipelajari dengan mudah.  Saya membuat kode program dengan menggunakan NetBeans 7.1.  Selain itu, agar program dapat di-compile, gunakan minimal Java 7, karena saya menggunakan diamond operator yang hanya ada sejak Java 7.  Untuk men-download JAR program tanpa perlu men-download source, silahkan klik di sini.

Jam 00.00 telah berlalu.  Dentuman kembang api pun mereda.  Dan sungguh kebetulan, hujan ikut turun membahasi bumi.  Malam pun kembali sepi dan dingin..

Perihal Solid Snake
I'm nothing...

5 Responses to Pencarian Jarak Terpendek Dengan Algoritma A*

  1. afrizalbotong mengatakan:

    bisa mnta file source code pojects nya nggak???
    buat kperluan tgas nih….

  2. afrizalbotong mengatakan:

    thx masbro…pasti bermanfaat

  3. andra mengatakan:

    terimakasih..mohon izin utk sya download dan pelajari,kbetulan sdg mmpelajari SMA* nya

  4. Thanks ya..kebetulan rencana saya ingin mengembangkan algoritma a* ini untuk skripsi..

Apa komentar Anda?

Please log in using one of these methods to post your comment:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: