Heuristic (informed) search

 

Heuristic (informed) search

Secara garis besar terbagi menjadi:

• Heuristic Function

• Hill Climbing

• Simulated Annealing

• Best-First Search

• A* Search

 

• Heuristik

> Heuriskein

• Untuk menemukan, menemukan, mencari
• Proses memperoleh pengetahuan atau hasil yang diinginkan dengan tebakan cerdas daripada dengan mengikuti beberapa rumus yang telah ditetapkan sebelumnya.
• Fungsi yang memberikan nilai perkiraan (estimasi biaya) dari suatu solusi
• Heuristik dapat dibandingkan dengan algoritma

1. Fungsi Heuristik

> Fungsi heuristik dapat diterima jika perkiraan biaya yang dihasilkan tidak melebihi biaya sebenarnya

> Fungsi heuristik yang terlalu tinggi dapat membuat proses pencarian hilang atau mencapai hasil yang tidak optimal. 

> Fungsi heuristik yang baik adalah fungsi yang memberikan perkiraan biaya yang mendekati biaya sebenarnya. 

> Semakin mendekati biaya sebenarnya, semakin baik fungsi heuristiknya

2. Hill Climbing Algorithm

1. Evaluasi keadaan awal jika itu adalah keadaan tujuan berhenti jika keadaan saat ini adalah keadaan awal. 

2. Ulangi hingga status saat ini adalah status tujuan atau tidak ada operator baru yang tersedia:

- Pilih operator baru untuk status ini dan buat status baru. 

- Evaluasi keadaan baru

• jika lebih dekat ke keadaan tujuan daripada keadaan saat ini, jadikan keadaan saat ini
• jika tidak lebih baik, abaikan

Steepest-Ascent Hill Climbing

> Dalam simple hill climbing, simpul terdekat pertama dipilih, sedangkan

> Dalam steepest ascent hill climbing semua penerus dibandingkan dan solusi terdekat dipilih

> Ini menunjukkan bahwa ia memiliki elemen algoritma pertama lebar.

3. Simulated Annealing

> Sebuah variasi dalam mendaki bukit dan idenya adalah menyertakan survei umum tempat kejadian untuk menghindari mendaki bukit kaki palsu. 

> Nama dan inspirasi berasal dari anil dalam metalurgi, teknik yang melibatkan pemanasan dan pendinginan terkontrol dari suatu material untuk meningkatkan ukuran kristalnya dan mengurangi cacatnya

Simulated Annealing Algorithm

• Evaluasi keadaan awal jika merupakan keadaan tujuan keluar, jika tidak keadaan saat ini adalah keadaan awal
• Inisialisasi T dengan nilai yang besar.  (jadwal anil)
• Inisialisasi Best-So-Far dengan keadaan saat ini
• Ulangi sampai keadaan saat ini adalah tujuan atau tidak ada operator baru yang tersedia

-          Pilih operator baru untuk keadaan ini dan buat keadaan baru

-          Evaluasi biaya keadaan baru AE = f (keadaan baru) - f  (keadaan saat ini)

-          Jika keadaan baru adalah sasaran atau AE (x) <0, pertahankan keadaan baru sebagai keadaan saat ini dan Best-So-Far

-          Jika AE (x)  0, terima keadaan baru sebagai keadaan saat ini dengan probabilitas P = e^{-AE / T} 

-          Revisi T = T - AT menurut jadwal anil.

• Kembalikan Best-So-Far sebagai solusi.

4. Best-First Search

> gunakan fungsi evaluasi f (n) untuk setiap node

- f (n) memberikan perkiraan untuk total biaya. 

- Perluas simpul n dengan f terkecil (n). 

> biasanya diimplementasikan menggunakan antrian prioritas.

Best-First Search Algorithm

• Inisialisasi OPEN antrian dengan status awal (node), dan CLOSED set kosong.
• Ulangi sampai status saat ini adalah tujuan atau tidak ada status lagi dalam antrian OPEN.

-          Dapatkan node x terbaik dari OPEN

-          Jika x adalah tujuan, kembali

-          Jika tidak tambahkan x ke CLOSED

-          Hasilkan semua penerus untuk x, untuk semua penerusnya y:

§  Evaluasi y dari induk x

§  Jika penerus belum pernah dibuat,

§  dan tambahkan ke OPEN, maka simpan x sebagai induknya

§  Jika penggantinya sudah di OPEN tetapi dengan induk yang berbeda, 

§  Jika evaluasi dari x lebih baik, ubah induknya dan evaluasi ulang semua penerusnya

 

Greedy Best-First Search

> Pencarian Terbaik-Pertama yang paling sederhana

> Hanya memperhitungkan perkiraan biaya

> Biaya sebenarnya tidak diperhitungkan

f (n) = h (n)

> Lengkap, namun tidak Optimal

Greedy Best-First Search Performance

> Complete

> Not Optimal

> Time Complexity = 0 (bm)

> Space Complexity = 0 (bm)

5. A * Search

> Menggabungkan Uniform Cost Search dan Pencarian Terbaik-Pertama Serakah Greedy Best-First Search

- hindari memperluas jalur yang sudah mahal

> Fungsi dihitung dari biaya aktual dan perkiraan biaya

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

> Selesai dan  Optimal

A * Performa Pencarian

> Selesai

> Optimal

- Tidak ada algoritma dengan heuristik yang sama yang dijamin untuk memperluas node yang lebih sedikit

> Kompleksitas Waktu = 0 (b^d)

> Kompleksitas Ruang = 0 (b^d)

 

Pencarian Heuristik dengan Batas Memori

> Bagaimana kita bisa mengatasi masalah memori untuk pencarian A *? 

> Ide: Cobalah sesuatu seperti pencarian pertama yang mendalam, tetapi tidak melupakan segala sesuatu tentang cabang yang telah dieksplorasi sebagian. 

> Ingat nilai f terbaik yang diamati sejauh ini di cabang yang akan dihapus.

Iterative Deepening A *

> Tiap iterasi adalah pencarian yang mengutamakan kedalaman, sama seperti pendalaman iteratif biasa

> Setiap iterasi bukan iterasi A *:

jika tidak, masih 0 (b^m) memori

> Gunakan batas biaya (f), bukan batas kedalaman  seperti dalam pendalaman berulang biasa

Simplified Memory-bounded A *

> Menggunakan semua memori yang tersedia

> Ide dasar:

1. Lakukan A sampai Anda kehabisan memori
2. Buang node dengan biaya tertinggif cost

• Simpan F-cost di node leluhur
• Perluas node lagi jika semua node lain dalam memori lebih buruk

SMA * Performa Pencarian

> Selesai jika dapat menyimpan semua node yang nilai f-nya lebih kecil daripada tujuan di memori

> Menemukan solusi terbaik (dan mengenalinya), dalam kondisi yang sama.