Algoritma A* (A-Star) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur optimal dengan poin tertinggi.
Diasumsikan ada sebaran titik titik tidak beraturan dalam sebuah grafik
Tidak semua titik terhubung satu sama lain, melainkan hanya melalui jalur-jalur tertentu saja
Dan setiap jalur memiliki poin sendiri-sendiri
Tentukan Jalur optimal yang harus diambil dari titik awal ke titik tujuan dengan poin maksimal
Dalam kasus ini, diasumsikan hanya ada 6×6 = 36 titik, dengan jalur sbb
-1 = tidak memiliki jalur, 0 = ada jalur, dan 100 = ada jalur dan mendapat poin
| -1 | -1 | -1 | -1 | 0 | -1 |
| -1 | -1 | -1 | 0 | -1 | 100 |
| -1 | -1 | -1 | 0 | -1 | -1 |
| -1 | 0 | 0 | -1 | 100 | -1 |
| 0 | -1 | -1 | 0 | -1 | 100 |
| -1 | 100 | -1 | -1 | 100 | 100 |
Index setiap baris dan kolom dimulai dari angka 0, sehingga ada baris 0 sampai 5 dan kolom 0 sampai 5
Contoh1: matriks(1,3) = 0 -> ada jalur dari titik 1 ke titik 3 dengan poin 0
Contoh2: matriks(4,0) = 0 -> ada jalur dari titik 4 ke titik 0 dengan poin 0
Contoh3: matriks(2,0) = -1 -> tidak ada jalur dari titik 2 ke titik 0
Contoh4: matriks(2,5) = 100 -> ada jalur dari titik 2 ke titik 5 dengan point 100
Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan Poin Hadiah (sesuai dengan tabel diatas)
-1 = tidak memiliki jalur, 0 = ada jalur, dan 100 = ada jalur dan mendapat poin.
Private Poin As Integer(,) = New Integer(,) {{-1, -1, -1, -1, 0, -1}, _
{-1, -1, -1, 0, -1, 100}, _
{-1, -1, -1, 0, -1, -1}, _
{-1, 0, 0, -1, 100, -1}, _
{0, -1, -1, 0, -1, 100}, _
{-1, 100, -1, -1, 100, 100}}
* Tentukan ukuran Matriks A*
Diasumsikan dalam kasus ini, ukuran matriks adalah 6
Private Const UkuranMatriks As Integer = 6
* Tentukan Titik Tujuan / Titik Akhir dalam perhitungan
Diasumsikan titik tujuan akhir adalah titik 5
Const Tujuan As Integer = 5
* Tentukan urutan prioritas State Awal
Jadi perhitungan titik Matriks tidak dilakukan secara urut (0,1,2,3,4,5) tetapi mengikuti urutan state
Diasumsikan dalam kasus ini, urutan prioritas state yang dihitung adalah state 1, 3, 5, 2, 4, 0
Dim UrutanStateAwal As Integer() = New Integer() {1, 3, 5, 2, 4, 0}
Langkah-langkah penggunaan algoritma ini adalah
1. Lakukan perhitungan pada semua state sesuai dengan urutan state yang sudah ditentukan (poin 1a)
For i As Integer = 0 To UkuranMatriks - 1 Dim StateSekarang As Integer = UrutanStateAwal(i) . . .
1a. Untuk masing-masing state terpilih,
Lakukan perhitungan selama state sekarang tidak sama dengan state tujuan (poin 1a1 – 1a3)
Do While StateSekarang <> TitikTujuan . . .
1a1. Inisialisasi matriks G dan H yang digunakan untuk menghitung fungsi G dan H pada masing-masing titik
Beri nilai awal fungsi dengan angka -1
Dim G(UkuranMatriks - 1) As Double Dim H(UkuranMatriks - 1) As Double For j As Integer = 0 To UkuranMatriks - 1 G(j) = -1 H(j) = -1 Next j
1a2. Lakukan perhitungan pada semua state selain state yang sedang terpilih
Lakukan perhitungan berikutnya apabila state ini bukan state awal atau merupakan state tujuan (poin 1a2a – 1a2c)
For j As Integer = 0 To UkuranMatriks - 1 If StateSekarang <> UrutanStateAwal(j) Or StateSekarang = TitikTujuan Then . . .
1a2a. Hitung nilai fungsi G
G adalah poin untuk setiap state tujuan yang terhubung
G(UrutanStateAwal(j)) = Poin(StateSekarang, UrutanStateAwal(j))
1a2b. Hitung nilai fungsi H
H adalah estimasi poin yang diperoleh untuk sampai langsung ke state terakhir
If Poin(StateSekarang, TitikTujuan) > 0 Then H(UrutanStateAwal(j)) = Poin(TitikTujuan, UrutanStateAwal(j)) End If
1a2c. Hitung nilai fungsi F
nilai fungsi F dihitung dengan rumus nilai fungsi G + nilai fungsi H
Cari nilai F yang terbesar, dan catat state tersebut sebagai state tujuan
If maks < G(UrutanStateAwal(j)) + H(UrutanStateAwal(j)) Then maks = G(UrutanStateAwal(j)) + H(UrutanStateAwal(j)) StateTujuan = UrutanStateAwal(j) ElseIf maks = G(UrutanStateAwal(j)) + H(UrutanStateAwal(j)) And UrutanStateAwal(j) = TitikTujuan Then maks = G(UrutanStateAwal(j)) + H(UrutanStateAwal(j)) StateTujuan = UrutanStateAwal(j) End If
1a3. Catat State tujuan yang terpilih sebagai state awal untuk perhitungan berikutnya
dan jumlahkan total poin yang sudah didapatkan pada perhitungan diatas
StateSekarang = StateTujuan Jalur += ", " & StateTujuan totalPoin += maks
Hasil akhir adalah: (klik untuk perbesar gambar)
Untuk Titik Tujuan 5:
Untuk Titik Tujuan 1:
Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:
Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.