Metode Pencarian (II)

Metode Pencarian

(Bagian II)

Pencarian dapat diartikan sebagai sebush proses pelacakan yang merupakan teknik untuk pencarian. Didalam pencarian ada dua kemungkinan hasil yang didapat yaitu menemukan dan tidak menemukan. Sehingga pencarian merupakan teknik yang penting dalam AI (Artificial Inteligen). Hal penting dalam menentukan keberhasilan sebuah sistem berdasarkan kecerdasan adalah kesuksesan dalam pencarian dan pencocokan. Pencarian adalah suatu proses mencari solusi dari suatu permasalahan agar dapat mendapat solusi melalui sekumpulan pencarian yang sudah diperoleh dengan semua kemungkinan keadaan. Untuk mengukur performansi metode pencarian, terdapat empat kriteria yang dapat digunakan:

·         Completeness (Kelengkapan)

·         Time compexity (Kekompleksan waktu)

·         Space complexity (Kekompleksan ruang)

·         Optimality (Optimal)

Ada beberapa teknik pelacakan :

·         Heuristic Search

Heuristic Search disebut sebagai model pencarian terbimbing atau sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness).

Fungsi heuristik digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

Ada beberapa metode yang tesedia di dalam Heuristic Search diantaranya:

1.      Pembangkitan dan Pengujian (Generate And Test)

Generate And Test yaitu model pencarian dengan car pembangkitan dan pengujian dan merupakan pendekatan yang paling sederhana dari semua pendekatan yang lainnya.

Sebagai Contoh:

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

Sehingga penyelesaian dengan menggunakan metode Generate and Test akan seperti ini

Pendekatan ini meliputi langkah–langkah sebagai berikut :

o   Membuat/bangkitkan sebuah solusi yang memungkinkan. Untuk sebuah problema hal ini dapat berarti pembuatan sebuah titik khusus dalam ruang problema.

o   Melakukan pengujian untuk melihat apakah solusi yang dibuat benar–benar merupakan sebuah solusi, dengan cara membandingkan titik khusus tersebut dengan goal-nya (solusi).

o   Jika telah diperoleh sebuah solusi, langkah – langkah tersebut dapat dihentikan. Jika belum, kembalilah ke langkah pertama.

Jika pembangkitan atau pembuatan solusi – solusi yang dimungkinkan dapat dilakukan secara sistematis, maka prosedur ini akan dapat segera menemukan solusinya (bila ada).  Namun, jika ruang problema sangat besar, maka proses ini akan membutuhkan waktu yang lama. Metode generate and test ini kurang efisien untuk masalah yang besar atau kompleks.

                Sehingga alur pencarian dari persoalan diatas akan menjadi seperti ini:

      Contoh diatas pada pencarian ke-1 terdapat lintasan ABCD dengan panjang lintasan 19  dan lintasan yang terpilih ABCD ddengan panjang lintasan terpilih 19. Pada pencarian ke-2 terdapat lintasan ABDC dengan panjang lintasan 18  dan lintasan yang terpilih ABDC dengan panjang lintasan terpilih 18. Dan pada pencarian ke-3 terdapat lintasan ACBD dengan panjang lintasan 12  dan lintasan yang terpilih ACBD dengan panjang lintasan terpilih pun 12. Dan seterusnya.

2.      Hill Climbing

Hill Climbing disebut sebagai pencarian Pendakian Bukit. Hill Climbing merupakan salah satu variasi dari metode generate and test. Dimana umpan balik yang berasal dari prosedur uji digunakan untuk memutuskan arah gerak dalam ruang pencarian (search).

Dalam prosedur generate and test, respon fungsi uji hanyalah ya atau tidak. Tetapi di dalam prosedur Hill Climbing, fungsi uji dikombinasikan dengan fungsi heuristik yang menyediakan pengukuran kedekatan suatu keadaan yang diberikan dengan tujuan/target.

                        Berikut ini adalah contoh dari Hill Climbing:

Prosedur Hill Climbing :

o   Membuatlah 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.

o   Dari solusi ini, terapkan sejumlah aturan yang dapat diterapkan untuk membuat sekumpulan solusi usulan yang baru.

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

o   Kembalilah ke langkah 2.

Sumber:

http://www.ziddu.com/download/23183192/MetodePencariandanPelacakan.docx.html

Pengantar Inteligensia Buatan – Heuristic Searching

Metode Pencarian (I)

Metode Pencarian

(Bagian I)

Pencarian dapat diartikan sebagai sebush proses pelacakan yang merupakan teknik untuk pencarian. Didalam pencarian ada dua kemungkinan hasil yang didapat yaitu menemukan dan tidak menemukan. Sehingga pencarian merupakan teknik yang penting dalam AI (Artificial Inteligen). Hal penting dalam menentukan keberhasilan sebuah sistem berdasarkan kecerdasan adalah kesuksesan dalam pencarian dan pencocokan. Pencarian adalah suatu proses mencari solusi dari suatu permasalahan agar dapat mendapat solusi melalui sekumpulan pencarian yang sudah diperoleh dengan semua kemungkinan keadaan. Untuk mengukur performansi metode pencarian, terdapat empat kriteria yang dapat digunakan:

·         Completeness (Kelengkapan)

·         Time compexity (Kekompleksan waktu)

·         Space complexity (Kekompleksan ruang)

·         Optimality (Optimal)

Ada beberapa teknik pelacakan :

·         Blind Search

Blind Search disebut sebagai model pencarian buta atau pencarian yang tidak memiliki inforamasi awal, model pencarian ini memiliki tiga ciri – ciri utama yaitu:
-          Membangkitkan simpul berdasarkan urutan
-          Jika ada solusi maka solusi akan ditemukan
-          Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui).

Ada beberapa metode yang tersedia di dalam Blind Search diantaranya:

1.      Breadth First Search

Breadth First Search yaitu model pencarian melebar pertama atau juga merupakan  model pencarian yang memakai metode melebar. Untuk dapat mencari hasilnya, model Breadth First Serach ini menggunakan teknik pencarian persoalan dengan cara membuka node (titik) pada tiap levelnya.

Sebagai Contoh:

Jadi, untuk pohon biner :

Maka, urutan penelusurannya adalah : a – b – c – d – e – f – g – h – i – j – k – l

Salah satu cara implementasi BFS adalah dengan bantuan struktur data queue. Sama seperti stack pada DFS, queue yang digunakan adalah queue yang isi elemennya adalah simpul pohon / tree.  Berikut ini adalah urutan algoritmanya :

o   Memasukkan simpul root ke dalam antrian.

o   Memeriksa antrian terdepan apakah memiliki anak simpul.

o   Jika ya, masukan semua anak simpul ke dalam antrian.

o   Menghapus antrian terdepan.

o   Jika antrian kosong berhenti, tapi jika tidak kembali ke langkah dua.

Untuk gambar pohon biner di atas, urutan langkah dan kondisi queue pada setiap iterasinya adalah sebagai berikut :

Contoh diatas menggunakan prioritas untuk memasukkan anak simpul dari sebelah kiri terlebih dahulu ke dalam queue. Sehingga, pada iterasi 2 elemen A dihapus lalu memasukkan anak simpulnya yaitu B dulu, baru C ke dalam stack. Untuk penelusurannya yang dilihat adalah bagian yang berwarna biru, yaitu antrian terdepan yang setiap iterasinya memiliki urutan a – b – c – d – e – f – g – h – i – j – k – l. Sama seperti DFS lagi pada iterasi ke 13 itu kondisi antrian sudah kosong.

2.      Depth First Search

Depth-first Search disebut juga pencarian mendalam pertama. Sesuai dengan namanya “pencarian mendalam”, Depth First Search tidak mencari solusi per level, namun mencari pada kedalaman sebelah kiri terlebih dahulu, kemudian bila belum ditemukan targetnya maka akan dilanjutkan ke sisi sebelah kanan dan seterusnya sampai ditemukan target. Pada DFS memori yang digunakan tidak terlalu banyak karena tidak membuka semua node.

Sebagai Contoh:

Jadi, jika ada pohon biner seperti gambar di bawah ini :

Maka, urutan penelusurannya adalah : a – b – d – h – e – i – c – f – g – j – k – l

Dalam implementasinya DFS dapat diselesaikan dengan cara rekursif atau dengan bantuan struktur data stack. Stack yang digunakan adalah stack yang isi elemennya adalah simpul pohon / tree. Berikut ini adalah urutan algoritmanya :

o   Memasukkan simpul root ke dalam tumpukan dengan push.

o   Mengambil dan menyimpan isi elemen (berupa simpul pohon) dari tumpukan teratas.

o   Menghapus isi stack teratas dengan prosedur pop.

o   Periksa apakah simpul pohon yang disimpan tadi memiliki anak simpul.

o   Jika ya, push semua anak simpul yang dibangkitkan ke dalam stack.

o   Jika tumpukan kosong berhenti, tapi jika tidak kembali ke langkah dua.

Jadi, untuk gambar pohon biner di atas urutan langkah dan kondisi stack-nya setiap iterasi adalah :

Contoh diatas menggunakan prioritas untuk memasukkan anak simpul dari sebelah kanan terlebih dahulu ke dalam stack. Sehingga, pada iterasi 2 elemen A dihapus lalu memasukkan anak simpulnya yaitu C dulu, baru B ke dalam stack. Selain itu bisa dilihat stack teratas (yang diwarna biru) pada tiap iterasi memiliki urutan a – b – d – h – e – i – c – f – g – j – k – l. Pada iterasi ke 13 kondisi stack sudah kosong karena ketika simpul J dibangkitkan tidak ada anak simpul yang dimasukkan ke stack.

Sumber:

http://www.ziddu.com/download/23183192/MetodePencariandanPelacakan.docx.html

Pengantar Inteligensia Buatan – Heuristic Searching