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 :
1.
BFS (Breadth First Search)
2.
DFS (Depth-first Search)
3.
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 :
1.
Generate and Test
2.
Hill Climbing
3.
Best First Search
4.
Alpha Beta Prunning
5.
Means-End-Anlysis
6.
Constraint Satisfaction
3.
Strategi Pencarian yang tidak berbentuk
Algoritma ini tidak memberikan informasi apapun tentang
permasalah yang ada, tetapi hanya berfokus memberikan informasi tentang
algorima tersebut. Algoritma ini juga disebut Blind Search. Istilah Blind
Search berpedoman bahwa, teknik pencarian ini tidak memiliki informasi tambahan
lain selain dari yang disediakan.
Yang dilakukan oleh algorima ini adalah melakukan generate dari
successor dan membedakan goal state dari non-goal state. Pencarian ini
dilakukan berdasarkan pada urutan mana saja node yang hendak di-expand.
Macam-macam Uninformed Search Algorithm :
·
Breadth First Search(BFS)
Pencarian dengan metode
ini menggunakan teknik dimana langkah pertama yang harus dilakukan adalah root
node di-ekspansi, 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 memiliki successor lagi).
·
Uniform Cost Search(UCS)
Pencarian dengan BFS 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).
·
Depth First Search(DFS)
Teknik pencarian dengan
metode ini adalah dengan melakukan ekspansi menuju node yang paling dalam pada
tree. Node paling dalam dicirikan dengan tidak adanya successor dari node itu.
Setelah node selesai di ekspansi, maka node tersebut akan ditinggalkan dan
dilakukan ke node paling dalam lainnya yang masih memiliki successor yang belum
di ekspansi.
·
Depth Limited Search
Pencarian menggunakan DFS akan berlanjut sampai kedalam paling
terakhir dari sebuah tree. Misalkan yang muncul pada DFS adalah ketikda proses
pencarian tersebut menemui infinite state space. Hal ini bisa diatasi dengan
mengisiasikan batas depth pada level tertentu semenjak awal pencarian. Sehingga
node pada level depth tersebut akan diperlakukan seolah-olah mereka sudah tidak
memiliki successor.
·
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.
·
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.
Link Powerpoint : Teknik Searching.ppt
Link Pdf : Teknik Searching.pdf
Tidak ada komentar:
Posting Komentar