Dian Irawati
3KA10
17115453
Dosen : Essy Malays Sari Sakti
2.1 Agen Pemecah Permasalahan
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:
Teknik searching sendiri terbagi menjadi dua, yaitu:
- Blind searching
- Heuristic searching
1. 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).
2. Blind Searching sendiri dibagi menjadi tiga macam yaitu :
- Breadth First Search (BFS)
- Depth First Search (DFS)
- Uniform Cost Search (UCS)
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 Strategi Pencarian yang tidak berbentuk
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
1.
Uninformed Search Algorithm
Algoritma yang tidak memberikan informasi tentang
permasalahan yang ada, hanya sebatas definisi dari algoritma tersebut.
2.
Informed Search Algorithm
Walaupun dengan menggunakan Uninformed Search Algorithm,
banyak permasalahan dapat dipecahkan, namun tidak semuanya dari algoritma
tersebut dapat menyelesaikan masalah dengan efisien
3.
Uninformed Search Algorithm
Uninformed Search sering disebut juga dengan Blind Search.
Istilah tersebut menggambarkan bahwa teknik pencarian ini tidak memiliki
informasi tambahan mengenai kondisi diluar dari yang disediakan oleh definisi
masalah. Yang dilakukan oleh algoritma ini adalah melakukan generate dari
successor dan membedakan goal state dari non-goal state. Pencarian dilakukan
berdasarkan pada urutan mana saja node yang hendak di-expand.
4.
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).
5.
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).
6.
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.
7.
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.
8.
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.
9.
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.
Referensi :
Pengantar Inteligensia Buatan – Heuristic Searching (Anonymous Writer)
Komentar
Posting Komentar