Penyelesaian Masalah Melalui Proses Pencarian/Searching

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.

1.  Agen Pemecahan Permasalahan

•           Simple reflex agents: berdasarkan persepsi yg terakhir.

•           Model-based reflex agents: memiliki representasi internal tentang keadaan sekitar.

•           Goal-based agents: memiliki informasi tentang tujuan, memilih tindakan yang mencapai tujuan.

•           Utility-based agents: melakukan penilaian kuantitatif terhadap suatu keadaan lingkungan.

•           Learning agents: belajar dari pengalaman, meningkatkan kinerja.

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 :

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.

ppt
https://docs.google.com/presentation/d/1o3E8YVYT97HE62KXEeS5LDEY-PMRhia_Z72drHXxybg/edit#slide=id.p1

sumber:
http://socs.binus.ac.id/2013/04/23/uninformed-search-dan-informed-search/
http://bgustiardi.blogspot.com/2017/09/penyelesaian-masalah-melalui-proses.html#.W7SSbXsza03
http://radenrakha.blogspot.co.id/2014/02/pengertian-informed-dan-uninformed.html