Materi4 searching
Download as ppt, pdf0 likes761 views
Dokumen ini membahas tentang searching sebagai salah satu cara untuk memecahkan masalah dalam sistem kecerdasan buatan. Terdapat berbagai jenis searching yang dibedakan menjadi searching tidak terarah (uninformed search) dan terarah (informed search). Contoh searching tidak terarah adalah breadth-first search, uniform cost search, dan depth-first search, sedangkan contoh searching terarah adalah hill climbing, best first search, generate and test, dan simulated annealing.
Materi4 searching
- 1. Problem Solving Searching Eddy Tungadi, ST, MT
- 2. 2 Pendahuluan Hubungan searching dengan AI ? Sistem AI, khususnya problem-solving agent (salah satu jenis goal-based agent), diharapkan dapat memecahkan suatu masalah secara autonomous. Salah satu cara untuk melakukannya, adalah dengan mencari langkah-langkah yang dapat mengantarkannya ke solusi menggunakan algoritma search. Pencarian solusi hanya bisa dilakukan setelah agent mengetahui apa yang dihadapinya, apa yang dicarinya perlu problem definition. Secara kasar, simple problem-solving agent : Percept Problem definition Search for solution Action.
- 3. 3 Problem Definition Problem definition (single-state problems) dapat dinyatakan dalam : contoh : lihat papan. Initial state : Keadaan/state awal. Operator : Aksi yang mungkin dilakukan agent. Aksi tersebut-lah yg. mampu memindahkan agent dari satu state ke state lain yang masih berada dalam state space-nya (himpunan seluruh state yang dapat dicapai dari initial state melalui serangkaian aksi, merupakan gabungan antara initial state dng. state-state yg. dihasilkan oleh operator yg. ada). Goal test : Menentukan apakah goal space telah tercapai atau belum. Solusi : path yg. menghubungkan intial state dng. goal state.
- 4. 4 Problem Definition Path cost function (g): Menentukan path mana (dlm. hal ini dapat dianggap juga rangkaian aksi) mana yg. lebih preferable. Problem definition utk. multiple-state problems hampir sama dng. problem definition utk. single-state problems, hanya saja state yg. ada berubah menjadi set of state. Beberapa perubahan: Initial state menjadi : Initial state set. State space menjadi : State set space. Path menghubungkan set of states satu ke set of states lain. Solusi : path yg. menghubungkan initial state set ke set of goal states.
- 5. 5 Searching Secara garis besar, searching dibedakan menjadi: Uninformed search (blind search). Tidak ada informasi mengenai jarak/cost dari current state ke goal state. Informed search. (heuristic search) Ada informasi mengenai jarak/cost dari current state ke goal state.
- 6. Hal yg. perlu diperhatikan dlm. searching : Completeness: jk. solusi ada, apakah pasti akan ditemukan ? Optimallity: jk. ada > 1 solusi, apakah selalu solusi terbaik yg. diperoleh ? Time Complexity: waktu yg. dibutuhkan utk. mendpt. solusi. Space complexity: memory yg. dibutuhkan utk. melakukan searching. 6
- 7. 7 Searching Contoh uninformed search : Breadth-first search (BFS). Uniform cost search. Depth-first search (DFS). Depth-limited search. Iterative deepening search (IDS). Bidirectional search.
- 8. 8 Breadth-First Search (BFS) Semua node solusi pada level n akan dikunjungi terlebih dahulu sebelum level n+1 Pencarian mulai dari akar kemudian ke level 1 mulai dari kiri ke kanan Complete (Jika ada satu solusi maka Bredth-First Search akan menemukannya) Membutuhkan memori yang cukup banyak Struktur data : queue. Optimal (jk. kedalaman node = path cost).
- 9. 9 Uniform Cost Search Utk. mengatasi agar search tetap optimal meskipun kedalaman node != path cost. Node diurutkan & di- expand berdasarkan path cost-nya. Akan = BFS jk. semua node n memiliki path cost(n)= depth(n). Complete. Optimal (jk semua path cost non-decreasing/tidak ada yg. negatif), lihat contoh di papan.
- 10. 10 Depth-First Search (DFS) Proses pencarian dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel Struktur data : stack. Tidak complete (bisa solusi ada, tapi stuck di inf. loop). Tidak optimal (bisa solusi yg. lebih baik ada, tapi yg. keambil yg. kurang baik). Keuntungan : Memori relatif kecil, Secara kebetulan akan menemukan solusi tanpa harus meguji lebih banyak lagi
- 11. 11 Depth-Limited Search Sama dng. DFS, hanya saja depth yg. akan di-expand dibatasi. Hal ini utk. menghindari inf. loop/pencarian yg. tdk. optimal krn. mencari terlalu dalam. Complete (batas depth >= depth(solusi) / Tidak complete (bisa solusi ada, tapi > batas depth). Tidak optimal (bisa ada > 1 solusi pd. depth < batas depth, tapi yg. keambil solusi yg. kurang baik).
- 12. 12 Iterative Deepening Search (IDS) Gabungan antara BFS & DFS. Pencarian dilakukan per level. Utk. tiap level, dilakukan DFS dng. level tersebut sebagai batas depth. Mengatasi kesulitan mencari batas depth pd. depth limited search. Complete. Optimal.
- 13. 13 Bidirectional Search Pencarian dilakukan 2 arah, dari root & dari goal. Solusi berhasil ditemukan ketika path dari root & goal bertemu. Complete. Optimal.
- 14. 14 Constraint Satisfaction Problem (CSP) States : values of a set of variables. Goal test : a set of constraints that the values must obey. Dapat diselesaikan dng. metode searching biasa & dpt. pula dng. algoritma khusus (constraint satisfaction search, lebih efisien). CSP dapat dikelompokkan menjadi : Berdasarkan banyaknya variabel dng. constraint : Unary, binary, higher-order. Apakah constraint merupakan keharusan atau preference : Absolute, preference. Berdasarkan nilai domain : Discrete, continuous.
- 15. 15 Constraint Satisfaction Search Dng. memanfaatkan constraint, node yg. perlu di- expand menjadi lebih sedikkit shg. waktu yg. dibutuhkan oleh searching lebih sedikit. Ada 2 macam : Backtracking search. Memeriksa yg. telah di-expand. Forward checking. Memeriksa dulu sebelum meng-expand.
- 16. Informed Search (Heuristic) Pendakian Bukit (Hill Climbing) Pencarian Terbaik Pertama (Best First Search) Pembangkit & Pengujian (Generate & Test) Simulated Annealing 16