Pertemuan 4

> Pencarian Heuristik ada 4 metode pencarian heuristik yaitu sebagai berikut:

1. Pembangkit & Pengujian (Generate and Test)
2. Pendakian Bukit (Hill Climbing)
3. Pencarian Terbaik Pertama (Best First Search)
4. Simulated Annealing

Hill Climbing

Gambar di bawah ini merupakan pencarian dengan menggunakan hill climbing













Pencarian Terbaik Pertama (Best First Search)

> Dengan metode pencarian hill climbing diatas maka kita akan melakukan pencarian terbaik
pertama (Best First Search) yaitu sebagai berikut:

• Metode best-first search ini merupakan kombinasi dari metode depth-first search dan metode breadth-first search dengan mengambil kelebihan dari kedua metode tersebut.
• Apabila pada pencarian dengan metode hill climbing tidak diperbolehkan untuk kembali ke node pada level yang lebih rendah meskipun node pada level yang lebih rendah tersebut memiliki nilai heuristik yang lebih baik, lain halnya dengan metode best-first search ini.
• Pada metode best-first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node pada lebih yang lebih tinggi ternyata memiliki nilai heuristik yang lebih buruk.
• Penentuan node berikutnya adalah node yang terbaik yang pernah dibangkitkan.
• Menggunakan informasi
  – biaya perkiraan
  – biaya sebenarnya
• Terdapat 2 jenis– Greedy Best First Search
  • biaya perkiraan f(n) = h(n)
  – A*
  • biaya perkiraan + biaya sebenarnya
  • f(n) = g(n) + h(n)
• Untuk mengimplementasikan metode ini menggunakan graph keadaan, dibutuhkan 2 antrian yang berisi node- node, yaitu:
  – OPEN, berisi node,node yang sudah dibangkitkan, namun belum diuji. Umumnya berupa antrian berprioritas yang berisi elemen-elemen dengan nilai heuristik tertinggi
  – CLOSED berisi node-node yang sudah diuji
• Algoritmanya sebagai berikut:
  – Tempatkan node awal A pada antrian OPEN.
  – Kerjakan langkah-langkah berikut hingga tujuan ditemukan atau antrian OPEN sudah kosong:
  – Ambil node terbaik dari OPEN;
  – Bangkitkan semua successornya;
  – Untuk tiap-tiap successor kerjakan:
  – Jika node tersebut belum pernah dibangkitkan sebelumnya, evaluasi node tersebut dan masukkan ke OPEN;
  – Jika node tersebut sudah pernah dibangkitkan sebelumnya, ubah parent jika lintasan baru lebih menjanjikan. Hapus node tersebut dari antrian OPEN.

> Contohnya sebagai berikut:


































Greedy Best First Search

> Contoh Pencarian menggunakan Greedy Best First Search sebagai berikut:





















OPEN = [A,B,C,D,E]
CLOSED = [S]

S Terbagi Menjadi A(yg memiliki nilai f=80), B(yg memiliki nilai f=60), C(yg memiliki nilai f=70), D(yg memiliki nilai f=85), E(yg memiliki nilai f=74)

Kemudian S menutup dirinya dan digantikan oleh A,B,C,D,E

OPEN = [A,C,D,E,F,K]
CLOSED = [S,B]

Kemudian dengan cara mencari nilai terendah dan terpendek pertama yaitu pada B, karena nilai A adalah 80 , sedangkan B 60, Maka B Menutup dan Membagi dirinya menjadi F(yg memiliki nilai f=70)dan K(yg memiliki nilai f=30).

OPEN = [A,C,D,E,F,G]
CLOSED = [S,B,K]
HASIL = S,B,K,G

Karena jarak ke F =70 sedangkan K= 30 , maka yg dipilih adalah K yg memiliki nilai yg lebih kecil dari dan K menutup dirinya yg digantikan oleh G (yg memiliki nilai f=0). Karena G sudah bernilai 0 dan tidak emiliki percabangan lagi,maka hasil yg diperoleh adalah S,B,K,dan G karena menggunakan metode pencari Best First Search.

> Contoh di atas merupakan pencarian menggunakan Greedy Best First Search

Pencaarian Menggunakan A*

> Ini merupakan Pencarian dengan menggunakan A*, contohnya sebagai berikut:

OPEN = [A,B,C,D,E]
CLOSED = [S]

S Menutup dirinya dan membagi dirinya menjadi A(yg memiliki nilai f=90),B(yg memiliki nilai f=85),C(yg memiliki nilai f=100),D(yg memiliki nilai f=120)dan E(yg memiliki nil ai f=84).




















OPEN = [A,B,C,D,J]
CLOSED = [S,E]

Karena Nilai E adalah nilai terkecil dengan nilai 84 +10 =94 sedangkan nilai A adalah 90+10=100 ,B =85+25=110, C= 100+30 =130, D= 120 +35=155 , maka yg terpilih adalah E yg kemudian terbagi menjadi D(yg memiliki nilai f=110) dan J(yg memiliki nilai f=130)

OPEN = [A,C,D,F,J,K]
CLOSED = [S,E,B]

Setelah dilihat dari nilai jumlah jarak kesuluruhan maka yg dipilih adalah B karana memiliki nilai jarak terkecil, Kemudian B menutup dirinya dan membagi menjadi F(yg memiliki nilai f=100) dan K( yg memiliki nilai f=105).













OPEN = [C,D,F,G,J,K]
CLOSED = [S,E,B,A]

Kemudian dilihat kembali jumlah jarak terpendek dan A adalah nilai jarak terpendek maka A dipilih dan A menutup dirinya. A membuka dirinya menjadi G(yg memiliki nilai f=100).

OPEN = [C,D,G,J,K]
CLOSED = [S,E,B,A,F]

Dilihat kembali nilai jarak terkecil , dan ditemukan nilai dari S-A-B-F lebih kecil dalu nilai F dipilih dan F menutup dirinya dan digantikan oleh nilai K(yg memiliki nilai f=95).












OPEN = [C,D,G,J]
CLOSED = [S,E,B,A,F,K]
HASIL = S,A,B,F,K,G

Hasilnya adalah jarak dari S-A-B-F-K-G adalah jarak dengan nilai terpendek dengan menggunakan metode A*.

> Dengan menggunakan kedua pencarian di atas ternyata pencarian dengan menggunakan A* lebih baik dibandingkan dengan Greedy Best First Search.

Lebih lengkap semua silakan download di bagian "Download Materi"