Algoritma A*

Algoritma pencarian A* atau disebut juga A-star search, merupakan format best-fist search yang banyak diketahui. A* search mengevaluasi tiap node dengan cara mengkombinasikan g(n) dan h(n), dimana g(n) merupakanCost yang dicapai sampai di n, dan h(n) adalah Estimasi cost untuk sampai pd goal dari n. Evaluation function dari A* search bisa dituliskan sebagai berikut :

f(n) = g(n) + h(n)

dimana f(n) merupakan Estimasi total cost dari path n sampai goal.

Apabila kita ingin menemukan solusi termurah, suatu hal layak untuk dicoba pertama kali adalah node dengan nilai g(n) yang paling rendah + h(n). Hal ini menunjukkan bahwa strategi ini lebih dari sekedar layak : dengan ketentuan bahwa heuristik function h(n) pada kondisi tertentu telah sesuai, maka A* search optimal dan lengkap.

Optimalitas dari A* search adalah bisa dianalisis secara langsung jika menggunakan Tree-Search. Dalam hal ini, A* search adalah optimal jika h(n) adalah sebuah admissible heuristic, dengan ketentuan bahwa h(n) tidak meng-overestimate cost untuk mencapai goal.

Fungsi Heuristic h(n) dikatakan konsisten jika setiap node n dan setiap successor n’ dari n yang digenerate action a, maka estimasi cost dari n sampai ke goal tidak lebih besar dari cost sampai step n’ + estimasi cost n’ ke goal

h(n) <= c(n,a,n’) + h(n’)

Jika h(n) konsisten, maka nilai dari f(n) melalui suatu path tidak berkurang/nondecreasing.

f(n’) = g(n’)+h(n’)

       = g(n) + c(n,a,n’) + h(n’)

       >= g(n) + h(n)

       = f(n)

Pencarian jalur atau istilah kerennya adalah pathfinding dalam deskripsi saya adalah proses pencarian rute/jalur (biasanya rute terdekat) dari suatu arena yang pada umumnya memiliki penghalang-penghalang dari arena tersebut. Adapun penghalang dapat berupa tembok, sungai, dsb. Goal dari pathfinding ini pada umumnya adalah untuk mencari jalur paling efisien dengan sebisa mungkin menghindari penghalang yang ada.

Pathfinding dapat diterapkan misalnya dalam membuat AI dari suatu game, misalnya agar AI tersebut dapat mengejar musuh secara efisien dan tanpa menabrak tembok atau menghindari penghalang lain. Terdapat beberapa metode yang dapat diterapkan dalam pathfinding ini, salah satu metode yang sering digunakan adalah A*. Ok, tanpa berbelit-belit langsung saja kita berkenalan dengan metode yang satu ini.

Langkah 1 : Arena
Berikut adalah contoh simple arena yang akan kita gunakan. Warna hijau adalah starting point, warna merah adalah goal/end point, dan biru adalah penghalang. Goal dari aplikasi ini adalah mencari rute dari titik hijau ke merah tanpa melewati penghalang biru

Langkah 2 : Movement Cost / Biaya Pergerakan
Kita asumsikan setiap langkah dari hijau adalah legal baik vertikal, horizontal, maupun diagonal dengan catatan tidak membentur tembok. Setiap langkah yang diizinkan kita berikan nilai G dimana G adalah cost atau biaya dalam setiap langkah. Dalam kasus ini kita akan berikan nilai 10 untuk setiap langkah vertikal maupun horizontal, dan 14 untuk diagonal. Nilai 14 kita dapatkan dari perhitungan pitagoras dimana 14,1421 = sqrt(sqr(10)+sqr(10)). Hasil data nilai G ini selanjutnya kita gambarkan sbb :

Selain dari perhitungan tersebut, kita dapat mengalikan dengan konstanta tertentu untuk memanipulasi biaya, misal : ketika melewati sungai maka G = G * 2. 

Langkah 3 : Estimated Movement / Estimasi gerakan
Langkah selanjutnya kita hitung biaya estimasi pergerakan dan kita simbolkan dengan H. Nilai H ini secara singkat adalah nilai jarak / estimasi biaya dari pergerakan dari suatu titik terhadap titik finish dengan mengabaikan penghalang yang ada. Untuk lebih jelasnya silahkan lihat gambar di bawah :

Langkah 4 : Scoring / Penilaian
Setelah nilai G dan H kita dapatkan, maka kita berikan skor dari masing-masing titik yang akan dilalui. Skor kita lambangkan misalnya dengan F dimana nilai F = G + H. Nilai F selanjutnya kita masukkan dalam setiap titik dari setiap langkah yang akan dilalui. Untuk lebih jelasnya lihat gambar di bawah :

Dari setiap nilai tersebut kita ambil keputusan dengan mengambil langkah dengan nilai F terkecil.

Langkah 5 : Looping / Perulangan
Setelah pergerakan pertama selesai selanjutnya lakukan perulangan dari dari langkah 1 sampai 4. Untuk lebih jelasnya setiap pergerakan akan digambarkan di bawah :

Pseudocode

function A*(start,goal)

    closedset := the empty set    // The set of nodes already evaluated.

    openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node

    came_from := the empty map    // The map of navigated nodes.

    g_score[start] := 0    // Cost from start along best known path.

    // Estimated total cost from start to goal through y.

    f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

    while openset is not empty

        current := the node in openset having the lowest f_score[] value

        if current = goal

            return reconstruct_path(came_from, goal)

        remove current from openset

        add current to closedset

        for each neighbor in neighbor_nodes(current)

            if neighbor in closedset

                continue

            tentative_g_score := g_score[current] + dist_between(current,neighbor)

            if neighbor not in openset or tentative_g_score < g_score[neighbor]

                came_from[neighbor] := current

                g_score[neighbor] := tentative_g_score

                f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)

                if neighbor not in openset

                    add neighbor to openset

    return failure

function reconstruct_path(came_from, current_node)

    if current_node in came_from

        p := reconstruct_path(came_from, came_from[current_node])

        return (p + current_node)

    else

        return current_node