Menyelesaikan Masalah Melalu Proses Pencarian/Searching

1.) Agen Pemecah Permasalahan

      Dalam membangun sebuah sistem AI, perlu dipertimbangkan 4 hal, yaitu:
1. Mendefinisikan masalah dengan tepat. Pendefinisian ini mencakup deskripsi masalah dengan baik
2.Menganalisis masalah tersebut serta mencari beberapa teknik penyelesaian masalah yang sesuai
3. Mempresentasikan pengetahuan yang perlu untuk menyelesaikan masalah tersebut
4. Memilih teknik penyelesaian masalah terbaik.

      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.) Pencarian Sebagai Solusi Pemecahan Masalah

      Metode pencarian dikatakan penting untuk solusi menyelesaikan permasalahan karean setiap keadaan menggambarkan langkah langkah untuk menyelesaikan permasalahan.Metode pencarian dikatakan penting untuk perencanaan karena dalam sebuah permainan akan menentukan apa yang harus dilakukan,dimana setiap keadaan menggambarkan kemungkinan posisi pada suatu saat.


3.) Strategi Pencarian yang tidak berbentuk/uniformed search strategi

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

• Breadth-First search

          Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian seterusnya.

          Algoritma ini memerlukan sebuah antrian q untuk menyimpan simpul yang telah dikunjungi. Simpul simpul ini diperlukan sebagai acuan untuk mengunjungi simpul-simpul yang bertetanggaan dengannya. Tiap simpul yang telah dikunjungu masuk ke dalam antrian hanya satu kali. Algoritma ini juga membutuhkan table Boolean untuk menyimpan simpul yang te lah dikunjungi sehingga tidak ada simpul yang dikunjungi lebih dari satu kali.

Untuk memperjelas cara kerja algoritma BFS beserta antrian yang digunakannya, berikut langkah-langkah algoritma BFS:
a.Masukkan simpul ujung (akar) ke dalam antrian
b.Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi
c.Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.
d,Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian
e.Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan
f.Ulangi pencarian dari langkah kedua

Maka penyelesaiannya adalah:

Gambar (a) BFS(1): 1, 2, 3, 4, 5, 6, 7, 1.

Gambar (b) BFS(1): 1, 2, 3, 4, 5, 6, 7, 1

Gambar (c) BFS(1): 1, 2, 3, 4, 5, 6, 7, 8, 9

• Uniform Cost Search

           Adalah algoritma Seach Tree (graph) yang digunakan untuk menyelesaikan beberapa persoalan . Algoritma ini memulai pencarian dari root node, kemudian dilanjutkan ke node-node selanjutnya. Dimana node tersebut dipilih yang memilki harga (cost) terkecil dari root node. Algoritma ini merupakan modifikasi dari Bread First Search (BFS).

            Dalam implementasi algoritma ini , melibatkan semua node yang berhubungan dengan root node, dan meletakannya dalam priority queue untuk mencapai node tujuan. Dimana node – node yang dipilih merupakan node yang berharga terkecil.

Ilustrasi jalannya algoritma Uniform Cost Search dapat digambarkan sebagai berikut :

• Depth First Search

          Adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik. Algoritma ini mirip dengan Algoritma BFS (Breadth First Search) yang sudah dijelaskan sebelumnya. Jika Algoritma BFS (Breadth First Search) melakukan perhitungan secara terurut dari urutan pertama sampai urutan terakhir, maka algoritma ini melakukan kebalikannya, yaitu melakukan perhitungan secara terurut dari urutan terakhir. Setelah menghabiskan semua kemungkinan dari titik terakhir, barulah mundur ke titik-titik sebelumnya sampai pada titik pertama. 

• Depth Limited Search

          Adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik.

          Algoritma ini merupakan variasi dari Algoritma DFS (Depth First Search) yang sudah dijelaskan sebelumnya. Jika Algoritma DFS (Depth First Search) melakukan perhitungan (yang dimulai dengan titik terakhir) dengan cara menghabiskan semua tingkatan / kedalaman dari sebuah titik, maka algoritma ini memiliki batasan dimana perhitungan pada sebuah titik hanya dihitung sampai pada kedalaman tertentu. Setelah semua kemungkinan pada kedalaman itu sudah habis, kemudian akan dilanjutkan pada titik berikutnya.

• Bidirectional Search

          Pencarian dengan metode bidirectional search adalah dengan menjalankan dua pencarian, pencarian maju (dari start ke goal) dan pencarian mundur (dari goal ke start). Ketika dua arah pencarian telah membangkitkan simpul yang sama, maka solusi telah ditemukan, yaitu dengan cara menggabungkan kedua jalur yang bertemu.

• Iterative Deeping Depts Search

         Metode Iterative Deepening A* Iterative-Deepening A* (IDA*) search algorithm adalah pengembangan dari A*search algorithm yang dikombinasikan dengan iterative deepening search. IDA* search algorithm merupakan best-first searches yang optimal dalam hal solution cost, time, dan space. Prinsip algoritma iterative deepening search adalah melakukan depth-limited search secara bertahap dengan nilai l yang incremental . Contoh cara kerja iterative deepening search dapat dilihat pada gambar di bawah ini:

Sumber : 

https://onbuble.wordpress.com/2011/05/26/6/

https://banyurachman.wordpress.com/2015/09/21/sekilas-tentang-uniform-cost-search-iterative-deepening-search/

https://piptools.net/algoritma-dfs-depth-first-search/

https://piptools.net/algoritma-dls-depth-limited-search/

http://najibzot.blogspot.co.id/p/teknik-searching-kecerdasan-buatan-di.html

http://rosyid.lecturer.pens.ac.id/kecerdasaran%20komputasional/Bab%204%20Algoritma%20Pencarian.pdf

http://tiindonesia.blogspot.co.id/2013/02/teknik-pemecahan-masalah-dalam-ai.html

http://jakaseptiadi.blogspot.co.id/2015/09/bi-directional-search-bds-depth-limited.html