Metode Pencarian dan Pelacakan 1
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 :
Completeness : apakah metode tersebut menjamin
penemuan solusi jika solusinya memang ada?
Time complexity : berapa lama waktu yang diperlukan?
[semakin cepat, semakin baik]
Space complexity : berapa banyak memori yang
diperlukan
Optimality : apakah metode tersebut menjamin
menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda?
4.1 Metode Pencarian Buta
(Blind Search) :
4.1.1 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
4.1.2Pencarian
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
4.2 Metode 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 metode pencarian heuristik
– Pembangkit & Pengujian (Generate and Test)
– Pendakian Bukit (Hill Climbing)
4.2.1
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
4.2.2
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:
Daftar Pustaka:
Komentar
Posting Komentar