Metode Pencarian
dan Pelacakan
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 4 kriteria yang dapat digunakan
:
A. Completeness : apakah metode tersebut menjamin penemuan
solusi jika solusinya memang ada?
B.
Time complexity : berapa lama
waktu yang diperlukan? [semakin cepat, semakin baik]
C.
Space complexity : berapa banyak
memori yang diperlukan
D. 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
• Contoh pada
masalah 8 puzzle
keadaan
awal
Tujuan
Keadaan Awal Tujuan Pencarian Heuristik
• Operator
– Ubin kosong
geser ke kanan
– Ubin kosong
geser ke kiri
– Ubin kosong
geser ke atas
– Ubin kosong
geser ke bawah
• Langkah Awal
Gambar
• Langkah Awal
hanya 3 operator yang bisa digunakan
– Ubin kosong
digeser ke kiri, ke kanan dan ke atas.
• Jika
menggunakan pencarian buta, tidak perlu mengetahui operasi apa yang akan
dikerjakan (sembarang)
• Pada
pencarian heuristik perlu diberikan informasi khusus dalam domain tersebut
• Untuk jumlah
ubin yang menempati posisi yang benar jumlah yang lebih tinggi adalah yang
lebih diharapkan (lebih baik)
• Untuk jumlah
ubin yang menempati posisi yang salah jumlah yang lebih kecil adalah yang
diharapkan (lebih baik).
• Menghitung
total gerakan yang diperlukan untuk mencapai tujuan jumlah yang lebih kecil
adalah yang diharapkan (lebih baik).
Pencarian Heuristik
• 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.
Contoh : Traveling Salesman Problem (TSP)
Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota
sudah diketahui. Ingin diketahui rute terpendek dimana setiap kota hanya boleh
dikunjungi tepat 1 kali.
Contoh : Traveling Salesman Problem (TSP)
• Generate
& test akan membangkitkan semua solusi yang mungkin:
– A – B – C – D
– A – B – D – C
– A – C – B – D
– A – C – D – B, dll
Kelemahan dari
Pembangkit & Pengujian (Generate and Test) yaitu ;
– 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.
Contoh TSP
• 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.
• Untuk N kota,
akan ada operator sebanyak:
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.
• 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.
Daftar
pustaka :
