Bagaimana konsistensi menyiratkan bahwa heuristik juga diterima?

Fungsi heuristik $h (n)$ adalah ...

• Konsisten jika perkiraan biaya dari node $n$ ke tujuannya adalah tidak lebih besar dari langkah biaya penggantinya $n'$ ditambah perkiraan biaya dari penerus tujuan.
• Diperbolehkan jika $h(n)$ tidak pernah melebih-lebihkan biaya sebenarnya untuk status tujuan.

Buku teks untuk kursus Kecerdasan Buatan saya menyatakan bahwa konsistensi lebih kuat dari pada dapat diterima tetapi tidak membuktikannya, dan saya mengalami masalah dengan penjelasan matematis.

Untuk membuktikan pernyataan dalam pertanyaan Anda, izinkan kami membuktikan bahwa konsistensi menyiratkan penerimaan sedangkan yang sebaliknya tidak selalu benar. Ini akan membuat konsistensi kondisi yang lebih kuat daripada yang terakhir.

Konsistensi menyiratkan penerimaan:

Mari saya mulai dengan menekankan bahwa jika fungsi heuristik h dapat diterima (di mana t adalah tujuan) karena biaya tepi diasumsikan non-negatif dan dengan demikian, biaya optimal dari satu node ke dirinya sendiri adalah 0 Ini tentu berlaku jika fungsi heuristik dapat diterima, tetapi kami ingin membuktikan bahwa konsistensi selalu berarti dapat diterima . Untuk ini, mari kita asumsikan lebih lanjut bahwa h ( t ) = 0 untuk tujuan apa pun --- dan fakta ini akan digunakan dalam kasus dasar di bawah ini.$h(t)=0$$h$$t$$h(t)=0$

Buktinya dihasilkan dengan induksi:

Basis kasus : mengambil pendahulu dari node tujuan . Biarkan n menyatakannya, sehingga t adalah penerus dari n . Jika fungsi heuristik konsisten , maka h ( n ) ≤ c ( n , t ) + h ( t ) = c ( n , t ) + 0 = c ( n , t ) dan karenanya, h berperilaku dapat diterima dalam kasus ini.$t$$n$$t$$n$$h(n)\leq c(n,t) + h(t)=c(n,t) + 0 =c(n,t)$$h$

$\langle n, t\rangle$$n$$t$$n$$t$$h(n)\leq c(n,t)$$t$

$n$$t$$n$$h^*(n)$$\min_{m\in\mathrm{SCS(n)}}\{c(n,m)+h^*(m)\}$$\mathrm{SCS}(n)$$n$$h(n)\leq c(n,n')+h(n')$$h(n')\leq h^*(n')$$h(n)\leq c(n,n')+h^*(n')$$n'$$n$$h(n)\leq \min_{m\in\mathrm{SCS(n)}}\{c(n,m)+h^*(m)\} = h^*(n)$ , sehingga .$h(n)\leq h^*(n)$

Penerimaan tidak selalu menyiratkan konsistensi:

Untuk ini, contoh sederhana sudah cukup. Pertimbangkan grafik yang terdiri dari jalur tunggal dengan 10 node: , di mana tujuannya adalah . Mari kita asumsikan wlog bahwa semua biaya tepi sama dengan 1. Jelas , dan mari kita buat , dan . Jelas, fungsi heuristik dapat ditambahkan :$\langle n_0, n_1, n_2, ..., n_9\rangle$$n_9$$h^*(n_0)=9$$h(n_0)=8$$h(n_i)=1, 1\leq i<9$$h(n_9)=0$

1. $h(t)=0$
2. $h(n_i)=1\leq h^*(n_i)=(9-i)$ , .$\forall i, 1\leq i<9$
3. Akhirnya, .$h(n_0)=8\leq h^*(n_0)=9$

Namun, tidak konsisten dan .h ( n 0 ) = 8 > c ( n 0 , n 1 ) + h ( n 1 ) = 1 + 1 = $h(n)$$h(n_0)=8 > c(n_0, n_1)+h(n_1)=1+1=2$

Semoga ini membantu,