Pengertian dan Penerapan Metode Best First Search

Salah satu algoritma yang digunakan dalam artificial intelligence, atau yang kita kenal juga dengan kecerdasan buatan adalah best first search. Best first search adalah algoritma yang mengeksplorasi sebuah grafik dengan cara memperluas node atau simpul yang paling menjanjikan yang dipilih sesuai dengan aturan yang ditentukan. Simpul merupakan gambaran dari area pencarian. Adapun grafik yang digunakan dalam best first search disebut grafik OR karena setiap cabangnya merepresentasikan jalan alternatif untuk penyelesaian masalah. Best first search bisa dibilang juga seperti mengembangkan simpul dari simpul sebelumnya. Simpul yang dikembangkan adalah simpul yang memiliki skor paling kecil dibanding simpul lainnya. Best first search menjadi jalan alternatif untuk menggabungkan manfaat dari metode depth dan breadth first search.

Sebagian penulis menggunakan alogritma best first search untuk merujuk pada pencarian heuristik. Heuristik sendiri merupakan metode yang lebih fokus dalam pengembangan efisiensi dalam pencarian dibanding kelengkapan. Para penulis yang menggunakan best first search biasanya mencoba memperkirakan jarak pada ujung jalur dengan solusi. Jika ada jalur yang lebih dekat dengan solusi, maka jalur itu akan diperpanjang terlebih dahulu . Jenis pencarian khusus ini disebut greedy best first search atau pure heuristic search. Greedy best first, dalam notasi matematika ditulis f(n) = h(n), karena hanya memperhitungkan skor perkiraan saja. Adapun skor yang sebenarnya tidak diperhitungkan.

Menggunakan algoritma greedy best first akan memperluas suksesor pertama dari parent. Jika suksesor telah terbentuk, akan ada dua kemungkinan. Yang pertama, jika suksesor heuristik lebih baik dari pada parent nya, maka suksesor akan diatur di depan queue (parent dimasukkan kembali di belakangnya), dan pengulangan kembali dimulai. Kemungkinan kedua, suksesor akan dimasukkan ke dalam queue (ke lokasi yang ditentukan oleh nilai heuristiknya).  Prosedur akan mengevaluasi suksesor yang tersisa dari parent.

Selain greedy best first, algoritma pencarian A* merupakan contoh lain dari algoritma best first search. Algoritma A* menggabungkan uniform cost search dengan greedy best first search. Algoritma ini disebut complete dan optimal karena skor yang diperhitungkan didapat dari skor sebenarnya ditambah skor perkiraan, atau dapat ditulis f(n)= g(n) + h(n)

Fungsi heuristik: f(n) = h(n)

Dimana h(n) adalah estimasi jarak garis lurus dari node ke goal.

Untuk mengimplementasikan prosedur pencarian grafik, kita akan membutuhkan 2 dua daftar simpul. Yang pertama adalah OPEN, simpul yang sudah dibuat tapi belum dievaluasi, dan CLOSED, simpul yang sudah dibuat dan sudah dievaluasi.

Algoritma:

1. Pertama, definisikan daftar OPEN dengan satu simpul sebagai simpul awal.
2. Kemudian, periksa apakah OPEN berisi atau kosong. Jika kosong, maka algoritma mengembalikan nilai gagal dan keluar.
3. Langkah selanjutnya, hapus simpul yang memiliki skor terbaik, n, dari OPEN kemudian pindahkan ke CLOSED.
4. Kemudian, kembangkan simpul n, dimana perluasannya merupakan identifikasi dari simpul suksesor n.
5. Selanjutnya periksa setiap simpul suksesor untuk melihat ada atau tidaknya simpul goal pada salah satunya. Jika ada suksesor yang menjadi simpul goal, maka algoritmanya akan mengembalikan nilai sukses dan solusinya, yang mana terdiri dari jalur yang ditelusuri mundur dari goal ke simpul awal. Jika tidak, lanjutkan ke langkah keenam.
6. Untuk langkah selanjutnya, untuk setiap simpul suksesor, algoritma menerapkan fungsi evaluasi f, kemudian memeriksa, melihat apakah simpul sudah berada di OPEN atau CLOSED. Jika simpul tidak ada di kedua daftar tersebut, maka akan ditambahkan ke OPEN.
7. Langkah selanjutnya adalah membangun struktur pengulangan dengan cara mengirimkan algoritma kembali ke langkah ke-2. Pengulangan ini akan berhenti jika algoritma mengembalikan nilai sukses di langkah 5 atau gagal di langkah 2.

Penulis : Syafira