Jak konsekwencja oznacza, że ​​heurystyka jest również dopuszczalna?

Funkcja heurystyczna to ...$h (n)$

• Spójne, jeśli szacowany koszt od węzła do celu nie jest większy niż koszt kroku do jego następcy plus szacowany koszt od następcy do celu.$n$$n'$
• Dopuszczalne, jeżeli nigdy nie przecenia rzeczywistych kosztów do stanu docelowego.$h(n)$

Podręcznik mojego kursu sztucznej inteligencji stwierdza, że ​​spójność jest silniejsza niż dopuszczalność, ale tego nie udowadnia i mam problem z wymyśleniem matematycznego wyjaśnienia.

Aby potwierdzić twierdzenie zawarte w pytaniu, pozwól nam udowodnić, że spójność oznacza dopuszczalność, podczas gdy odwrotnie nie jest to prawda. To uczyniłoby spójność silniejszym warunkiem niż ten drugi.

Spójność oznacza dopuszczalność:

Zacznę od podkreślenia, że jeśli funkcja heurystyczna jest dopuszczalna (gdzie jest celem), ponieważ zakłada się, że koszty brzegowe są nieujemne, a zatem optymalny koszt z jednego węzła do siebie koniecznie wynosi 0 Jest tak z pewnością w przypadku, gdy funkcja heurystyczna jest dopuszczalna, ale chcemy udowodnić, że spójność koniecznie oznacza dopuszczalność . W tym celu przyjmijmy dalej, że dla dowolnego celu --- i fakt ten zostanie wykorzystany w poniższym przypadku podstawowym.$h(t)=0$$h$$t$$h(t)=0$

Dowód przechodzi przez indukcję:

Przypadek podstawowy : weź dowolnego poprzednika węzła celu . Niech oznacza to, aby było następcą . Jeśli funkcja heurystyczna jest spójna , to i stąd zachowuje się w tym przypadku dopuszczalnie .$t$$n$$t$$n$$h(n)\leq c(n,t) + h(t)=c(n,t) + 0 =c(n,t)$$h$

Zauważ, że przypadek podstawowy nie zakłada, że ​​krawędź jest koniecznie optymalnym rozwiązaniem od do i rzeczywiście może istnieć inna ścieżka od do przy niższym koszcie. Ważnością przypadku podstawowego jest to, że dla wszystkich przodków węzła ! Ten wynik zostanie ponownie wykorzystany na etapie indukcji.$\langle n, t\rangle$$n$$t$$n$$t$$h(n)\leq c(n,t)$$t$

Etap indukcyjny : rozważ węzeł . Optymalny koszt osiągnięcia celu od , , jest obliczany jako: , gdzie jest zbiorem następców węzła . Ponieważ hipoteza zakłada spójność , wówczas . Ponadto, ponieważ jest przyjmowany przez etap indukcji, to i jest to prawdą dla wszystkie następcy węzła . Innymi słowy:$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)$ , więc .$h(n)\leq h^*(n)$

Dopuszczalność niekoniecznie oznacza konsekwencję:

Do tego wystarczy prosty przykład. Rozważmy wykres składający się z pojedynczej ścieżki z 10 węzłami: , gdzie celem jest . Załóżmy wlog, że wszystkie koszty brzegowe są równe 1. Oczywiście , i zróbmy , i . Oczywiście funkcja heurystyczna jest dopuszczalna :$\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. Wreszcie .$h(n_0)=8\leq h^*(n_0)=9$

Jednak nie jest spójne, a .$h(n)$$h(n_0)=8 > c(n_0, n_1)+h(n_1)=1+1=2$

Mam nadzieję że to pomoże,