ARTIFICIAL INTELLIGENCE: PENCARIAN,METODE BFS-DFS

KONSEP PENCARIAN

Pencarian merupakan suatu proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space). Ruang keadaan sendiri yaitu suatu ruang yang berisi semua keadaan yang mungkin.

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

1. Completeness : Apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada?
2. Time complexity : Berapa lama waktu yang diperlukan? 
3. Space complexity : Berapa banyak memori yang diperlukan?
4. Optimality : Apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda?

TEKNIK PENCARIAN

Teknik searching pada AI dibagi menjadi 2 yaitu :

1. Pencarian buta (blind search). Blind searching adalah model pencarian buta atau pencarian yang tidak memiliki informasi awal. Ada beberapa algoritma pencarian buta diantaranya BFS (Breadth First Search), DFS (Depth First Search), dan UCS (Uniform Cost Search). 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
2. Pencarian terbimbing (heuristic search). Heuristic searching merupakan metode pencarian yang memperhatikan nilai heuristik (nilai perkiraan). Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness). Jenis-jenis heuristic searching :
• Generate and Test
• Hill Climbing
• Best First Search
• Alpha Beta Prunning
• Means-End-Analysis
• Constraint Satisfaction

KARAKTERISTIK MASALAH

Pencarian heuristic adalah metode yang sangat umum yang dapat diterapkan dalam begitu banyak masalah, meliputi begitu banyak variasi teknik yang spesifik, dimana masing-masing efektif untuk penyelesaian masalah tertentu yang lebih spesifik. Untuk memilih metode mana (atau kombinasi metode mana) yang akan digunakan untuk menyelesaikan masalah, penting untuk menganalisa masalah pada beberapa dimensi kunci atau karakteristik, sebagai berikut :

• Dapatkah masalah disederhanakan kedalam kelompok terpisah yang lebih kecil atau subprogram yang lebih mudah ?
• Dapatkah satu tahap penyelesaian solusi diabaikan atau setidaknya tidak dilakukan jika terbukti tidak layak ?
• Apakah ruang lingkup masalah dapat diprediksi ?
• Dapatkah dinyatakan sebuah solusi yang baik untuk penyelesaian masalah tanpa membandingkannya dengan solusi lain yang mungkin ?
• Solusi yang diinginkan adalah sebuah stata atau jalur menuju stata ?
• Apakah sejumlah pengatahuan mutlak diperlukan untuk menyelesaikan masalah atau pengetahuan hanya diperlukan untuk membatasi pencarian ?
• Dapatkah komputer yang diberikan permasalahan langsung memberikan solusi atau pemecahan masalah memerlukan interaksi antara komputer dan manusia ?

TEKNIK SEARCH

• Arah search Dapat dilakukan : Maju, bermula dari keadaan awal (start state) Mundur, diawali dari keadaan tujuan (goal state)
• Topologi proses search Ada dua macam penggambaran problem, yaitu dalam bentuk : 
1. Pohon (tree)
2. Graf (graph) : Graf berarah dan Graf tidak berarah

METODE BREADTH-FIRST-SEARCH

Algoritma Breadth-First-Search :

1. Bentuk variabel dengan nama NODE-LIST dan jadikan sebagai initial state.
2. Sampai goal state ditemukan atau NODE-LIST kosong, lakukan : 
• Ambil elemen pertama dari NODE-LIST, sebut E. jika NODE-LIST kosong, quit.
• Untuk tiap cara dimana tiap aturan(fungsi) dapat cocok dengan stata di E, lakukan : 
• Gunakan aturan(fungsi) untuk menuju stata baru
• Jika stata baru adalah goal state, quit return stata ini 
• Jika bukan, tambahkan stata baru di akhir NODE-LIST.

METODE DEPTH-FIRST-SEARCH

Algoritma Depth-Fisrt-Search : 

1. Jika initial state adalah goal state, quit dan return success 
2. Jika bukan, lakukan dibawah ini sampai dicapai sinyal success atau gagal
• Tentukan successor, E dari initial state. Jika tidak ada lagi successor, maka sinyal gagal
• Jalankan Depth-Fisrt-Search dengan E sebagai initial state
• Jika success dihasilkan, sinyal success. Jika tidak maka ulangi langkah