Fungsi Heuristik dengan Dynamic Weighting

Pencarian A* (A-star) dikenal dengan kelengkapan dan keoptimalan-nya. Untuk setiap langkah, kita hanya memperluas simpul dalam perbatasan dengan nilai tertinggi dari f(n).

Definisi
Sebuah Fungsi Heuristik h2 dikatakan mendapat informasi lebih daripada h1 jika keduanya diterima dan h2 lebih dekat ke biaya yang optimal. Untuk kasus MAP, kemungkinan dari tugas yang optimal Popt < h2 < h1.

Teorema
If h2 lebih banyak informasi daripada h1 maka A2* mendominasi A1* (Nilsson).[Pearl,1985]

Kekuatan dari Fungsi Heuristik adalah mengukur dengan sejumlah pemangkasan terinduksi oleh h(n) dan bergantung pada akurasi dari estimasi ini. Jika h(n) mengestimasi biaya lengkap secara tepat (h(n) = Popt), maka A* akan memperluas simpul-simpul pada jalur yang optimal. Dengan kata lain, if tidak semua heuristik digunakan (pada kasus MAP sejumlah pada h(n) = 1), maka sebuah Pencarian Uniform-Cost terjadi kemudian, yang mana jauh lebih tidak efisien. Jadi sangat kritis untuk kita mencari sebuah keterimaan dan keeratan h(n) untuk mendapat solusi yang akurat dan efisien.

Dynamic Weighting
Sejak ikatan keeratan Greedy-Guess rendah pada kemungkinan MAP yang optimal, hal itu sangat mungkin untuk kompensasi pada galat (error) antara Greedy-Guess dan kemungkinan optimalnya. Kita bisa menerima hal ini dengan menambahkan sebuah berat pada Greedy-Guess seperti produk mereka sebanding atau lebih tinggi daripada kemungkinan optimal untuk masing-masing simpul dalam pada pencarian pohon dalam asumsi berikut:

 

dimana e adalah berat minimum yang bisa dijamin fungsi heuristik untuk diterima. gambar 1 menunjukkan bahwa jika kita menjaga e tetap konstan, pengabaian perubahan dari akurasi estimasi dengan meningkatnya variabel MAP, estimasi fungsi dan kemungkinan optimal bisa direpresentasikan oleh kurva Constant Weighting Heuristic. Jelasnya, Kasus dengan cara ini lebih sedikit informasi saat proses pencarian, sebagaimana ada beberapa variabel MAP untuk diestimasikan.

Dynamic Weighting [Pohl, 1973] adalah sebuah alat efisien untuk meningkatkan efisiensi dari pencarian A*. Jika diterapkan dengan benar, maka hal itu akan menjaga fungsi heuristik diterima selama keeratan yang tersisa pada kemungkinan optimal. untuk MAP, lapisan dangkal pada pencarian pohon, kita mendapat lebih variabel MAP daripada  lapisan dalam. Maka, Greedy mengestimasikan akan lebih seperti menyimpang dari kemungkinan optimal. Kita mengusulkan Fungsi Heuristik Dynamic Weighting berikut untuk layer ke-x pada Pencarian pohon dari variabel Map ke-n :

Bukan menjaga berat tetap konstan lewat pencarian, kita secara dinamis mengubahnya, jadi akan membuat berat itu ringan saat pencarian semakin mendalam. pada langkah terakhir dari pencarian (x = n -1), berat akan menjadi nol, ssejak Greedy Guess hanya untuk satu variabel MAP yang eksak dan biaya fungsi f(n-1) sebanding pada kemungkinan penugasan. Gambar 1 menunjukkan sebuah perbandingan empiris dari Greedy Guess, konstan dan Heuristik Dynamic Weighting terhadap akurasi kemungkinan estimasi. Kita lihat bahwa heuristik Dynamic Weighting leih banyak mendapat informasi daripada Constant Weighting.

Sumber:
Xiahou Sun, Marek J. Druzdzel, Changhe Yuan
DynamicWeighting A* Search-based MAP Algorithm for Bayesian Networks

========================= \\ // =========================