Teknik Searching

mengingat materi searching ini keluar pasa quiz di kampus :) jadi saya rasa sangat penting untuk membahas teknik searching pada AI.

searching adalah salah satu metode penyelesaian masalah dengan teknik penencarian solusi pada permasalahan tersebut.

teknik search terbagi 2
1. blind searching

2. heuristic searching

pada atikel kali ini akan dibahas keduanya

1. BLIND SEARCHING

merupakan pencarian buta, pencarian ini tidak memiliki informasi awal.

ciri2 Blind Search
- Membangkitkan simpul berdasarkan urutan
- Kalau ada solusi, solusi akan ditemukan
- hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui)

Blid search di bagi menjadi 3
1. BFS (Breadth-first Search)atau sering disebut juga pencarian melebar
contoh

pada BFS teknik pencarian pesoalannya adalah dengan membuka node (titik) per levelnya.. sehingga pada persoalan diatas penyelesaian pada BFS adalah.

jadi urutan node yang di lalui pada pencarian BFS adalah. a,b,c,d,e,f,g,h

2. DFS (Depth-first Search)atau sering disebut juga pencarian mendalam
sesuai namanya pencarian mendalam, DFS tidak mencari solusi per level, namun mencari pada kedalaman sebelah kiri terlebih dahulu. masih menggunakan permasalahan di awal, pada DFS akan di dapatkan solusi seperti ini.

jadi solusi node yang di lalui pada DFS adalah a,b,e,h
dfs memiliki beberapa keuntungan,yaitu memori yang di gunakan tidak terlalu banyak karena tidak membuka semua node.

3. UCS (Uniform cost search) perpaduan antara BFS dan DFS
pada UCS, pencarian nya mempehatikan cost/jarak antara 1 node ke node lain.
contoh nya.

pada permasalahan diatas telah ditentukan jarak antara node. maka pada ucs akan membuka node yang memiliki nilai/cost antar node yang terendah.
pada gambar diatas jika kita buka
c = 10
b = 20
a = 10

karena nilai c dan a sama maka teserah mau buka yang mana lebih dahulu.
seandainya kita mebuka c maka kita teruskan pencariannya, jika kita buka
d = 10+5 =15
e = 10+40 = 50 (mencapai goal, namun nilai cost nya dirasa masih terlalu besar)

maka kita buka node d, lalu akan didapat
e = 10+5+30 = 45 (nilai pada pencarian ini pun terasa masih terlau besar) maka dari itu kita buka node yang kecil di awal tadi yaitu node a

setelah kita buka node a akan di dapat
e = 10 + 20 = 30 (di dapatkan goal dengan solusi terbaik)

dari kasus diatas dapat kita lihat, ada banyak cara unuk mendapatkan solusi. namun dari berbagai macam penyelesaian kasus, kita dapat mencari solusi yang paling optimal dan ini lah ke unggulan dari UCS


2. HEURISTIC SEARCHING
heuristic search merupakan metode pencarian yang memperhatikan nilai heuristik(nilai perkiraan).

heuristic memperkirakan jarak ke Goal (yang disebut dengan fungis heuristik)

salah satu contoh huristi search adalah Best First Search yang di bagi 2
1. Greddy Best
2. A* (baca A star)

kedua teknik ini memiliki persamaan dan perbedaan, persamaannya adalah sama-sama menggunakan nilai heuristic (perkiraan) perbedaannya akan dijelaskan di bawah ini

dalam heuristic search sangat di perhatikan nilai f(n) Fungsi Evaluasi yang menyataka seberapa bagus sebuah node.

heuristic function h(n) : fungsi yang menyataakan estimasi cost dari n ke goal state.

pada greddy best f(n) = h(n) dimana (* h(n) fungsi heuristik itu sendiri)
pada A* f(n) = h(n) + g(n) dimana (*g(n) merupakan aktual cost atau total jarak menuju ke n node)

contoh kasus pada teknik A*
Peta Rumania Problem

contoh kasus pada teknik Greddy Best
8 puzzle problem