Metode Searching

Metode Pencarian/Pelacakan

• Hal penting dalam menentukan keberhasilan sistem AI adalah kesuksesan dalam pencarian solusi.
• Pencarian = suatu proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan/masalah (state space).
• Ruang keadaan/masalah = merupakan suatu ruang yang berisi semua keadaan yang mungkin.

Untuk mengukur kinerja metode pencarian, terdapat empat kriteria yang dapat digunakan :

• Completeness :
  apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada?

• Time complexity :
  berapa lama waktu yang diperlukan?

• Space complexity :
  berapa banyak memori yang diperlukan

• Optimality :
  apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda? 

Langkah-langkah dalam teknik searching :

1. Mendefinisikan RUANG MASALAH/RUANG KEADAAN untuk suatu masalah yg dihadapi.
2. Mendefinisikan aturan produksi yang digunakan untuk mengubah suatu “state” ke “state” lainnya.
3. Memilih metode pencarian yg tepat sehingga dapat menemukan solusi terbaik dengan usaha yang minimal.

Pada dasarnya terdapat 2 teknik pelacakan yang biasa digunakan :

1. Pencarian buta ( blind search )

2. Pencarian Terbimbing ( heuristic search )

Pengertian Teknik Pencarian dalam AI

Pencarian adalah suatu proses mencari solusi dari suatu permasalahn melalui sekumpulan ruang keadaan. Ruang keadaan adalah suatu ruang yang didalamnya berisi semua keadaan yang mungkin.

Kondisi dalam suatu pencarian menggunakan AI :

> Kondisi sekarang / keadaan awal

> Keadaan Tujuan yang merupakan solusi yang dijangkau apakah sudah mencapai sasaran .

> Biaya atau nilai yang diperoleh dari solusi

Solusi merupakan suatu lintasan dari keadaan awal sampai keadaan tujuan.

Uniform Cost Search

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.

Depth First Search

Algoritma DFS (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

Depth Limited Search Algoritma DLS (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.