Como a consistência implica que uma heurística também é admissível?

Uma função heurística $h (n)$ é ...

• Consistente se o custo estimado do nó $n$ à meta não for maior que o custo da etapa para o seu sucessor $n'$ mais o custo estimado do sucessor à meta.
• Admissível se $h(n)$ nunca superestimar o custo real para o estado da meta.

O livro do meu curso de Inteligência Artificial afirma que a consistência é mais forte que a admissibilidade, mas não prova isso, e estou tendo problemas para encontrar uma explicação matemática.

Para comprovar a afirmação em sua pergunta, demonstremos que consistência implica admissibilidade, enquanto o contrário não é necessariamente verdadeiro. Isso tornaria a consistência uma condição mais forte que a última.

Consistência implica admissibilidade:

Deixe-me começar enfatizando que se a função heurística h é admissível (onde t é uma meta), pois os custos de borda são considerados não negativos e, portanto, o custo ideal de um nó para si é necessariamente 0 Isso certamente se aplica caso a função heurística seja admissível, mas queremos provar que a consistência necessariamente implica admissibilidade . Para isso, suponhamos ainda que h ( t ) = 0 para qualquer objetivo - e esse fato será usado no caso base abaixo.$h(t)=0$$h$$t$$h(t)=0$

A prova prossegue por indução:

Caso base : adote qualquer antecessor do nó de objetivo . Seja n o denotado, para que t seja um sucessor de n . Se a função heurística é consistente , então h ( n ) ≤ c ( n , t ) + h ( t ) = c ( n , t ) + 0 = c ( n , t ) e, portanto, h se comporta de maneira admissível nesse caso.$t$$n$$t$$n$$h(n)\leq c(n,t) + h(t)=c(n,t) + 0 =c(n,t)$$h$

Note-se que o caso de base não assume que a borda é necessariamente a solução óptima do n de t e, na verdade, pode haver um caminho diferente do n de t com um custo mais baixo. A importância do caso base é que h ( n ) ≤ c ( n , t ) para todos os ancestrais do nó t ! Este resultado será reutilizado na etapa de indução.$\langle n, t\rangle$$n$$t$$n$$t$$h(n)\leq c(n,t)$$t$

Etapa de indução : considere um nó . O custo ideal para atingir a meta t de n , h ∗ ( n ) é calculado como: min m ∈ S C S ( n ) { c ( n , m ) + h ∗ ( m ) } , onde S C S ( n ) é o conjunto de sucessores do nó n . Como consistência$n$$t$$n$$h^*(n)$$\min_{m\in\mathrm{SCS(n)}}\{c(n,m)+h^*(m)\}$$\mathrm{SCS}(n)$$n$é assumido por hipótese, então . Além disso, como h ( n ′ ) ≤ h ∗ ( n ′ ) é assumido pelo passo de indução, então h ( n ) ≤ c ( n , n ′ ) + h ∗ ( n ′$h(n)\leq c(n,n')+h(n')$$h(n')\leq h^*(n')$$h(n)\leq c(n,n')+h^*(n')$ e isso é verdade para todos os sucessores do nó n . Em outras palavras: h ( n ) ≤ min m ∈ S C S ( n ) { c ( n , m ) + h ∗ ( m ) } = h ∗ ( n ) , de modo que h ( n ) ≤ h ∗ ( n ) .$n'$$n$$h(n)\leq \min_{m\in\mathrm{SCS(n)}}\{c(n,m)+h^*(m)\} = h^*(n)$$h(n)\leq h^*(n)$

A admissibilidade não implica necessariamente consistência:

Para isso, basta um exemplo simples. Considere-se um gráfico que consiste de um único caminho com 10 nós: , onde o objectivo é n 9 . Vamos supor WLOG que todos os custos de ponta são iguais a 1. Obviamente h * ( n 0 ) = 9 , e façamos h ( n 0 ) = 8 , h ( n i ) $\langle n_0, n_1, n_2, ..., n_9\rangle$$n_9$$h^*(n_0)=9$$h(n_0)=8$ e h ( n 9 ) = 0 . Claramente, a função heurística éadmissível:$h(n_i)=1, 1\leq i<9$$h(n_9)=0$

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

No entanto, não é consistente e h ( n 0 ) = 8 > c ( n 0 , n 1 ) + h ( n 1 ) = 1 + 1 = 2 .$h(n)$$h(n_0)=8 > c(n_0, n_1)+h(n_1)=1+1=2$

Espero que isto ajude,