BAB 4
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.2 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
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:
Tidak ada komentar:
Posting Komentar