Pencarian heuristik

• Pencarian heuristik
 Ada 4 macam metode dalam pencarian heuristik:
1). Pembangkit & Pengujian (Generate and Test)
2.) Pendakian Bukit (Hill Climbing)
3.) Pencarian Terbaik Pertama (Best First Search)
4.) Simulated Annealing

• Pencarian terbaik pertama ( Best First Search)
merupakan kombinasi dari metode depth-first search dan metode breadth-first search
dengan mengambil kelebihan dari kedua metode tersebut. Pada metode best-first search, ini , 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. Kemudian penentuan node berikutnya adalah node yang terbaikyang pernah dibangkitkan, yaitu dengan cara menngunakan informasi yamg terdiri atas biaya perkiraan dan biaya sebenarnya.
 Ada 2 jenis Pencarian Terbaik Pertama ( Best First Search), yaitu :
a.) Greedy Best First Search
 biaya perkiraan f(n) = h(n)
b.) A*
• biaya perkiraan + biaya sebenarnya
• f(n) = g(n) + h(n)
 Cara Untuk mengimplementasikan metode ini yaitu dengan menggunakan graph keadaan, dan dibutuhkan 2 antrian yang berisi node-node,yaitu:
- OPEN,* berisi node,node yang sudah dibangkitkan,namun belum diuji.
- CLOSED, * Umumnya berupa antrian berprioritas yang berisi elemen-elemen dengan nilai

heuristik tertinggi
* berisi node-node yang sudah diuji

 Algoritma:
1.) Pertama Tempatkan node awal A pada antrian OPEN.
2.) Kemudian Kerjakan langkah-langkah berikut hingga tujuan ditemukan atau antrian OPEN sudah kosong:
3.) Ambil node terbaik dari OPEN;
4.) Bangkitkan semua successornya;
5.) Untuk tiap-tiap successor kerjakan:
6.) Jika node tersebut belum pernah dibangkitkan sebelumnya,kemudian evaluasi node tersebut dan masukkan ke OPEN;
7.) Jika node tersebut sudah pernah dibangkitkan sebelumnya,setelah itu ubah parent jika lintasan baru lebih menjanjikan.dan langkah terakhir adalah hapus node tersebut dari antrian OPEN

Masalah, Ruang Keadaan dan Pencarian

Untuk membangun sistem yang mampu menyelesaikan

masalah, perlu dipertimbangkan 4 hal:

– Mendefinisikan masalah dengan tepat

• Spesifikasi yang tepat mengenai keadaan awal

• Solusi yang diharapkan

– Menganalisis masalah serta mencari beberapa

teknik penyelesaian masalah yang sesuai

– Merepresentasikan pengetahuan yang perlu untuk

menyelesaikan masalah

– Memilih teknik penyelesaian masalah yang terbaik

Ruang Keadaan

(State Space)

• Suatu ruang yang berisi semua keadaan yang

mungkin

• Sehingga secara umum, untuk mendeskripsikan

masalah dengan baik, harus:

– Mendefinisikan suatu ruang keadaan

– Menetapkan satu atau lebih keadaan awal

– Menetapkan satu atau lebih tujuan

– Menetapkan kupulan aturan

• Ada beberapa cara untuk merepresentasikan

Ruang Keadaan

Penyelesaian masalah

secara umum

• Mendefinisikan suatu ruang keadaan;

• Menetapkan satu atau lebih keadaan awal;

• Menetapkan satu atau lebih tujuan;

• Menetapkan kumpulan aturan

Metode Pencarian dan

Pelacakan

• Untuk mengukur perfomansi metode pencarian,

terdapat empat kriteria yang dapat digunakan :

– Completeness : apakah metode tersebut menjamin

penemuan solusi jika solusinya memang ada?

– Time complexity : berapa lama waktu yang

diperlukan?

– Space complexity : berapa banyak memori yang

diperlukan

– Optimality : apakah metode tersebut menjamin

menemukan solusi yang terbaik jika terdapat

beberapa solusi berbeda?

Dua teknik pencarian dan pelacakan

– Pencarian buta (blind search)

• Pencarian melebar pertama (Breadth – First

Search)

• Pencarian mendalam pertama (Depth – First

Search)

– Pencarian terbimbing (heuristic search)

• Pendakian Bukit (Hill Climbing)

• Pencarian Terbaik Pertama (Best First Search

Pencarian Melebar Pertama

(Breadth-First Search)

• Semua node pada level n akan dikunjungi

terlebih dahulu sebelum level n+1

• Mulai dari akar terus ke level 1 dari kiri ke

kanan

• Kemudian ke level selanjutnya hingga solusi

Ditemukan

Keuntungan

– Tidak akan menemui jalan buntu

– Menjamin ditemukannya solusi (jika solusinya

memang ada) dan solusi yang ditemukan pasti

yang paling baik

– Jika ada satu solusi maka bread-first search akan

Menemukannya

• Kelemahannya

– Membutuhkan memori yang cukup banyak

– Membutuhkan waktu yang cukup lama

Pencarian mendalam pertama

(Depth-First Search)

• Proses pencarian dilakukan pada semua

anaknya sebelum dilakukan pencarian ke

node-node yang selevel

• Keuntungan

– Memori yang relatif kecil

– Secara kebetulan, akan menemukan

solusi tanpa harus menguji lebih banyak

lagi

Pencarian buta

(blind search)

• Kekurangan

– Memungkinkan tidak ditemukannya

tujuan yang diharapkan

– Hanya akan mendapatkan 1 solusi pada

setiap pencarian