METODE PENCARIAN PADA AI

1. Metode Pencarian Buta (Blind Seaching)


Blind searching adalah pencarian yang tidak memiliki informasi awal, ciri-ciri :

• Membangkitkan simpul berdasarkan urutan

• Solusi akan ditemukan

• Hanya memiliki informasi tentang node yang sudah dibuka

A. BFS (Breadth First Search)





BFS merupakan model pencarian yang memakai metode meebar. Mencarir hasil dengan cara pencarian permasalahannya dengan cara membuka node pada tiap levelnya.


Keuntungan :

• Tidak akan menemui jalan buntu

• Jika ada solusi maka akan ditemukan dan jika ada lebih dari satu solusi maka akan dicari yang paling minimum

Kekurangan :

• Membutuhkan memori yang cukup banyak

• Kmunginan ditemukan optimal lokal

contoh :


Mencari jalur angkutan umum dari terminal senen ke terminal Kp. Rambutan


* Initial State : Senen


* Goal State : Kp. Rambutan






Rute Perjalanan



Penjelasan Gambar :


1. Membangkitkan anak dari terminal Senen = Terminal blok M, Terminal Pulo Gadung, Terminal Manggarai



2. Karena goal state (Terminal Kp. Rambutan) belum tercapai maka kita bangkitkan anak dari terminal senen


Terminal Blok M = Terminal Grogol, Terminal Lebak Bulus


Terminal Lebak Bulus = Terminal Ciputat, Terminal Kp. Rambutan.


Terminal Pulo Gadung = Terminal bekasi


Terminal Manggarai = Terminal Cililitan, Terminal Harmoni



B. DFS (Depth first search)





DFS merupakan pencarian mendalam, jadi pada metode ini akan mencari pada kedalaman sebelah kiri dahulu, kalau belum ditemukan hasilnya maka akan dicari ke sisi kanan sampai ditemukan hasilnya.


Keuntungan :

• Membutuhkan memori yang kecil

• Menemukan solusi tanpa harus menguji ruang

Kekurangan :

• Kemungkinan terjebak dalam optimal lokal

• Hanya akan mendapat 1 solusi

Contoh :




Penjelasan :


Pencarian dimulai dari simpul sebelah kiri yaitu ABD karena D tidak memiliki anak maka lanjut ke sebelah kanan yaitu E lalu FG. Anak-anak dari simpul B sudah habis maka lanjut ke simpul C dan di teruskan ke HIJK. K merupakan goal state dari pohon tersebut


Pada prinsipnya, DFS ini menggunakan tumpukan untuk menyimpan seluruh state yang ditemukan atau bisa dikatakan bahwa DFS menggunakan metode LIFO (Last In First Out).





2. Heuristic Searching


Heuristic searching merupakan metode pencarian yang memperlihatkan nilai perkiraan. Pada teknik ini sangat efisien sehingga tidak memboroskan waktu dan juga memiliki kemungkinan paling sukses. Fungsi heuristic ini mengevaluasi keadaan-keadaan masalah individual dan menentukan seberapa jauh untuk mendapat solusi yang diinginkan.





A. Generate and Test


Generate and test merupakan pendekatan yang paling sederhana tapi metode ini kurang efisien untuk masalah yang besar.


Contoh :


“Travelling Salesman Problem (TSP)” Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui ruter terpendek dimana setaip kota hanya boleh dikkunjungi tepat 1 kal i. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti gambar di bawah ini:











Penyelesaian dengan metode Generate and Test

















B. Hill Climbing


Salah satu metode generate and test dimana umpan balik yang berasal dari prosedur uji digunakan untuk memutuskan arah gerak dalam ruang pencarian. Fungsi uji hanyalah ya atau tidak.


Keuntungan :

• Membutuhkan memori yang relatif kecil

• Menemukan solusi tanpa harus menguji ruang

Kekurangan :

• Algoritma akan berhenti kalau mencapai nilai optimum lokal

• Tidak diijinkan untuk melihat satupun langkah sebelumnya

Prosedur Hill Climbing :

Buatlah solusi usulan pertama dengan cara yang sama seperti yang dilakukan dalam prosedur buat dan uji (generate and test). Periksalah apakah solusi usulan itu merupakan sebuah solusi. Jika ya, berhentilah. Jika tidak, kita lanjutkan ke langkah berikutnya.
Dari solusi ini, terapkan sejumlah aturan yang dapat diterapkan untuk membuat sekumpulan solusi usulan yang baru.
Untuk setiap elemen kumpulan solusi tersebut, lakukanlah hal-hal berikut ini :


1. Kirimkanlah elemen ini ke fungsi uji. Jika elemen ini merupakan sebuah solusi, berhentilah.


2. Jika tidak, periksalah apakah elemen ini merupakan yang terdekat dengan solusi yang telah diuji sejauh ini. Jika tidak, buanglah.


3. Ambilah elemen terbaik yang ditemukan di atas dan pakailah sebagai solusi usulan berikutnya. Langkah ini bersesuaian dengan langkah dalam ruang problema dengan arah yang muncul sebagai yang tercepat dalam mencapai tujuan.


4. Kembalilah ke langkah 2.


Contoh :


• Kasus Traveling Salesman Problem(TSP)







Sumber


http://izalhidayat.student.telkomuniversity.ac.id/gis/


http://tioramadhani.blogspot.co.id/2015/04/algoritma-metode-pencarian-buta.html


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