Penyelesaian Masalah Melalui Proses Pencarian / Searching

Pemecahan masalah adalah sebuah proses dimana suatu situasi diamati kemudian bila ditemukan ada masalah dibuat penyelesaiannya dengan cara menentukan masalah, mengurangi atau menghilangkan masalah atau mencegah masalah tersebut terjadi. Ada banyak urutan proses pemecahan masalah yang diajukan oleh para ahli, salah satunya seperti terlihat pada Gambar 1.12.

Pada gambar 1.12 terlihat serangkaian tahapan proses yang berbeda yang dapat digunakan dalam berbagai tingkatan, tergantung dari tipe dan sifat masalahnya. Masalah yang berbeda membutuhkan penggunaan cara yang berbeda, bahkan mungkin urutan yang berbeda. Tahapan kritis dari proses pemecahan masalah adalah Pendefinisian Masalah. Apabila masalah tidak cukup jelas didefinisikan maka tahapan-tahapan berikut sulit untuk dijalankan. Bahkan apabila dipaksakan, kemungkinan besar penyelesaian yang tepat tidak akan diperoleh.

gambar 1.12

Secara umum proses pemecahan masalah dapat dilakukan dengan empat tahapan utama yaitu :

Memahami dan mendefinisikan masalah

Bagian ini merupakan bagian yang sangat penting karena menjadi awal dari seluruh proses pemecahan masalah. Tujuan pada bagian ini adalah memahami masalah dengan baik dan menghilangkan bagian-bagian yang dirasa kurang penting.

Membuat rencana untuk pemecahan masalah

Pada bagian ini ada dua kegiatan penting yaitu :

mencari berbagai cara penyelesaian yang mungkin diterapkan

membuat rencana pemecahan masalah

Penyelesaian suatu masalah biasanya tidak hanya satu tapi mungkin bisa beberapa macam. Sebagai ilustrasi, apabila kita berada di kota Surabaya dan ingin pergi ke Jakarta, maka banyak cara yang mungkin bisa dilakukan, misalnya kita bisa menempuh dengan angkutan darat, laut atau udara. Dengan angkutan darat kita bisa menggunakan kereta api, bus atau angkutan yang lain. Jalurnya pun kita bisa lewat jalur utara, tengah atau selatan. Jadi banyak sekali cara penyelesaian yang bisa kita kembangkan. Masing-masing mempunyai karakteristik sendiri-sendiri. Dari sekian banyak penyelesaian ini kita harus memilih satu yang berdasarkan persyaratan tertentu merupakan cara yang paling baik untuk menyelesaikan permasalahan. Setelah terpilih, maka kita dapat membuat rencana kasar (outline) penyelesaian masalah dan membagi masalah dalam bagian-bagian yang lebih kecil. Rencana kasar (outline) penyelesaian masalah hanya berisi tahapan-tahapan utama penyelesaian masalah.

Merancang dan menerapkan rencana untuk memperoleh cara penyelesaian

Pada bagian ini rencana kasar penyelesaian masalah diperbaiki dan diperjelas dengan pembagian dan urutan rinci yang harus ditempuh dalam penyelesaian masalah.

Memeriksa dan menyampaikan hasil dari pemecahan masalah

Bagian ini bertujuan untuk memeriksa apakah akurasi (ketepatan) hasil dari cara yang dipilih telah memenuhi tujuan yang diinginkan. Selain itu juga untuk melihat bagaimana daya guna dari cara yang dipilih yang dipilih.

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 :

Uninformed Search Algorithm

Algoritma yang tidak memberikan informasi tentang permasalahan yang ada, hanya sebatas definisi dari algoritma tersebut.

Informed Search Algorithm

Walaupun dengan menggunakan Uninformed Search Algorithm, banyak permasalahan dapat dipecahkan, namun tidak semuanya dari algoritma tersebut dapat menyelesaikan masalah dengan efisien

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.

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).

Gambar 1 Penelusuran Ekspansi Node pada Breadth First Search

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).

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.

Gambar 2 Penelusuran Ekspansi Node pada Depth First Search

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.

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.

power point 
https://drive.google.com/open?id=10keH8lE9yO6-kzK3HG5ifCswU1lUtjfc

credits

http://socs.binus.ac.id/2013/04/23/uninformed-search-dan-informed-search/

ZAHRA FATIMAH
17116896
3KA12