Saya coba lanjutkan beberapa catatan dari workshop AI yang diselenggarakan Fasilkom UI. Materi ini bagian kedua dari kuliah Intelligent System (sistem cerdas) pak Fariz, temanya tentang searching. Dalam sistem cerdas, bagian paling mendasar adalah tentang problem solving. Maksudnya bagaimana sistem cerdas dapat mencari solusi dari sebuah masalah. Langkah-langkah problem solving adalah:
- Goal Formulation
- Problem Formulation
- Searching for a solution
- Executing the solution
Contoh pertama yang diberikan adalah sbb: Vacation in Romania
- Goal Formulation: mencari jalan ke Bucharest
- Problem Formulation:
- action: mengemudi dari satu kota ke kota lain;
- State: Lokasi di sebuah kota
- Initial state: Arad
- Searching: Mencari jalur dari Arad ke bucharest
- Executing: Mengemudi dengan mengikuti panduan dari hasil searching
Contoh Lainnya:
- Vacuum Cleaner Bot
- Eight Puzzle
- N Queen
- Chatbot
Searching: proses mencari solusi dari masalah yang diberikan
Search tree: beberapa urutan aksi yang memungkinkan dari initial state; menggunakan beberapa algoritma untuk pergi dari initial state ke goal state
Algoritma Tree-Search:
function: tree-search (problem, strategy) returns a solution, or failure intialize the search tree using the intial state of the problem
loop do
if there are no candidates for expansion then return failure
choose a leaf node for expansion according to strategy
if the node contains a goal state then return the corresponding solution
else expand the node and add the resulting nodes to the search tree
Search strategy:
- Breadth First Search (BFS)
- Depth First Search (DFS)
- Uniform cost search (UCS)
Bread First Search
- Expand shallowest unexpanded node
- Queu data structure (FIFO)
contoh pada kasus Rumania
- jika terdapat solusi, menggunakan BFS pasti solusi akan ditemukan
- Hanya saja kompleksitas waktu dan space meningkat secara eksponensial
Depth First Search
- expand deepest unexpanded node
- Stack data structure (LIFO)
- Contoh pada kasus rumania:
DFS:
- Lower space complexity than BFS
- However, can get stuck going down a very long (or even infinite) path!
- Solution to avoid infinite path: Repeated state checking
- Still, repeated state checking does not guarantee optimality
Uniform Cost Search
-
expand unexpanded node with lowest path cost
-
Priority queue data structure, ordered by path cost from lowest to highest
- pada contoh kasus rumania
Heuristic
- BFS, DFS dan UCS adalah uninformed search
- Ketiganya tidak menggunakan heuristic (rule of thumb) untuk mempercepat pencarioan
- Fungsi heuristik digunakan untuk menghitung cost terendah pada jalur dari node n ke goal node
pada contoh kasus rumania diberikan fungsi heuristik jarak garis lurus kota X dengan bucharest
Greedy Search
- cari node yang sepertinya terdekat dengan tujuan
- Solusi: Arad – Sibiu – Fagaras – Bucharest
- Solusi ini tidak optimal!
A* Search
-
Greedy search itu greed (rakus) karena dia hanya menilihat nilai heuristik dari sebuah node
-
A* Search lebih berhati-hati, karena dia mengkombinasikan g(n): cost untuk mencapai current node n; h(n): nilai heuristic atau estimasi cost dari current node n ke goal node
f(n) = g(n) + h(n)
-
A* search lebih optimal ketika fungsi heuristik tidak overestimate cost untuk mencapai tujuan
- Arad; 366= 0 + 366; sibiu; 393=140+253 ; Rimnicu Vilcea: 413=220+193; Pitesti: 417= 317+100; Bucharest: 418=418+0
Adversarial Search
- Search pada lingkungan multiagent
- Sangat berguna pada game, dimana tujuan agent adalah maximize score dan tujuan lawan adalah untuk minimize score
- Tidak seperti search problem biasa, strategi yang diambil harus mempertimbangkan berbagai aksi lawan yang memungkinkan
- Contoh game Tic-tac-toe (catur jawa)
Sampai disini dulu, materi berikutnya adalah knowledge representation and reasoning. Insyaallah saya akan lanjutkan besok, semoga bermanfaat!
2 tanggapan untuk “Searching – Fariz Darari”
Terima kasih atas informasinya.
Izin bertanya pak, materi seperti ini itu ada di mata kuliah apa ya? Apakah ada di mata kuliah Algoritma dan Pemrograman? Terimakasih