Pengertian dan Contoh Algoritma Best First Search

Best First Search merupakan salah satu contoh algoritma yang menerapkan heuristic search. Heuristic search ialah metode pencarian yang memperhatikan nilai heuristic (nilai perkiraan).

Heuristic Search memperkirakan jarak menuju goal (yang disebut dengan fungsi heuristik). Fungsi heuristik ini digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

Pengertian Best First Search

Best First Search menggunakan konsep pencarian heuristik (Heuristic Search) dan priority queue untuk memperluas simpul dari simpul sebelumnya dengan beberapa aturan tertentu. Tujuan dari algoritma ini adalah untuk mencapai titik tujuan atau titik akhir dengan rute sesingkat mungkin dari titik awal . 

Best first search akan memilih simpul atau node baru yang memiliki cost paling kecil diantara semua leaf node (simpul-simpul pada level terdalam) yang pernah dibangkitkan. Untuk mengambil simpul terbaik digunakan sebuah fungsi yang disebut fungsi evaluasi f(n). Fungsi evaluasi Best First Search dapat berupa cost perkiraan dari suatu simpul menuju ke goal atau gabungan antara cost sebenarnya dan cost perkiraan tersebut.

Pada setiap tahap dari proses pencarian node atau simpul terbaik, kita memilih node-node dengan menerapkan fungsi heuristik yang memadai dengan menggunakan aturan-aturan tertentu untuk menghasilkan penggantinya. Fungsi heuristik merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan (state space) suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan sepanjang jalur yang memiliki kemungkinan sukses paling besar. Sehingga, strategi ini digunakan untuk memecahkan masalah ketika tidak ada solusi yang tepat atau waktu untuk mendapatkan solusi terlalu lama. 

Adapun istilah yang sering digunakan pada metode best first search adalah sebagai berikut:

1. Start node adalah istilah untuk menyebut simpul awal sebuah pencarian.
2. Current node adalah simpul yang sedang dijalankan dalam algoritma pencarian jalan terpendek.
3. Succesor adalah simpul-simpul yang akan diperiksa setelah current node.
4. Simpul atau node merupakan representasi dari area pencarian.
5. Open list adalah tempat menyimpan data simpul yang mungkin diakses dari starting node maupun simpul yang sedang dijalankan.
6. Closed list adalah tempat menyimpan data simpul yang juga merupakan bagian dari jalur terpendek yang telah berhasil didapatkan.
7. Goal node yaitu simpul tujuan.
8. Parent adalah current node dari suksesor.

Algoritma Best First Search

Best first search merupakan metode atau teknik pencarian yang menggabungkan keunggulan yang ada dari teknik Depth First Search dan Breadth First Search. Tujuan menggabungkan dua teknik pencarian ini adalah untuk menelusuri satu jalur saja pada satu saat, tapi dapat berpindah ketika jalur lain terlihat lebih menjanjikan dari jalur yang sedang ditelusuri.

Pada algoritma best first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node di level yang lebih tinggi memiliki nilai heuristic yang lebih buruk.

Setiap sebuah node dikembangkan, algoritma ini akan menyimpan setiap successor node n sekaligus dengan harga (cost) dan petunjuk pendahulunya (parent). Algoritma akan berakhir pada goal node, dan tidak ada lagi pengembangan node selanjutnya.

Kata “best first” pada algoritma ini mengeksplorasi node dengan nilai terbaik yang pertama didapatkan. Sebuah fungsi evaluasi digunakan untuk menetapkan nilai untuk setiap calon node. Dalam algoritma ini, ruang pencarian dievaluasi menurut fungsi heuristic yang dinyatakan dengan persamaan berikut:

dimana:

f(n) = fungsi heuristik

h(n) = fungsi evaluasi yang dipakai untuk mengestimasi seberapa baik setiap node yang dibangkitkan.

Menggunakan nilai-nilai heuristik tiap node yang dibuka. Node dengan nilai heuristik terbaik akan dibuka lebih dahulu. Bila goal state belum ditemukan, akan dilakukan pemeriksaan pada simpul berikutnya dengan nilai heuristik terbaik pada kedalaman yang sama. Simpul tersebut kemudian dibuka dan diperiksa apakah terdapat goal state pada cabang-cabangnya. Bila goal state belum ditemukan, akan dilakukan proses yang sama pada simpul berikutnya.

Berikut ini adalah pseudo-code algoritma best first Search :

Procedure Best First Search
Begin
Open := [start];
Closed :=[];
While open ≠ [] do
Begin
  Remove the leftmost state from open,
    Call it X
    If X = a goal then return the path from start to X
    Else begin
      Generate children of X;
For each child of X do
Case
The child is not on open or closed;
Begin
Assign the child s heuristic value;
Add the child to open
End;
The child is already on open
If the child was reached by a shorter path
  Then give the state on open the shorter path
The child is already on closed;
If the child was reached by a shorter path
Begin
  Remove the state from closed;
  Add the child to open
End
Put X on closed;
Reorder state on open by heuristic merit (best left most);
Put remaining children on left end of open
End;
End
Return FAIL
End.

Untuk mengimplementasikan algortima pencarian ini, diperlukan dua buah senarai (list), yaitu: OPEN untuk mengelola node yang pernah dibangkitkan tetapi belum dievaluasi dan CLOSE untuk mengelola node yang pernah dibangkitkan dan sudah dievaluasi. Algoritma best first search adalah sebagai berikut:

1. Masukkan node awal ke dalam OPEN
2. OPEN berisi node awal dan CLOSE masih kosong
3. Masukkan node awal ke CLOSE dan successor nya pada OPEN list
4. Ulangi langkah berikut sampai goal ditemukan dan tidak ada lagi node yang akan dikembangkan:
1. Hitung nilai f nodes yang ada pada OPEN, ambil node terbaik (f terkecil)
2. Jika node tersebut sama dengan node tujuan, maka suks
3. Jika tidak, masukkan node tersebut ke dalam CLOSE
4. Bangkitkan semua successor dari node tersebut
5. Untuk setiap successor lakukan: 
1. Jika successor tersebut belum pernah dibangkitkan, evaluasi successor tersebut, tambahkan ke OPEN, dan catat parent-nya.
2. Jika successor tersebut sudah pernah dibangkitkan sebelumnya, ubah parent-nya jika lintasan baru lebih menjanjikan atau jalur melalui parent ini lebih baik daripada jalur melalui parent yang sebelumnya,. Selanjutnya, perbarui biaya untuk successor tersebut dan nodes lain yang berada di level bawahnya.

Contoh proses best first search dapat dilihat pada gambar dibawah ini:

Langkah-langkah yang dilakukan oleh algoritma Best First Search:

1. Bangkitkan node A. Kemudian semua successor A dibangkitkan, dan dicari cost paling minimal.
2. Node B terpilih karena memiliki cost paling rendah, yakni 2.
3. Semua successor B dibangkitkan, kemudian cost-nya akan dibandingkan dengan cost node C dan D. ternyata cost node D paling kecil dibandingkan cost node C, E, dan F. sehingga D terpilih dan selanjutnya akan dibangkitkan semua successor D.
4. Cost node H paling kecil dibandingkan cost node C, E, F, dan G. maka semua successor H dibangkitkan. Demikian seterusnya sampai ditemukan node tujuan.

Berbagi :