METODE PENCARIAN BEST FIRST SEARCH

               Metode best first search ini merupakan kombinasi dari beberapa kelebihan teknik depth first search dan breadth first search. Pada pencarian dengan hill climbing tidak diperkenankan untuk kembali ke node pada level yang lebih rendah meskipun node pada level yang lebih rendah tersebut memiliki nilai heuristik yang lebih baik. Hal ini berbeda dengan metode best first search dimana pencarian diperkenankan mengunjungi node yang ada di level yang lebih rendah jika ternyata node pada level yang lebih tinggi ternyata memiliki heuristic yang buruk.

Ada dua jenis pencarian best first, yaitu:

A.    Graf OR

             Untuk jenis yang pertama ini, pengimplementasian dengan menggunakan graf keadaan, dibutuhkan dua antrian yang berisi node-node yaitu:

1.     OPEN, berisi node-node yang telah dihasilkan dan ada fungsi heuristic yang diterapkan padanya, namun belum diperiksa. Daftar ini sebenarnya berupa antrian berprioritas dengan elemen-elemen yang mempunyai prioritas tertinggi sebagai nilai fungsi heuristic yang paling dapat diharapkan.

2.     CLOSED berisi node-node yang telah diuji. 

           B.     Algoitma A*

            Algoritma A merupakan algoritma best first search dengan pemodifikasian fungsi heuristik, yang akan meminimumkan total biaya lintasan, dan pada kondisi yang tepat  akan memberikan solusi yang terbaik dalam waktu yang optimal.

Algoritma A juga membutuhkan dua antrian, yaitu OPEN dan CLOSED. Selain itu, ada juga fungsi heuristik yang memprediksi keuntungan tiap node yang di buat. Yang akan memungkinkan algoritma untuk melakukan pencarian-pencarian lintasan yang lebih di harapkan. Fungsi ini di sebut f’(n) sebagai pendekatan dari fungsi f(n) yang merupakan fungsi evaluasi yang sebenarnya terhadap node n. dalam banyak penarapan, akan lebih baik jika fungsi di definisikan sebagai kombinasi atau jumlah dua komponen yaitu g(n) dan h(n). Fungsi g(n) merupakan ukuran biaya yang di keluarkan dari keadaan awal sampai ke node n. Nilai yang didapat g(n) merupakan jumlahan biaya penerapan setiap aturan yang dilakukan pada sepanjang lintasan trbaik menuju suatu simpul dan bukan merupakan hasil estimasi.

Fungsi h(n) merupakan pengukur biaya tambahan yang harus dikeluarkan dari node n sampai mendapatkan tujuan. Perlu diketahui bahwa g(n), tidak negatif karena bila negatif maka lintasan yang membalik siklus pada graf akan tampak lebih baik dengan semakin panjangnya lintasan.

Secara matematis,fungsi F sebagai estimasi fungsi evaluasi terhadap node ndapat di tuliskan :

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

Dengan

    f’(n) = fungsi evaluasi

    g(n) = biaya yang sudah di keluarkan dari keadaan awal sampai

                keadaan n

    h’(n) = estimasi biaya untuk sampai pada suatu tujuan mulai dari

dari fungsi di atas maka ada beberapa kondisi yang perlu di perhatikan, yaitu :

Ø Jika h = h’, berarti proses pencarian telah sampai ke tujuan ( goal ).

Ø Jika g = h’ = 0 maka f’ random, artinya system tidak dapat di kendalikan oleh apa pun.

Ø Jika g = k, k adalah konstanta dan biasanya bernilai 1, h’ = 0, artinya system menggunakan breadth first search.

Contoh:

Berikut ini adalah peta Romania dengan jarak jalan-jalan yang menghubungkan kota-kota dalam km.

Adapun jarak kota-kota terhadap kota Bucharest jika ditarik garis lurus adalah sebagai berikut :

Permasalahannya adalah untuk mencari jalan terdekat dari kota Arad menuju kota Bucharest dengan menggunakan metoda Best First Search

Heuristik yang digunakan adalah jarak kota-kota terhadap kota Bucharest jika ditarik garis lurus yang jaraknya seperti yang tertera di atas dengan asumsi kota terhubung yang letaknya paling dekat dengan kota Bucharest adalah jalan yang paling optimal.

Dari Langkah-langkah di atas, dengan metode Best First Search didapatkan kota-kota yang harus dilalui untuk mendapatkan jalan yang paling dekat jaraknya dari Arad ke Bucharest adalah : Arad – Sibiu – Fagaras – Bucharest. Dari peta di atas, panjang jalan yang dilalui adalah 140+99+211 = 450 km.

KEUNTUNGAN

¨ Membutuhkan memori yang relatif kecil. karena hanya node-node pada lintasan yang aktif saja yang disimpan.

¨ Secara kebetulan, metode best first search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.

KELEMAHAN

¨ Algoritma akan berhenti kalau mencapai nilai lokal optimum.

¨ Tidak diijinkan untuk melihat satupun langkah sebelumnya.

source : http://elearning.upnjatim.ac.id/courses/KECERDASANBUATAN/work/4c5929fa45954BEST_FIRST_SEARCH.ppt