Kecerdasan Buatan : PERTEMUAN VIII, IX, X, XI CII2M3_ADF06 | Heuristic Search

 Assalamualaikum Warahmatullahi Wabarakatuh...

Artificial Intelligent (AI)

·      PERTEMUAN VIII, IX, X, XI

CII2M3_ADF06 | Heuristic Search

 

Ø Heuristic (informed) Search

Heuristic (hyu-RIS-tik) adalah suatu proses mengira-ngira untuk mendapatkan informasi, pengetahuan atau target. Heuristic bisa dikontraskan terhadap suatu algoritma yang deterministic. Fungsi heuristic yang bagus jika dia bisa  sedekat mungkin dengan nilai asli tapi tidak melebihi.

 

Ø Hill Climbing (HC)

HC Algotihm  : dimana kita di suatu inisial state dan jika algoritmanya benar maka selsai, jika belum maka akan diulangi sampai state benar.

Ø Steepest-Ascent Climbing

Bahwa dari satu posisi membangkitkan semua state lalu dibandingkan mana yang harus dipilih untuk dijadikan current state, kemudian baru algoritmanya dijalankan.

Ø  Simulated  Annealing

Annealing dimana dia memasukkan ide atau suatu konsep untuk menghindari terjadinya terjebak di optimum local di hill climbing. Intinya simulasi aneling menambahkan probability unntuk keluar dari local minimum.

Ø Best-First Search

Bisa dikatakan sebagai paying kelompok algoritma dimana ada kelompok algoritma best-first, implementasi algoritma  yang paling dasar adalah Gredy BFS dan yang paling umum A*.

Best-First Search Algorithm :

ü  Terdapat2 queue  yaitu Open dan Close

ü  Pilih algoritma dari node didalam open lalu ambil yang terkecil dan masukkan kedalam close, apabaila benar maka searching selesai.

ü  Memilih Open berdasarkan fumgsi F(n)

ü  Node memiliki nilai.

Implementasinya :

Ø Greedy Best-First Search

ü Dimana F nya adalah heuristic

ü Penilaian node berdasarkan nilai heuristic tetapi tidak optimal.

 

Ø A* Search

ü  A* Search  adalah F(n) atau nilai asli dari node tersebut.

ü  Dengan menggunakan g(n) dan h(n) algoritmanya menjadi kompliit dan optimal.

A* Search Performance      :

ü  Complete

ü  Optimal (tidak ada algoritma yang menggunakan heuristic jika algoritma tersebut mengunakan heuristc yang sama  kemudia tidak ada algoritma yang bisa mendapatkan solusi lebih baik daripada A*).

ü  Time Complexity = 0  (b^d)

ü  Space Complexity = 0  (b^d)

ü  More Of A*

ü  Interative Deepening A*

ü  Simple Memory-Bounded A*

ü  Bi-Directional A*

ü  Modified Bi-Directional A*

ü  Dynamic Weighted A*

ü  Beam A*