32
diterimanya. Seringkali kita ingin terikat relaksasi ini, sehingga kami dapat
menjamin bahwa jalan solusi tidak lebih buruk daripada (1 + e) kali jalan
solusi optimal. Ini jaminan baru ini disebut sebagai e -diterima.
Ada sejumlah e algoritma diterima:
Tertimbang A*. Jika h
(n)
adalah fungsi heuristik diterima,
dalam versi tertimbang dari A* pencarian satu menggunakan h
w (n)
= e
h
(n)
, e> 1 sebagai fungsi heuristik, dan melakukan pencarian A * seperti
biasa (yang akhirnya terjadi lebih cepat daripada menggunakan h
a
sejak
kurang node diperluas). Jalan maka ditemukan oleh algoritma pencarian dapat
memiliki biaya paling e kali dari jalur biaya termurah dalam grafik.
Static Bobot menggunakan biaya fungsi f (n) = g (n) + (1 + e)
h (n) .
Dinamis Bobot menggunakan biaya fungsi f (n) = g (n) + (1 +
e w (n)) h (n) , di mana
, dan di
mana d(n) adalah kedalaman pencarian dan N adalah panjang diantisipasi dari
jalur solusi.
Sampel Pembobotan Dinamis menggunakan sampling node
untuk estimasi yang lebih baik dan debias kesalahan heuristik.
.
menggunakan dua fungsi heuristik. Yang pertama adalah
daftar FOCAL, yang digunakan untuk memilih node calon, dan yang
kedua h
F
digunakan untuk memilih node yang paling menjanjikan dari daftar
FOCAL.
 |