Pencarian

Metode Pencarian dan Pelacakan

Hal penting dalam menentukan keberhasilan sistem cerdas adalah
kesuksesan dalam pencarian.
• Pencarian = suatu proses mencari solusi dari suatu permasalahan melalui
sekumpulan kemungkinan ruang keadaan (state space).
• Ruang keadaan = merupakan suatu ruang yang berisi semua keadaan yang mungkin

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 Heuristik
• Pencarian buta tidak selalu dapat diterapkan dengan baik
– Waktu aksesnya yang cukup lama
– Besarnya memori yang diperlukan
• Metode heuristic search diharapkan bisa menyelesaikan permasalahan yang lebih besar.
• Metode heuristic search menggunakan suatu fungsi yang menghitung biaya perkiraan (estimasi) dari suatu simpul tertentu menuju ke simpul tujuan ➔ disebut fungsi heuristic
• Aplikasi yang menggunakan fungsi heuristic : Google, Deep Blue Chess Machine

• Jika menggunakan pencarian buta, tidak perlu mengetahui operasi apa yang akan dikerjakan (sembarang)
• Pada pencarian heuristik perlu diberikan informasi khusus dalam domain tersebut

• Ada 4 metode pencarian heuristik:
– Pembangkit & Pengujian (Generate and Test)
– Pendakian Bukit (Hill Climbing)
– Pencarian Terbaik Pertama (Best First Search)
– Simulated Annealing

Pembangkit & Pengujian (Generate and Test)
• Pada prinsipnya metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal.
• Algoritma:

– Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal).
– Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.
– Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah yang pertama.

• Kelemahan
– Perlu membangkitkan semua kemungkinan sebelum dilakukan pengujian
– Membutuhkan waktu yang cukup lama dalam pencariannya

Pendakian Bukit (Hill Climbing)
• Metode ini hampir sama dengan metode pembangkitan & pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik.
• Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan.
• Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang
mungkin.

Simple Hill Climbing
• Algoritma
– Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan,
maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.
– Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan

sekarang:

• Cari operator yang belum pernah digunakan,gunakan operator ini
untuk mendapatkan keadaan yang baru.
• Evaluasi keadaan baru tersebut.
• Jika keadaan baru merupakan tujuan, keluar.
• Jika bukan tujuan, namun nilainya lebih baik daripada keadaan
sekarang, maka jadikan keadaan baru tersebut menjadi keadaan
sekarang.
• Jika keadaan baru tidak lebih baik daripada keadaan sekarang,
maka lanjutkan iterasi.

• Operator : Tukar kota ke-i dengan kota ke-j (Tk i,j)
• Untuk 4 kota:
– Tk 1,2 : tukar kota ke-1 dengan kota ke-2.
– Tk 1,3 : tukar kota ke-1 dengan kota ke-3.
– Tk 1,4 : tukar kota ke-1 dengan kota ke-4.
– Tk 2,3 : tukar kota ke-2 dengan kota ke-3.
– Tk 2,4 : tukar kota ke-2 dengan kota ke-4.
– Tk 3,4 : tukar kota ke-3 dengan kota ke-4.

Steepest Ascent Hill Climbing
• Steepest-ascent hill climbing sebenarnya hampir sama dengan simple hill climbing, hanya saja gerakan pencarian tidak dimulai dari posisi paling kiri.
• Gerakan selanjutnya dicari berdasarkan nilai heuristik terbaik.
• Dalam hal ini urutan penggunaan operator tidak menentukan penemuan solusi.

Algoritma
• Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.
• Kerjakan hingga tujuan tercapai atau hingga iterasi tidak memberikan perubahan pada keadaan sekarang.
• Tentukan SUCC sebagai nilai heuristic terbaik dari successorsuccessor.
• Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang:
• Gunakan operator tersebut dan bentuk keadaan baru.
• Evaluasi keadaan baru tersebut. Jika merupakan tujuan, keluar. Jika bukan, bandingkan nilai heuristiknya dengan SUCC. Jika lebih baik, jadikan nilai heuristic keadaan baru tersebut sebagai SUCC. Namun jika tidak lebih baik, nilai SUCC tidak berubah.
• Jika SUCC lebih baik daripada nilai heuristic keadaan sekarang, ubah node SUCC menjadi keadaan sekarang.

Pencarian Terbaik Pertama (Best First Search)
• 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 ternyatamemiliki 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 nodenode,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

Algoritma:
– Tempatkan node awal A pada antrian OPEN.
– Kerjakan langkah-langkah berikut hingga tujuanditemukan 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.

Leave a Reply

Your email address will not be published. Required fields are marked *