Bab 4 Metode Pencarian dan Pelacakan 1
Tugas Softskill Pengantar Teknologi Sistem Cerdas
Nama : Dewi Laras Wijayanti
NPM : 12114876
Kelas : 3KA10
Nama : Dewi Laras Wijayanti
NPM : 12114876
Kelas : 3KA10
Bab 4
Metode Pencarian
dan Pelacakan 1
Pada
bab sebelumnya kita telah membahas mengenai kecerdasaan buatan pada bab ini
saya akan menjelaskan mentode pencarian dan pelacakan metode ini sangat penting dalam menentukan
keberhasilan sistem cerdas adalah kesuksesan dalam pencarian. Pelacakan
adalah teknik untuk pencarian. Didalam pencarian ada dua kemungkinan hasil yang
didapat yaitu menemukan dan tidak menemukan. Sehingga pencarian merupakan
teknik yang penting dalam kecerdasaan buatan.
Pegertian dari Pencarian
itu sendiri adalah suatu proses mencari solusi dari suatu permasalahan melalui
sekumpulan kemungkinan ruang keadaan (state space).
Kemudian Ruang keadaan itu sendiri berarti suatu ruang yang berisi
semua keadaan yang mungkin.
Untuk mengukur
performansi metode pencarian, terdapat empat kriteria yang dapat digunakan :
·
Completeness (Kelengkapan) : apakah
metode tersebut menjamin penemuan solusi jika solusinya memang ada ?
·
Time compexity (Kekompleksan waktu) :
berapa lama waktu yang diperlukan ?
·
Space complexity (Kekompleksan ruang) :
berapa banyak memori yang di perlukan ?
·
Optimality (Optimal) : apakah metode
tersebut menjamin menemukan solusi yang terbaik jika beberapa solusi berbeda ?
4.1
Metode Pencarian Buta (Blind Search)
Pencarian buta (blind
search) memiiki dua tipe lain antaranya :
• Pencarian
melebar pertama (Breadth – First Search)
• Pencarian
mendalam pertama (Depth – First Search)
4.1.1
Breadth First Search
Pencarian Melebar
Pertama (Breadth-First Search)
Metode
ini akan mulai mencari dari node yang paling kiri, kemudian berpindah ke-node
se-level dengannya, dan berulang - ulang trus hingga menemukan solusi yang
dimaksud.
• 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
dari metode Breadth-First Search adalah
: pasti menemukan solusi yang dicari, tidak akan mengalami jalan buntu / tidak
menemukan solusi.
ü Kelemahan
metode Breadth-First Search adalah : memerlukan memori yang cukup besar, karena
metode ini mengecek keseluruhan node yang ada dan membutuhkan waktu yang lebih
untuk mengecek semua node yang ada tersebut.
4.1.2
Depth First Search
Depth
- Fisth Search : Metode ini dimulai dari semua
node-node anaknya kemudian berpindah ke node-node se-level nya.
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 Pencancarian Heurristik
Pencarian
terbimbing (Heuristic search) adalah Pencarian buta tidak selalu dapat diterapkan dengan
baik karena :
ü Waktu aksesnya yang cukup lama
ü Besarnya memori yang diperlukan
Namun diharapkan 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. Biasanya aplikasi yang menggunakan fungsi heuristic adalah Google,
Deep Blue Chess Machine , selain itu Heuristic search
terbagi menjadi 4 macam yaitu :
A. Pembangkit
& Pengujian
B. Hill
Climbing
C. Best
First Search (BFS)
D. Simulated
Annealing
A.
Pembangkit & Pengujian
Pembangkit
& Pengujian : Pada prinsipnya metode ini merupakan penggabungan antara
depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke
belakang menuju pada suatu keadaan awal. Terdapat kelemahan dalam metode ini :
Ø Perlu
membangkitkan semua kemungkinan sebelum dilakukan pengujian
Ø Membutuhkan
waktu yang cukup lama dalam pencariannya
B.
Hill Climbing
Hill
Climbing adalah metode ini hampir sama dengan metode pembangkitan &
pengujian, namun memiliki perbedaan dalam hal proses pengujian dilakukan. Hill
Climbing menggunakan fungsi heuristik dalam hal pencarian.
C. Algoritma Simple Hill Climbing
1.Mulai
dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan
jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.
2.Kerjakan
langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada
operator baru yang akan diaplikasikan pada keadaan sekarang:
3.Cari
operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan
keadaan yang baru.
4.Evaluasi
keadaan baru tersebut.
5.Jika
keadaan baru merupakan tujuan, keluar.
6.Jika bukan tujuan,
namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru
tersebut menjadi keadaan sekarang.
7.Jika keadaan baru
tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.
D. Algoritma 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.
DAFTAR
PUSTAKA
Komentar
Posting Komentar