Untuk membangun sistem yang mampu menyelesaikan
masalah, perlu dipertimbangkan 4 hal:
– Mendefinisikan masalah dengan tepat
• Spesifikasi yang tepat mengenai keadaan awal
• Solusi yang diharapkan
– Menganalisis masalah serta mencari beberapa
teknik penyelesaian masalah yang sesuai
– Merepresentasikan pengetahuan yang perlu untuk
menyelesaikan masalah
– Memilih teknik penyelesaian masalah yang terbaik
Ruang Keadaan
(State Space)
• Suatu ruang yang berisi semua keadaan yang
mungkin
• Sehingga secara umum, untuk mendeskripsikan
masalah dengan baik, harus:
– Mendefinisikan suatu ruang keadaan
– Menetapkan satu atau lebih keadaan awal
– Menetapkan satu atau lebih tujuan
– Menetapkan kupulan aturan
• Ada beberapa cara untuk merepresentasikan
Ruang Keadaan
Penyelesaian masalah
secara umum
• Mendefinisikan suatu ruang keadaan;
• Menetapkan satu atau lebih keadaan awal;
• Menetapkan satu atau lebih tujuan;
• Menetapkan kumpulan aturan
Metode Pencarian dan
Pelacakan
• 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 buta
(blind search)
• Kekurangan
– Memungkinkan tidak ditemukannya
tujuan yang diharapkan
– Hanya akan mendapatkan 1 solusi pada
setiap pencarian
Tidak ada komentar:
Posting Komentar