AI_20111010
0 likes546 views
Dokumen tersebut membahas metode-metode pencarian (searching) dalam masalah pemecahan masalah (problem solving) untuk agen berbasis pengetahuan (knowledge-based agents). Beberapa metode pencarian yang dijelaskan antara lain breadth-first search, depth-first search, depth-limited search, dan iterative deepening search beserta contoh penerapannya.
AI_20111010
- 1. Metode Pelacakan Buta Inteligensi Buatan (MKB6403) Kuliah 4 SEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN TEKNIK KOMPUTER INDONESIA (STMIK-INDONESIA) 息 2011 Cara Kerja Problem-Solving Agent 1. Perumusan tujuan (goal formulation): tentukan tujuan yang ingin dicapai 2. Perumusan masalah (problem formulation): tentukan tindakan (action) dan keadaan (state) yang dipertimbangkan dalam mencapai tujuan 3. Pencarian solusi masalah (searching): tentukan rangkaian tindakan yang perlu diambil untuk mencapai tujuan 4. Pelaksanaan solusi (execution): laksanakan rangkaian tindakan yang sudah ditentukan di tahap sebelumnya 10/19/2011 Metode Pelacakan Buta 2
- 2. Contoh Penelusuran Search Tree Mulai dari root node (Arad) sebagai current node Lakukan node expansion Pilih salah satu node yang di-expand sebagai current node yang baru. Ulangi langkah sebelumnya Arad Sibiu Timisoara Zerind Fagaras Oradea Rimnicu Vilcea 10/19/2011 Metode Pelacakan Buta 3 Algoritma Penelusuran Search Tree function GENERAL-SEARCH(problem,fringe) returns solution or failure fringe INSERT(MAKE-NODE(INITIAL-STATE(problem),fringe)) loop do if fringe is EMPTY than return failure node REMOVE-FIRST(fringe) if GOAL-TEST(problem) applied to STATE(node) succeeds then return node fringe INSERT-ALL(EXPAND(node,problem),fringe) end 1. Pada awal, fringe = himpunan node yang mewakili initial state 2. Pilih satu node dari fringe sebagai current node. Jika fringe kosong, selesai dengan gagal 3. Jika node tsb . lolos goal test, selesai dengan sukses! 4. Jika tidak, lakukan node expansion terhadap current node tsb. 5. Ulangi langkah 2 10/19/2011 Metode Pelacakan Buta 4
- 3. Strategi Pencarian Ada berbagai jenis strategi dalam melakukan searching. Perbedaannya terdapat pada node expansion-nya Search strategy dievaluasi berdasarkan: Completeness: apakah solusi (jika ada) pasti ditemukan? Time complexity: berapa lama untuk mencari solusi? atau berapa banyak jumlah node yang di-expand? Space complexity: jumlah maksimum node di dalam memori Optimality: apakah solusi dengan minimum cost pasti ditemukan? 10/19/2011 Metode Pelacakan Buta 5 Jenis-jenis Strategi Pencarian Ada 2 jenis strategi pencarian: Uninformed strategy, hanya menggunakan informasi dari definisi masalah Informed strategy, menggunakan informasi lainnya Uninformed strategy dapat diterapkan secara generik terhadap semua jenis masalah yang bisa direpresentasikan dalam sebuah state space 10/19/2011 Metode Pelacakan Buta 6
- 4. Jenis-jenis Uninformed Strategy Breadth-first Search (BFS) Depth-first Search (DFS) Depth-limited Search Iterative Deepening Search 10/19/2011 Metode Pelacakan Buta 7 Breadth-first Search Prinsip breadth-first search: Lakukan node expansion terhadap node di fringe yang paling dekat ke root systema c strategy Implementasi: fringe adalah sebuah queue, data struktur FIFO (First In First Out) Hasil node expansion (successor function) ditaruh di belakang 10/19/2011 Metode Pelacakan Buta 8
- 5. Breadth-first Search Prinsip breadth-first search: Lakukan node expansion terhadap node di fringe yang paling dekat ke root systema c strategy Implementasi: fringe adalah sebuah queue, data struktur FIFO (First In First Out) Hasil node expansion (successor function) ditaruh di belakang A 10/19/2011 Metode Pelacakan Buta 9 Breadth-first Search Prinsip breadth-first search: Lakukan node expansion terhadap node di fringe yang paling dekat ke root systema c strategy Implementasi: fringe adalah sebuah queue, data struktur FIFO (First In First Out) Hasil node expansion (successor function) ditaruh di belakang A B C 10/19/2011 Metode Pelacakan Buta 10
- 6. Breadth-first Search Prinsip breadth-first search: Lakukan node expansion terhadap node di fringe yang paling dekat ke root systema c strategy Implementasi: fringe adalah sebuah queue, data struktur FIFO (First In First Out) Hasil node expansion (successor function) ditaruh di belakang A B C D E 10/19/2011 Metode Pelacakan Buta 11 Breadth-first Search Prinsip breadth-first search: Lakukan node expansion terhadap node di fringe yang paling dekat ke root systema c strategy Implementasi: fringe adalah sebuah queue, data struktur FIFO (First In First Out) Hasil node expansion (successor function) ditaruh di belakang A B C D E F G 10/19/2011 Metode Pelacakan Buta 12
- 7. Cari solusi dari Arad ke Bucharet dengan menggunakan BFS! 10/19/2011 Metode Pelacakan Buta 13 Depth-first Search Prinsip depth-first search: Lakukan node expansion terhadap node di fringe yang paling jauh dari root Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last In First Out) 10/19/2011 Metode Pelacakan Buta 14
- 8. Depth-first Search Prinsip depth-first search: Lakukan node expansion terhadap node di fringe yang paling jauh dari root Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last In First Out) A 10/19/2011 Metode Pelacakan Buta 15 Depth-first Search Prinsip depth-first search: Lakukan node expansion terhadap node di fringe yang paling jauh dari root Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last In First Out) A B C 10/19/2011 Metode Pelacakan Buta 16
- 9. Depth-first Search Prinsip depth-first search: Lakukan node expansion terhadap node di fringe yang paling jauh dari root Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last In First Out) A B C D E 10/19/2011 Metode Pelacakan Buta 17 Depth-first Search Prinsip depth-first search: Lakukan node expansion terhadap node di fringe yang paling jauh dari root Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last In First Out) A B C D E H I 10/19/2011 Metode Pelacakan Buta 18
- 10. Depth-first Search Prinsip depth-first search: Lakukan node expansion terhadap node di fringe yang paling jauh dari root Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last In First Out) A B C D E H I 10/19/2011 Metode Pelacakan Buta 19 Depth-first Search Prinsip depth-first search: Lakukan node expansion terhadap node di fringe yang paling jauh dari root Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last In First Out) A B C D E H I J K 10/19/2011 Metode Pelacakan Buta 20
- 11. Depth-first Search Prinsip depth-first search: Lakukan node expansion terhadap node di fringe yang paling jauh dari root Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last In First Out) A B C D E H I J K 10/19/2011 Metode Pelacakan Buta 21 Depth-first Search Prinsip depth-first search: Lakukan node expansion terhadap node di fringe yang paling jauh dari root Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last In First Out) A B C D E F G H I J K 10/19/2011 Metode Pelacakan Buta 22
- 12. Depth-first Search Prinsip depth-first search: Lakukan node expansion terhadap node di fringe yang paling jauh dari root Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last In First Out) A B C D E F G H I J K L M 10/19/2011 Metode Pelacakan Buta 23 Depth-first Search Prinsip depth-first search: Lakukan node expansion terhadap node di fringe yang paling jauh dari root Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last In First Out) A B C D E F G H I J K L M 10/19/2011 Metode Pelacakan Buta 24
- 13. Depth-first Search Prinsip depth-first search: Lakukan node expansion terhadap node di fringe yang paling jauh dari root Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last In First Out) A B C D E F G H I J K L M N O 10/19/2011 Metode Pelacakan Buta 25 Cari solusi dari Arad ke Bucharet dengan menggunakan DFS! 10/19/2011 Metode Pelacakan Buta 26
- 14. Depth-limited Search Prinsip depth-limited search: Sama seperti depth-first search dengan depth yang terbatas. Contoh: Ada 20 kota dalam peta Rumania. Jika ada solusinya, maka length maksimum adalah 19. 10/19/2011 Metode Pelacakan Buta 27 Iterative Deepening Search Prinsip depth-first search: Lakukan depth-limited search secara bertahap dengan nilai l yang incremental 10/19/2011 Metode Pelacakan Buta 28
- 15. Iterative Deepening Search Prinsip depth-first search: Lakukan depth-limited search secara bertahap dengan nilai l yang incremental 10/19/2011 Metode Pelacakan Buta 29 Iterative Deepening Search Prinsip depth-first search: Lakukan depth-limited search secara bertahap dengan nilai l yang incremental 10/19/2011 Metode Pelacakan Buta 30
- 16. Iterative Deepening Search Prinsip depth-first search: Lakukan depth-limited search secara bertahap dengan nilai l yang incremental 10/19/2011 Metode Pelacakan Buta 31 Iterative Deepening Search Prinsip depth-first search: Lakukan depth-limited search secara bertahap dengan nilai l yang incremental 10/19/2011 Metode Pelacakan Buta 32
- 17. Cari solusi dari Arad ke Bucharet dengan menggunakan depth- limited search dengan l = 3! 10/19/2011 Metode Pelacakan Buta 33