2.2 Peng. Teknologi Sistem Cerdas

 2. Teknik pencarian Hill Climbing

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.

Fungsi heuristic adalah hanya masalah jarak antara lokasi anda berada dengan letak gedung tertinggi dan bagaimana menemukan jarak yang terdekat atau cara tercepat menuju gedung tertinggi.

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.

 

Algoritma Simple Hill Climbing :

1. Evaluasi initial state. Jika ini goal state maka return dan keluar. Jika bukan maka lanjutkan dengan initial state sebagai current state.

2. Ulangi langkah berikut sampai menemukan solusi atau sampai tidak ada lagi operator yang dapat digunakan pada current state

                                          a. Pilih operator yang belum digunakan pada current state dan

                                             gunakan untuk menghasilkan/menuju stata baru

                                          b. Evaluasi stata baru.

                                                i.   Jika ini goal state maka return dan keluar

                                                ii.  Jika bukan goal state tetapi lebih baik dari current state

                                                    maka jadikan stata baru sebagai current state

                                                iii. Jika tidak lebih baik dari current state lanjutkan

                                                    perulangan

2.1 Peng. Teknologi Sistem Cerdas

 1. Teknik Pencarian Generate and taste

Teknik Generate-and-Test adalah teknik yang paling mudah dibandingkan 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.                3.  Jika solusi sudah ditemukan, quit. Jika belum kembali ke langkah 1.

Kebaikan dan Keburukan Generate-and-Test :

Jika penurunan solusi yang mungkin dilakukan secara sistematis, maka procedure diatas akan dapat menemukan solusi suatu saat, jika memang ada. Tapi sayangnya jika ruang permasalahan sangat luas maka saat ditemukannya solusi akan menjadi sangat lama.

Cara terbaik menerapkan generate-and-test yang sistematis adalah pada tree dari depth-first search dengan backtracking, yaitu kembali ke stata sebelumnya bila ditemui stata yg sudah pernah di test atau memodifikasi prosedurnya untuk menelusuri stata pada bentuk graph.

1.2 Tugas Peng. Teknologi Sistem Cerdas

 2. BFS ( Breadth First Seacrh)

Breadth First Seacrh adalah serupa denga DFS yaitu algoritma untuk mencari atau mengunjungi node dalam sebuah tree atau graph. BFS dimulai dari root sebuah tree dan mencari node per level sampai memuaskan yang dicari atau semua node terkunjungi.

Aplikasi yang menggunakan BFS :

1. Menemukan kompenen yang terhubung dalam graph

2. Mencari shortest path dalam yang unweight graph 

3. Metode ford-fulkerson untuk menghitung maximum flow 

Simulasi Tree :

1.1 Peng. Teknologi Sistem Cerdas

 1. DFS ( Depth First Search) 

Depth First Search adalah algoritma untuk mencari atau mengunjungi node yang dalam sebuah tree atau graph. Pencarian dimula dari root sebuah tree dan dilanjutkan sejauh mungkin ke node child sebelum back traking.

Aplikasi yang menggunakan DFS :

1. Pencarian Articulation dan Bridge dalam Graph

2. Pencarian kompenen yang berhubungan 

2. Topological Sorting

DFS dapat diimplementasikan dengan recursive function atau iterasi menggunakan stack. 

simulasi menggunakan stack pada DFS :