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

12

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.

user58348
fonte

Respostas:

11

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)=0hth(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.tntnh(n)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.n,tntnth(n)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ênciantnh(n)minmSCS(n){c(n,m)+h(m)}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)c(n,n)+h(n)h(n)h(n)h(n)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 ) .nnh(n)minmSCS(n){c(n,m)+h(m)}=h(n)h(n)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 ) =n0,n1,n2,...,n9n9h(n0)=9h(n0)=8 e h ( n 9 ) = 0 . Claramente, a função heurística éadmissível:h(ni)=1,1i<9h(n9)=0

  1. h(t)=0
  2. ,i , 1 i < 9 .h(ni)=1h(ni)=(9i)i,1i<9
  3. Finalmente, .h(n0)=8h(n0)=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(n0)=8>c(n0,n1)+h(n1)=1+1=2

Espero que isto ajude,

Carlos Linares López
fonte