SEARCH LANJUTAN

SEARCH LANJUTAN

1. Masalah dan ruang masalah 

Untuk membuat system untuk menyelesaikan masalah terpisah, kita harus melakukan 4 hal sbb : 

1. Mendefinisikan masalah dengan tepat, meliputi definisi yg tepat tentang keadaan awal dan keadaan akhir sebagai solusi yang dapat diterima. 

2. Analisa masalah, beberapa fitur penting akan menentukan kelayakan dari beberapa teknik yang mungkin untuk menyelesaikan masalah. 

3. Membatasi dan menghadirkan pengetahuan yang diperlukan untuk menyelesaikan masalah 

4. Pilih teknik penyelesaian terbaik dan aplikasikan pada masalah.

2. Cara Merepresentasikan masalah 

Untuk membuat deskripsi formal dari permasalahan, harus dilakukan beberapa hal, diantaranya : 

1. Definisikan ruang stata yang memuat semua konfigurasi yg mungkin dari objek yang terkait (dan mungkin  beberapa yg tidak mungkin). Hal ini, tentu saja mungkin  untuk mendefiniskan ruang stata dengan jumlah stata  yang tidak terbatas. 

2. Tentukan satu atau beberapa stata yang menyatakan keadaan awal dari masalah, disebut initial states. 

3. Tentukan satu atau beberapa stata yang dapat diterima sebagai keadaan akhir (solusi), disebut goal states.

3. Konsep Pencarian

Beberapa metode/konsep search yang akan dipelajari :

1. Breadth-First-Search

2. Depth-Fisrt-Search

3. Generate-and-Test

4. Hill-Climbing

5. Best-First-Search 

Pencarian buta (1,2), pencarian heuristic (3,4,5)

4. Metode Pencarian Heuristik 

Teknik pencarian heuristik (heuristic searching) merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan (state space) suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan di sepanjang jalur yang memiliki kemungkinan sukses paling besar, dan mengesampingkan usaha yang bodohdan memboroskan waktu.

a. Generate And Test (Pembangkit dan Pengujian) 

Teknik Generate-and-Test adalah teknik yang paling mudah di bandingkan teknik search yang lain, namun relatif lebih lama dalam mendapatkan solusi.

Algoritma Generate-and-Test :

1. Bentuk solusi yang mungkin. Untuk beberapa masalah, ini berarti membentuk poin terpisah dari area permasalahan. Pada masalah lain, ini berarti membentuk jalur dari stata awal. 

2. Lakukan test untuk melihat apakah poin yang ditemui adalah solusi dengan membandingkan poin yang dipilih atau poin terakhir dari jalur yang dipilih dengan kumpulan stata tujuan 

3. Jika solusi sudah ditemukan, quit. Jika belum kembali ke langkah 1.

b. Hill Climbing (Pendakian Bukit) 

Teknik Hill Climbing adalah pengembangan dari teknik Generate-and-Test, dengan penambahan adanya umpan balik dari prosedur test yang sudah digunakan untuk membantu memilih arah mana yang harus ditelusuri pada setiap area search. Pada prosedur Generate-and-Test yang murni, fungsi test hanya ditanggapi dengan Ya atau Tidak. Tetapi pada Hill￾Climbing fungsi test ditambahkan dengan fungsi heuristic atau fungsi objectif yang memungkinkan perkiraan seberapa dekat simpul yang ditelusuri terhadap goal state.

Hill-climbing sering kali digunakan jika fungsi heuristic yang baik tersedia untuk mengevaluasi stata, tapi ketika tidak ada lagi pengetahuan yang dapat digunakan. Sebagai contoh, anda berada disuatu kota yang belum pernah anda kunjungi tanpa memiliki peta. Tujuannya menuju gedung tertinggi yang terlihat dari tempat anda berada.

 Penyelesaian masalah diatas dimulai dengan meninjau karakteristik masalah, apakah solusi yang pertama ditemukan dapat diterima sebagai solusi yang baik ? (mutlak atau relatif ?) Karena tidak ada peta dan tidak ada pengalaman memilih jalan (tidak ada pengetahuan) maka dipilih saja jalan yang arahnya menuju solusi sampai kita tiba di tujuan tanpa mengulangi atau mencoba lagi jalur yang lain dan kita terima itu sebagai solusi terbaik (dgn mengabaikan kemungkinan lain). Jadi adalah masuk akal menerapkan hill-climbing ketika tidak ada alternatif yang dapat diterima untuk memilih atau menuju pada suatu stata.

c. Best-First-Search 

Teknik Best-First-Search adalah teknik search yang menggabungkan kebaikan yang ada dari teknik Depth-First-Search dan Breadth-First-Search. 

Tujuan menggabungkan dua teknik search ini adalah untuk menelusuri satu jalur saja pada satu saat, tapi dapat berpindah ketika jalur lain terlihat lebih menjanjikan dari jalur yang sedang ditelusuri. Untuk mendapatkan jalur yang menjanjikan adalah dengan memberikan skala prioritas pada setiap stata saat dihasilkan dengan fungsi heuristic.

Untuk menggunakan Best-First-Search, kita memerlukan dua daftar simpul, yaitu : 

1. OPEN

berisi simpul yang dihasilkan dari fungsi heuristic tapi belum dievaluasi, memilki antrian prioritas dimana elemen dengan prioritas tertinggi adalah yang memiliki nilai paling baik yang dihasilkan fungsi heuristic. 

2. CLOSED

berisi simpul yang sudah dievaluasi. Kita perlu tetap menyimpan simpul-simpul ini dalam memori jika kita ingin melakukan search pada Graph, sehingga jika kita menemui suatu simpul kita bisa memeriksa apakah simpul ini sudah pernah dieavaluasi atau belum