3 KA 10
16115925
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:
1. 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).
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 :
- 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 :

Tidak ada komentar:
Posting Komentar