METODE PENCARIAN DAN PELACAKAN SISTEM INTELEGENSIA Pertemuan 4 Diema Hernyka S, M.Kom
Materi Bahasan Metode Pencarian & Pelacakan 1. Pencarian buta (blind search) a. Pencarian melebar pertama (Breadth – First Search) b. Pencarian mendalam pertama (Depth – First Search) 2. Pencarian terbimbing (heuristic search) a. Pembangkit & Pengujian b. Pendakian Bukit (Hill Climbing) c. Pencarian Terbaik Pertama (Best First Search)
Kriteria Untuk Mengukur Performansi Metode Pencarian dan Pelacakan 1. Completeness
2. Time complexity 3. Space complexity 4. Optimality
1. Pencarian Buta (Blind Search) 1.1 Pencarian melebar pertama (Breadth – First Search) 1.2 Pencarian mendalam pertama (Depth – First Search)
1.1 Pencarian Melebar Pertama (Breadth-First Search)
depth = 3
depth = 2
depth = 1
depth = 0
Breadth-First Search: Missionaries and Cannibals
Keuntungan & Kelemahan BFS
Keuntungan : Tidak akan menemui jalan buntu Jika ad satu solusi, maka BFS akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan Kelemahan : Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level yang ke-(n+1)
Algoritma BFS: 1. Buat suatu variabel Node_List dan tetapkan sebagai
keadaan awal. 2. Kerjakan langkah-langkah berikut ini sampai tujuan tercapai atau Node_List dalam keadan kosong : a. Hapus elemen pertama dari Node_List, sebut dengan nama E. Jika node_list kosong, keluar. b. Pada setiap langkah yang aturannya cocok dengan E, kerjakan : a. b. c.
Aplikasikan aturan tersebut untuk membentuk suatu keadaan baru. Jika keadaan awal adalah tujuan yang diharapkan, sukses dan keluar. Jika tidak demikian, tambahkan keadaan awal yang baru tersebut pada akhir Node_List.
1.2 Pencarian mendalam pertama (Depth-First Search)
depth = 3
depth = 2
depth = 1
depth = 0
Depth-First Search: Missionaries and Cannibals
Keuntungan & Kelemahan DFS Keuntungan Memori relatif kecil, node lintasan aktif saja yang disimpan. Secara kebetulan, metode ini akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan. Kelemahan Memungkinkan tidak ditemukannya tujuan yang diharapkan. Hanya akan mendapatkan satu solusi setiap pencarian.
2. Pencarian Heuristik 2.1 Generate And Test 2.2 Pendakian Bukit (Hill Climbing) 2.3 Pencarian Terbaik Pertama (Best First Search)
2. Pencarian Heuristik Contoh pada masalah 8 puzzle
Keadaan Awal
Tujuan
2. Pencarian Heuristik Operator – Ubin kosong geser ke kanan – Ubin kosong geser ke kiri – Ubin kosong geser ke atas – Ubin kosong geser ke bawah a.
2. Pencarian Heuristik b.
Informasi yang diberikan
– Untuk jumlah ubin yang menempati posisi yang benar
jumlah yang lebih tinggi adalah yang lebih diharapkan (lebih baik)
2. Pencarian Heuristik b.
Informasi yang diberikan
– Untuk jumlah ubin yang menempati posisi yang salah
jumlah yang lebih kecil adalah yang diharapkan (lebih baik).
2. Pencarian Heuristik b.
Informasi yang diberikan
– Menghitung total gerakan yang diperlukan untuk
mencapai tujuan jumlah yang lebih kecil adalah yang diharapkan (lebih baik).
2. Pencarian Heuristik Nilai terbaik adalah 2 (h=2) yang diperoleh dengan
menggeser ubin ke kiri. Nilai ini paling kecil dibanding dengan nilai lainnya (4). Sehinga menggeser ubin ke kiri adalah langkah yang harus dilakukan selanjutnya.
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: 1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal). 2. 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. 3. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah yang pertama.
2.1 Pembangkit & Pengujian (Generate and Test) Contoh pada TSP (Traveling Salesman Problem)
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.
2.1 Pembangkit & Pengujian (Generate and Test) Penyelesaian Traveling Salesman Problem (TSP)
1. 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
2.1 Pembangkit & Pengujian (Generate and Test) 2. Tentukan Lintasannya
2.1 Pembangkit & Pengujian (Generate and Test)
2.1 Pembangkit & Pengujian (Generate and Test) Kelemahan
– Perlu membangkitkan semua kemungkinan sebelum dilakukan pengujian – Membutuhkan waktu yang cukup lama dalam pencariannya
2.2 Pendakian Bukit (Hill Climbing) • Metode ini hampir sama dengan metode pembangkitan & pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik. • Pencarian dilihat dari anak kiri, bila nilai heuristik kiri lebih baik, maka dibuka untuk pencarian selanjutnya, bila tidak baru melihat tetangga dari anak kiri tersebut.
2.2 Pendakian Bukit (Hill Climbing) • 3 Masalah dalam SHC: 1. Algoritma akan berhenti kalau mencapai nilai optimim lokal 2.Urutan penggunaan operator akan sangat berpengaruh pada penemuan solusi 3.Tidak diijinkan untuk melihat satupun langkah sebelumnya
2.2 Pendakian Bukit (Hill Climbing) • Contoh Lihat kembali TSP
2.2 Pendakian Bukit (Hill Climbing) • Contoh Lihat kembali TSP
2.2. Steepest Ascent Hill Climbing • Contoh Lihat kembali TSP 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.
2.2. Steepest Ascent Hill Climbing
2.2. Steepest Ascent Hill Climbing • Ada 3 masalah pada pencarian ini : 1. Local optimum : keadan semua tetangga lebih buruk atau sama dengan keadaan dirinya 2. Plateu : keadaan tetangga sama dengan keadaan dirinya 3. Ridge : local optimum yang lebih disebabkan karena ketidakmampuan untuk menggunakan 2 operator sekaligus
2.3 Best First Search • Metode best first search merupakan kombinasi dari metode depth first search dan breadth first search • Dengan mengambil kelebihan dari kedua metode tersebut. Hill climbing tidak diperbolehkan untuk kembali ke node pada level lebih rendah meskipun node tersebut memiliki nilai heuristik lebih baik.
2.3 Best First Search • Pada best first search, pencarian diperbolehkan mengunjungi node di level lebih rendah, jika ternyata node di level lebih tinggi memiliki nilai heuristik lebih buruk.
2.3 Best First Search • Impelementasinya 2 antrian yang berisi nodenode • OPEN : berisi node-node yang sudah dibangkitkan, sudah memiliki fungsi heuristik namun belum diuji. Umumnya berupa antrian berprioritas yang berisi elemen-elemen dengan nilai heuristik tertinggi. • CLOSED : berisi node-node yang sudah diuji.
2.3 Best First Search
SELESAI Terima Kasih Atas Perhatiannya
