Nama: BILIT ALATAS

 

Nama: BILIT ALATAS    

Kelas: INF A 2018 
NIM: 18.01.013.031

Pemateri: Anditya Arifianto
Materi: Heuristic search 

Pencarian
 buta tidak selalu dapat diterapkan dengan baik, hal ini disebabkan waktu aksesnya yang cukup lama serta besarnya memori yang dibutuhkan. Kelemahan ini dapat diatasi jika ada informasi tambahan (fungsi heuristik) dari domain yang bersangkutan.

Heuristik 
adalahsuatu proses yang mungkin dapat menyelesaikan suatu masalah tetapi tidak ada jaminan bahwa solusi yang dicari selalu dapat ditemukan. Fungsi Heuristik adalah fungsi yang melakukan pemetaan (mapping) dari diskripsi keadaan masalah (problema) kepengukur kebutuhan, umumnya direpresentasikan berupa angka.
 AI menggunakan heuristik dalam 2 situasi dasar :

1.       Persoalan/problema yang mungkin memiliki solusi eksak, namun biaya perhitungan untuk menemukan solusi tersebut sangat tinggi dalam kebanyakan persoalan (seperti catur), ruang keadaan bertambah secara luar biasa seiring dengan jumlah

2.       Persoalan yang mungkin tidak memiliki solusi eksak karena ambiquitas (ketidakpastian) mendasar dalam pernyataan persoalan atau data yang tersedia, diagnose medis merupakan salah satu contohnya.

·         Heuristik hanyalah sebuah cara menerka langkah berikutnya yang harus diambil dalam memecahkan suatu persoalan berdasarkan informasi yang ada/tersedia.

·         Heuristic Search

1.      Iterative Deepening A* (IDA*)

2.      Simlified Memory-Bounded A* (SMA*)

3.      Bi-directional A* (BDA*)

4.      Modified Bi-directional A* (MBDA*)

5.      Dynamic Weighting A* (DWA*)

6.      Beam A* (BA*)

·         Hill climbing (HC)

1.      Simple Hill Climbing

2.      Steepest = Ascent Hill Climbing

·         Simulated Anneling

Simulated Annealing   merupakan metode pencarian random untuk mengoptimalkan metode pencarian heuristic yang berpotensi menimbulkan hasil yang kurang optimal akibat adanya permasalahan optimum local. Secara sederhana, analogi Simulated Annealing adalah metode Hill Climbing yang dilengkapi dengan fitur inisialisasi ulang ditempat random. Meskipun dikatakan random, terdapat parameter tertentu didalam pemilihan tempat pada metode SA.

·         Best-First Search

  Metode ini merupakan kombinasi dari metode depth first search dan breadth-first search. Pada metode best-first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node pada level yang lebih tinggi ternyata memiliki nilai heuristic yang lebih buruk.

Fungsi Heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal state, yang dinyatakan dengan : 

f’(n) = g(n) + h’(n)

f’ = Fungsi evaluasi

g = cost dari initial state ke current state

h’ = prakiraan cost dari current state ke goal state

·         A*Search

Metode ini dirancang untuk memperbaiki kelemahan metode Greedy dengan cara menghindari ekspansi terhadap rute yang sudah tergolong mahal.

Fungsi evaluasi f(n) = g(n) + h(n)

Dimana g(n) adalah biaya yang sudah dikeluarkan hingga suatu node, dan h(n) adalah estimasi biaya yang perlu dikeluarkan dari suatu node hingga node tujuan.  Dengan katalain, A* menghitung total biaya yang sudah dikeluarkan ditambah estimasi biaya yang perlu dikeluarkan. A* melakukan ekspansi terhadap node dengan f(n) paling rendah.

Sekian dan Terima kasih.