Jelaskan apa perbedaan Blind Search dan Heuristic Search?

SEARCHING Blind Search & Heuristic Search

PENDAHULUAN Banyak cara yang digunakan untuk membangun sistem yang dapat menyelesaikan masalah-masalah di AI. Teknik penyelesaian masalah yang dapat dipakai untuk menyelesaikan permasalahan di AI antara lain : 1. Searching (pencarian) 2. Reasoning (penalaran) 3. Planning : memecah masalah menjadi sub-sub masalah satu demi satu untuk kemudian menggabungkan sub sub masalah tersebut menjadi solusi yang lengkap 4. Learning : program komputer yang secara otomatis sanggup belajar dan meningkatkan performance nya melalui pengalaman

Searching dibagi menjadi 2 yaitu : 1. Blind Search 2. Heuristic Search

Blind Search Blind Search yaitu metode sederhana yang hanya berusaha mencari semua kemungkinan penyelesaian masalah serta tidak ada informasi awal yang bisa digunakan dalam proses pencarian Algoritma yang digunakan : a. Breadth First Search (BFS) b. Depth First Search (DFS) c. Uniform Cost Search (UCS) d. Depth-Limited Search (DLS) e. Iterative Deepening Search (IDS) f. Bi-Directional Search (BDS)

CONTOH Menghitung Rute Terpendek Menggunakan Algoritma BFS (Studi Kasus : Uin Susqa ke Mall Ska) Hasil dari proyeksi gambar Google Earth didapatkan pengambilan nodenya berdasarkan persimpangan jalan. Tujuh node, dimana A = UIN SUSQA ; B = Simpang Garuda Sakti HR Soebrantas ; C = Simpang Garuda Sakti Akap ; D = Bundaran SM Yamin - Tuanku Tambusai ; E = Simpang HR Soebrantas - SM Yamin ; F = Simpang Pasar Pagi Arengka ; G = MALL SKA

Kasus di atas akan diselesaikan dengan BFS Pengertian : BFS akan melakukan pencarian pada semua simpul dalam setiap level secara berurutan dari kiri ke kanan. Jika pada satu level belum ditemukan solusi, maka pencarian akan dilanjutkan ke level berikutnya hingga solusi ditemukan. Berikut adalah langkah-langkah algoritma BFS 1. Masukkan node akar ke dalam QUEUE 2. Ambil node dari awal QUEUE, lalu cek apakah node merupakan solusi 3. Jika node merupakan solusi, pencarian selesai dan hasil dikembalikan 4. Jika node bukan solusi, masukkan seluruh node anak ke dalam QUEUE 5. Jika QUEUE kosong dan setiap node sudah dicek, pencarian selesai. 6. Jika QUEUE tidak kosong, ulangi pencarian mulai dari poin 2

Iterasi ke 1 masukkan node A ke QUEUE. keluarkan A dari QUEUE dan cek apakah A adalah goal? QUEUE Masuk Lewat Pintu Kiri, Keluar Lewat Pintu kanan representasi ruang keadaan : A ternyata A goal, maka masukkan A ke solusi Solusi : A

representasi ruang keadaan : A B Iterasi ke 2 masukkan node anak A yaitu B ke QUEUE. keluarkan B dari QUEUE dan cek apakah B adalah goal? QUEUE Masuk Lewat Pintu Kiri, Keluar Lewat Pintu kanan ternyata B goal, masukkan B ke solusi Solusi : A B

representasi ruang keadaan : A B D C Iterasi ke 3 masukkan node anak B yaitu D & C ke QUEUE. keluarkan D dari QUEUE dan cek apakah D adalah goal? ternyata D goal, masukkan D ke solusi Solusi : A B D

representasi ruang keadaan : A B D C Iterasi ke 4 masukkan node anak D yaitu F & E ke QUEUE. F E keluarkan C dari QUEUE dan cek apakah C adalah goal? ternyata C goal, masukkan C ke solusi Solusi : A B D C

representasi ruang keadaan : A B D C Iterasi ke 5 masukkan node anak C yaitu E ke QUEUE. Namun karna E sudah ada di Queue maka tidak dimasukkan. F E keluarkan F dari QUEUE dan cek apakah F adalah goal? ternyata F goal, masukkan F ke solusi Solusi : A B D F

representasi ruang keadaan : A B D C Iterasi ke 6 masukkan node anak F yaitu G ke QUEUE. G F E keluarkan E dari QUEUE dan cek apakah E adalah goal? ternyata E goal, masukkan E ke solusi Solusi : A B D F E

representasi ruang keadaan : A B D C Iterasi ke 7 masukkan node anak E yaitu G ke QUEUE. Namun karna G sudah ada di QUEUE maka tidak perlu dimasukkan lagi. G F E keluarkan G dari QUEUE dan cek apakah G adalah goal? ternyata G = goal, masukkan G ke solusi Solusi : A B D F E G

Solusi dicari dengan merunut dari G Parent G adalah F maka G F Parent F adalah D maka G F D Parent D adalah B maka G F D B Parent B adalah A maka G F D B A Karna A adalah root maka jalur dari node A ke G adalah A B D F G

Heuristic Search Pencarian buta biasanya tidak efisien karena waktu akses memori yang dibutuhkan cukup besar. Untuk mengatasi hal ini maka perlu ditambahkan suatu informasi pada domain yang bersangkutan sehingga proses pencarian yang baru akan dihasilkan. Pencarian seperti ini disebut sebagai informed search atau pencarian heuristic atau pencarian terbimbing, yaitu pencarian berdasarkan panduan. (Dalam sutojo dkk) teknik pencarian heuristic merupakan suatu strategi untuk melakukan proses pencarian secara selektif dan dapat memandu proses pencarian yang memiliki kemungkinan sukses paling besar, namun dengan kemungkinan mengorbankan kelengkapan (completeness) Contoh algoritma : Generate and Test, Hill Climbing (simple Hill climbing atau Stepest Ascent Hill Climbing), Simulated Annealing, Best First Search, A* dan lain-lain.

Kasus di atas akan diselesaikan dengan A* Algoritma A* merupakan perbaikan dari metode best first search dengan memodifikasi fungsi heuristiknya, Algoritma A* akan meminimumkan total biaya lintasan. Pada kondisi yang tepat, Algoritma A* akan memberikan solusi yang terbaik dalam waktu yang optimal (Kusumadewi, 2003). Fungsi f(n) sebagai estimasi fungsi evaluasi dihitung dengan persamaan : f(n) = g(n) + h(n) dengan : f(n) = fungsi evaluasi g(n) = biaya yang sudah dikeluarkan dari keadaan awal sampai keadaan n h(n) = estimasi biaya untuk sampai pada suatu tujuan mulai dari n

CONTOH : sumber http://web.unair.ac.id/admin/file/f_22581_algoritma_a_star_search.pptx Menghitung Rute Terpendek Menggunakan Algoritma A* Search Dengan Fungsi Heuristik Euclidean Distance. (Studi Kasus : Uin Susqa Mall Ska) Hasil dari proyeksi gambar Google Earth didapatkan Tujuh node, dimana pengambilan nodenya berdasarkan persimpangan jalan. A = UIN SUSQA ; B = Simpang Garuda Sakti HR Soebrantas ; C = Simpang Garuda Sakti Akap ; D = Bundaran SM Yamin - Tuanku Tambusai ; E = Simpang HR Soebrantas - SM Yamin ; F = Simpang Pasar Pagi Arengka ; G = MALL SKA

Setiap Index mewakili jarak 200 meter A = UIN SUSQA (0,0) B = Simpang Garuda Sakti - HR Soebrantas (6,0) C = Simpang Garuda Sakti Akap (2,11) D = Bundaran SM Yamin - Tuanku Tambusai (21,0) E = Simpang HR Soebrantas - SM Yamin (21,20) F = Simpang Pasar Pagi Arengka (36,0) G = MALL SKA (36,20)

Langkah 1 : Menghitung Heuristik Rumus jarak dua titik: Dengan menggunakan rumus di atas, maka perhitungan dari semua titik dapat dilihat sebagai berikut:

LANGKAH 2 MENCARI NILAI f(n) ALGORITMA A* Setelah nilai heuristik dari masing-masing node didapat maka kita akan mencari f(n) menggunakan algoritma A* dengan rumus: dimana, h(n) = Nilai heuristik antar Koordinat ; g(n) = Jarak Koordinat ke titik tujuan Step 1 : Penyelesaian Kasus

Titik B memiliki 2 cabangan yaitu titik C dan titik D, maka f(n) yang harus dipilih adalah f(n) yang menghasilkan biaya paling kecil, yaitu titik C.

Maka f(n) total yang didapat adalah 123.72, karena satu titik ordinat mewakili 200 meter maka jaraknya sebenarnya (dalam meter) adalah: = 123.72 200 = 24744 meter = 24,744 km Jalur yang dilalui: A B C E G UIN SUSQA Jln HR Soebrantas Simpang Garuda Sakti Jln Tuanku Tambusai II Mall SKA

A.  Metode Pencarian Buta (Blind Search)

Blind Search merupakan pencarian asal ketemu. Jika solusi sudah ketemu, maka pencarian akan dihentikan. Jika dibuat skemanya, pencarian buta hanya mengenal tiga bagian, [masalah]-[pencarian]-[solusi]. Misalkan dalam kotak ada 3 kelereng warna merah, 3 biru, dan 3 kuning. Masalahnya adalah, ambillah satu kelereng yang berwarna merah. Solusi, setelah melakukan pencarian, kemudian didapat satu kelereng warna merah, nah, itulah solusinya.

Breadth First Search merupakan salah satu dari metode pencarian buta. istilah buta disini lebih dikenal dengan nama blind. Dikatakan buta karena memang tidak ada informasi awal yang digunakan dalam proses pencarian.

Breadth-first search (BFS) melakukan proses searching pada semua node yang berada pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan proses searching pada node di level berikutnya. 

Breadth First Search (BFS) juga memiliki alur algoritma yang paling sederhana dibandingkan dengan metode blind yang lain. Itulah alasan mengapa BFS selalu dipelajari lebih dulu ketika membahas masalah pencarian buta. 

Sebelum menelaah lebih jauh bagaimana metode BFS dijalankan, kita telisik dulu mengapa metode ini dinamakan pencarian Breadth First. Breadth dapat diartikan dengan luas / lebar, sedangkan first adalah pertama. Penamaan metode ini disesuaikan dengan konsep algoritma secara garis besar yaitu melakukan proses pencarian pada semua node yang berada pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan proses pencarian pada node di level berikutnya.
Contoh :

BFS akan mencari satu per satu node secara melebar dari kiri ke kanan secara berurutan berdasarkan tingkat level nodenya. Jika pada satu level belum ditemukan solusi yang diinginkan, maka pencarian dilanjutkan hingga level berikutnya. Demikian seterusnya hingga ditemukan solusi. Maka, dengan cara seperti ini, BFS menjamin ditemukannya solusi apabila solusinya memang ada. 

Depth-first search (DFS) adalah proses searching sistematis buta yang melakukan ekpansi sebuah path (jalur) menuju penyelesaian masalah sebelum melakukan ekplorasi terhadap path yang lain. Proses searching mengikuti sebuah path tunggal sampai menemukan goal atau dead end. Apabila proses searching menemukan dead-end, DFS akan melakukan penelusuran balik ke node terakhir untuk melihat apakah node tersebut memiliki path cabang yang belum dieksplorasi. Apabila cabang ditemukan, DFS akan melakukan cabang tersebut. Apabila sudah tidak ada lagi cabang yang dapat dieksplorasi, DFS akan kembali ke node parent dan melakukan proses searching terhadap cabang yang belum dieksplorasi dari node parent sampai menemukan penyelesaian masalah.

Pencarian dilakukan pada satu node dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam, solusi belum ditemukan, maka pencarian dilanjutkan pada node sebelah kanan. Node yang kiri dapat dihapus dari memori. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi. Jika solusi ditemukan maka tidak diperlukan proses backtracking (penelusuran balik untuk mendapatkan jalur yang dinginkan).

Berdasarkan gambar , proses pencarian dilakukan dengan mengunjungi cabang terlebih dahulu hingga tiba di simpul terakhir. Jika tujuan yang diinginkan belum tercapai maka pencarian dilanjutkan ke cabang sebelumnya, turun ke bawah jika memang masih ada cabangnya. Begitu seterusnya hingga diperoleh tujuan (goal). Operasi semacam ini dikenal dengan sebutan backtracking.

Heuristic search adalah suatu istilah yang berasal dari bahasa Yunani yang berarti menemukan/menyingkap. Heuristik adalah suatu perbuatan yang membantu kita menemukan jalan dalam pohon pelacakan yang menuntut kita kepada suatu solusi masalah. Heuristik dapat diartikan juga sebagai suatu kaidah yang merupakan metoda/prosedur yang didasarkan kepada pengalaman dan praktek, syarat, trik atau bantuan lainnya yang membantu mempersempit dan memfokuskan proses pelacakan kepada suatu tujuan tertentu.

George Poyla (dalam Kristanto. A, 2003) mendefinisikan heuristik sebagai ”studi tentang sebuah metode dan aturan discovery serta invention” dalam pencarian state space, heuristik didefinisikan sebagai aturan untuk memilih cabang-cabang dalam ruang keadaan yang paling tepat untuk mencapai solusi permasalahan yang dapat diterima .

Metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak kebelakang menuju pada suatu keadaan awal. Algoritma: 

Bangkitkan suatu kemungkinan solusi (membangkitkan suatu tititk tertentu atau lintasan tertentu dari keadaan awal). 

Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node terebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan. 

Jika solusi ditemukan, keluar. Jika  tidak, ulangi kembali langkah pertama.

 “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: 

Metode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin. 

Contoh: TSP dengan Simple Hill Climbing 

Disini ruang keadaan berisi semua kemungkinan lintasan yang mungkin. Operator digunakan untuk menukar posisi kota-kota yang bersebelahan. Apabila ada n kota, dan kita ingin mencari kombinasi l intasan dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan sebanyak: 

sebanyak 6 kombinasi (lihat gambar dibawah). Fungsi heuristic yang digunakan adalah panjang lintasan yang terjadi