Algoritma Heuristik - Best First Search

  • Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness).
  • Fungsi heuristik digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
  • Jenis-jenis Heuristic Searching:

– Generate and Test.

– Hill Climbing.

– Best First Search.

– Means-EndAnlysis, Constraint Satisfaction, dll

 

PENCARIAN TERBAIK PERTAMA (Best-First Search)

  • Metode ini merupakan kombinasi dari metode depthfirst search dan breadth-first search. Pada metode best-first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node pada level yang lebih tinggi ternyata memiliki nilai heuristic yang lebih buruk.
  • Fungsi Heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal state, yang dinyatakan dengan : 

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

    • f’ = Fungsi evaluasi
    • g = cost dari initial state ke current state
    • h’ = prakiraan cost dari current state ke goal state

 

  • Contoh soal 1 dan jawaban Algoritma Best First Search :
  • Misalkan kita memiliki ruang pencarian seperti pada gambar berikut. Node M merupakan keadaan awal dan node T merupakan tujuannya. Biaya edge yang menghubungkan node M dengannode A adalah biaya yang dikeluarkan untuk bergerak dari kota M ke kota A. Nilai g diperoleh berdasarkan biaya edge minimal. Sedangkan nilai h’ di node A merupakan hasil perkiraan terhadap biaya yang diperlukan dari node A untuk sampai ke tujuan. h’(n) bernilai ~ jika sudah jelas tidak ada hubungan antara node n dengan node tujuan (jalan buntu). Kita bisa merunut nilai untuk setiap node.

Teknik Pencarian Heuristik (Heuristic Search)

Teknik Pencarian Heuristik (Heuristic Search)

  • Contoh soal  2 dan jawaban Algoritma Best First Search  :
  • Selesaikan puzzle di bawah ini dari node awal A ke node tujuan Z, menggunakan algoritma Heuristik yaitu Algoritma Best First Search. Cara mengerjakan seperti studi kasus di bawah ini.

Node Tujuan Z

1 2 3
4 5 6
7 8  

Node Awal A

3 7 4
1   6
5 2 8

Berikut adalah proses penyelesaian sampai puzzle berubah ke node yang di inginkan

aniswindows1

aniswindows2

aniswindows3

sumber tambahan : http://shabri-prayogi.blogspot.co.id/2013/08/teknik-pencarian-heuristik-heuristic.html

Related Posts:

0 Response to "Algoritma Heuristik - Best First Search"

Posting Komentar

Komentar kamu aku tunggu :)