Penyelesaian Masalah :
I. Penyelesaian Masalah melalui proses Pencarian / Searching
2.1. Agen pemecah permasalahan
Dalam menentukan teknik penyelesaian terbaik dalam AI memang tidak mudah, untuk itu ada beberapa teknik penyelesaian masalah yang perlu kita pahami, antara lain:
1. Searching
Teknik penyelesaian masalah yang mempresentasikan masalah kedalam ruang keadaan (state) dan secara sistematis melakukan pembangkitan dan pengujian state-state dari initial state sampai ditemukan suatu goal state.
2. Reasoning
Teknik penyelesaian masalah yang mempresentasikan masalah kedalam logic (Mathematical Tools yang digunakan untuk merepresentasikan dan memanipulasi fakta dan aturan)
3. Planning
Memecah masalah dalam sub-sub masalah yang lebih kecil, menyelesaikan sub-sub masalah satu demi satu, kemudian menggabungkan solusi-solusi dari sub masalah tersebut menjadi sebuah solusi lengkap.
4. Learning
Program komputer yang secara otomatis sanggup belajar dan meningkatkan performancenya melalui pengalaman
2.2. Pencarian sebagai solusi pemecahan masalah
Searching di dalam AI (Artificial Intelligence) adalah salah satu motode penyelesaian masalah dengan pencarian solusi pada suatu permasalahan yang dihadapi.
Teknik searching sendiri terbagi menjadi dua, yaitu:
Ø Blind Searching
Blind Searching adalah model pencarian buta atau pencarian yang tidak memiliki inforamasi awal, model pencarian ini memiliki tiga ciri – ciri utama yaitu:
– Membangkitkan simpul berdasarkan urutan
– Kalau ada solusi maka solusi akan ditemukan
– Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui).
Blind Searching sendiri dibagi menjadi tiga macam yaitu :
- BFS (Breadth First Search)
- DFS (Depth-first Search)
- UCS (Uniform Cost Search).
Ø Heuristic Searching
Heuristic Search merupakan metode pencarian yang memperhatikan nilai heuristik (nilai perkiraan).Teknik pencarian heuristik (heuristic searching) merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan (state space) suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan di sepanjang jalur yang memiliki kemungkinan sukses paling besar, dan mengesampingkan usaha yang bodoh dan memboroskan waktu.
Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness).Heuristic Search memperkirakan jarak menuju Goal (yang disebut dengan fungsi heuristik).
Fungsi heuristik ini digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
Jenis-jenis Heuristic Searching :
- Generate and Test
- Hill Climbing
- Best First Search
- Alpha Beta Prunning
- Means-End-Anlysis
- Constraint Satisfaction
2.3.Strategi Pencarian yang tidak berbentuk (uniformed search strategy)
Searching adalah mekanisme pemecahan masalah yang paling umum di dalam kecerdasan buatan. Di dalam permasalahan-permasalahan kecerdasan buatan, urutan langkah-langkah yang dibutuhkan untuk memperoleh solusi merupakan suatu isu yang penting untuk diformulasikan. Hal ini harus dilakukan dengan mengidentifikasikan proses try and error secara sistematis pada eksplorasi setiap alternatif jalur yang ada.
Algoritma searching di dalam kecerdasan buatan yang umumnya dikenal adalah
a. Uninformed Search Algorithm
Algoritma yang tidak memberikan informasi tentang permasalahan yang ada, hanya sebatas definisi dari algoritma tersebut.
b. Informed Search Algorithm
Walaupun dengan menggunakan Uninformed Search Algorithm, banyak permasalahan dapat dipecahkan, namun tidak semuanya dari algoritma tersebut dapat menyelesaikan masalah dengan efisien.
Pada kesempatan kali ini saya hanya akan membahas tentang Strategi Pencarian Tidak Berbentuk (uninformed search strategy), diantaranya sebagai berikut :
1. Breadth First Search (BFS)
Pencarian dengan Breadth First Search menggunakan teknik dimana langkah pertamanya adalah root node diekspansi, setelah itu dilanjutkan semua successor dari root node juga di-expand. Hal ini terus dilakukan berulang-ulang hingga leaf (node pada level paling bawah yang sudah tidak mempunyai successor lagi).
Penelusuran Ekspansi Node pada Breadth First Search
2. Uniform Cost Search (UCS)
Pencarian dengan Breadth First Search akan menjadi optimal ketika nilai pada semua path adalah sama. Dengan sedikit perluasan, dapat ditemukan sebuah algoritma yang optimal dengan melihat kepada nilai tiap path di antara node-node yang ada.
Selain menjalankan fungsi algoritma BFS, Uniform Cost Search melakukan ekspansi node dengan nilai path yang paling kecil. Hal ini bisa dilakukan dengan membuat antrian pada successor yang ada berdasar kepada nilai path-nya (node disimpan dalam bentuk priority queue).
3. Depth First Search (DFS)
Teknik pencarian dengan Depth First Search adalah dengan melakukan ekspansi menuju node yang paling dalam pada tree. Node paling dalam dicirikan dengan tidak adanya successor dari node itu. Setelah node itu selesai diekspansi, maka node tersebut akan ditinggalkan, dan dilakukan ke node paling dalam lainnya yang masih memiliki successor yang belum diekspansi.
Penelusuran Ekspansi Node pada Depth First Search
4. Depth Limited Search
Pencarian menggunakan DFS akan berlanjut terus sampai kedalaman paling terakhir dari tree. Permasalahan yang muncul pada DFS adalah ketika proses pencarian tersebut menemui infinite state space. Hal ini bisa diatasi dengan menginisiasikan batas depth pada level tertentu semenjak awal pencarian. Sehingga node pada level depth tersebut akan diperlakukan seolah-olah mereka tidak memiliki successor.
5. Iterative Deepening Depth First Search
Iterative deepening search merupakan sebuah strategi umum yang biasanya dikombinasikan dengan depth first tree search, yang akan menemukan berapa depth limit terbaik untuk digunakan. Hal ini dilakukan dengan secara menambah limit secara bertahap, mulai dari 0,1, 2, dan seterusnya sampai goal sudah ditemukan.
6. Bidirectional Search
Pencarian dengan metode bidirectional search adalah dengan menjalankan dua pencarian secara simultan, yang satu dikerjakan secara forward dari initial state menuju ke goal, sedangkan yang satu lagi dikerjakan secara backward mulai dari goal ke initial state. Yang kemudian diharapkan bahwa kedua pencarian itu akan bertemu di tengah-tengah.
Keterangan
Nama: Mahmud Yusuf
Kelas: 3KA10
NPM: 14116231
Referensi
- http://alfarisidaffaa.blogspot.com/2017/10/pemecahan-masalah-pada-kecerdasan-buatan.html
- http://dianiraaa.blogspot.com/2017/09/pert-2-penyelesaian-masalah-dalam.html
- https://adiazep.wordpress.com/2017/11/12/penyelesaian-masalah-melalui-proses-pencarian-searching/
Download PPT >>> Penyelesaian Masalah melalui proses Pencarian/ Searching
EmoticonEmoticon