Heuristic Search Kecerdasan Buatan

 

Nama                    : Malik Bayu Aji
Nim                      : 19.01.013.007
Mata Kuliah         : Kecerdasan Buatan 
Dosen Pengampu : Herfandi, A.Md., S.Kom., M.Kom.

HEURISTIC SEARCH (video 1)

Kata Heuristic berasal dari dari srbuah kata kerja bahsa Yunani (hyu-RIS-tik) Heuriskein yang berarti mencari atau menemukan.Heuristic juga dapat diartikan  jarak atau nilai yang menyatakan seberapa dekat suatu state ke goal.

·         Heuristic Function

fungsi heuristic dapat diterima jika perkiraan biaya yang dihasilkan tidak melebihi biaya sebenarnya.

Fungsi heuristic yang terlalu  tinggi dapat memebuat proses pencarian menjadi hilang atau mencapai hasil yang tidak optimal.

Semakin mendekati biaya sebenrnya, semakin baik fungsi heuristiknya.

Adapun jenis-jenis Heuristic Search :

·         Hill Climbing

Dalam Hill Climbing, fungsi uji dikombinasikan dengan fungsi heuristic yang menyediakan pengukuran kedekatan suatu keadaan yang diberi dengan tujuan (goal).

·         HC Algorithm

Mengevaluasi keadaan awal jika itu adalah  keadaan  tujuan, berhenti jika keadaan saat ini adalah keadaan awal

Ulangi sampai keadaan saat ini adalah keadaan tujuan atau tidak ada operator baru yang tersedia:

Pilih operator baru untuk status ini dan buat status baru.

Evaluasi status baru.

Jika heuristicnya mendekati tujuan maka jadikan itu sebagai keadaan saat ini.

Jika heuristinya tidak mendekati tujuan maka bisa diabaikan.

·         Steepest-Ascent Hill Climbing

Dalam pendakian bukit sederhana, simpul terdekat pertama dipilih, sedangkan

Di bukit pendakian yang paling curam, semua penerus dibandingkan dan yang paling dekat dengan solusi di pilih.

Ini menunjukkan bahwa ia memiliki elemen algoritma pertama yang luas.

·         Simulated Annealing (SA)

SA menggunakan formula probabilitas yang memungkinkan untuk mengeluarkan minimum local

SA menggunakan formula probabilitas yang biasa disebut dengan konsep coba-coba.

Status baru yang tidak lebih baik dari status saat ini masih dapat dipilih dengan probabilitas.

Best-first search

Best-first search menggunakan fungsi evaluasi f (n) untuk setiap node

f (n) memberikan perkiraan untuk total biaya

Perluas simpul n dengan f(n) terkecil

Biasanya diimplementasikan menggunakan priority queue (antrian prioritas).

·         Best-First Search Algorithm

OPEN : berisi node-node yang sudah dibangkitkan, sudah memiliki fungsi  heuristic  namun belum diuji.Umumnya berupa antrian berprioritas yang berisi  elemen-elemen dengan nilai heuristic tertinggi.

CLOSED : berisis node-node yang sudah diuji.

·         Greedy best-first search

            Pencarian Terbaik Pertama yang paling sederhana Hanya memperhitungkan perkiraan biaya sedangkan biaya sebenarnya tidak dimasukkan ke dalam akun f(n) = h(n). Penilaian nodenya ditentukan berdasarkan heuristiknya yang lengkap  namun tidak optimal. Kompleksitas ruang = 0(bm) sedangkan kompleksitas waktu = 0(bm).

·         A* Search

Menggabungkan Uniform Cost Search dan Greedy Best-First Search.Hindari  memperluas jalur yang sudah mahal. Fungsi tersebut dihitung dari biaya aktual dan perkiraan biaya f(n) = g(n) + h(n).Performance A* Search yaitu lengkap dan optimal.