Como uma heurística admissível garante uma solução ideal?

16

Ao usar A * (ou qualquer outro algoritmo de melhor localização de caminho), dizemos que a heurística usada deve ser admissível , ou seja, nunca deve superestimar o comprimento (ou os movimentos) reais do caminho da solução.

Como uma heurística admissível garante uma solução ideal? De preferência, estou procurando uma explicação intuitiva.

Se você quiser, pode explicar usando a heurística de distância de Manhattan do quebra-cabeça 8.

Ashwin
fonte
2
@ Ashwin Intuitivamente porque quando o algoritmo encontra um caminho de comprimento , ele já tentou todos os outros caminhos que possam ter comprimento máximo de k . É por isso que sua função heurística nunca deve superestimar o custo da meta. Tente você mesmo criando uma função heurística que pode superestimar. kk
GD

Respostas:

7

Enquanto a resposta de Anton é absolutamente perfeita, deixe-me tentar fornecer uma resposta alternativa: ser admissível significa que a heurística não superestima o esforço para atingir a meta, ou seja, para todos os n no espaço de estados (no quebra-cabeça 8, isso significa apenas para qualquer permutação dos ladrilhos e o objetivo que você está considerando no momento) em que h ( n ) é o custo ideal para atingir a meta.h(n)h(n)nh(n)

Eu acho que a resposta mais lógica para ver por que fornece soluções ideais se h ( n ) é admissível, porque ele classifica todos os nós no OPEN em ordem crescente de f ( n ) = g ( n ) + h ( n ) e, também , porque não para ao gerar a meta, mas ao expandi-la:Ah(n)f(n)=g(n)+h(n)

  1. Como os nós são expandidos em ordem crescente de você sabe que nenhum outro nó é mais promissor do que o atual. Lembre-se: h ( n ) é admissível, portanto, ter o menor f ( n ) significa que ele tem uma oportunidade de atingir a meta por um caminho mais barato que os outros nós no OPEN não têm. E isso é verdade, a menos que você possa provar o contrário, ou seja, expandindo o nó atual.f(n)h(n)f(n)
  2. Como pára apenas quando ele prossegue para expandir o nó de objetivo (em oposição a parar ao gerá-lo), você tem certeza (desde o primeiro ponto acima) que nenhum outro nó leva a um caminho mais barato para ele.A

E isso é, essencialmente, tudo o que você encontrará na prova original de Nilsson et al.

Espero que isto ajude,

Carlos Linares López
fonte
3
Obrigado. Ajudou. Você estava se referindo a alguma prova de Nilsson et al. Que é aquele? E onde posso encontrar a prova?
Ashwin
1
@ Ashwin Veja o livro " Principles of Artificial Intelligence " (na página 80), de Nils J. Nilsson (1982).
Nbro 24/02/19
11

Se a função heurística não for admissível, poderemos ter uma estimativa maior que o custo real do caminho de um nó para um nó de objetivo. Se essa estimativa de custo de caminho mais alto estiver no caminho de menor custo (que estamos procurando), o algoritmo não o explorará e poderá encontrar outro caminho (não de menor custo) para a meta.

Veja este exemplo simples.

insira a descrição da imagem aqui

AGh(N)NGNc(N,Xi)NXiNi=1..mmNN

Que as heurísticas sejam

  • h(B)=3

  • h(C)=4

H

h(C)=4>c(C,G)=2

UMAUMABGUMABG4UMACG3

Anton
fonte
1
Está bem. Mas como uma heurística admissível garante uma solução ideal?
Ashwin 14/10
Pode acontecer que - h (b) <h (c) com h (b) e h (c) sendo admissíveis, mas custo real (b)> custo real (c), certo? Então b será escolhido como o próximo caminho onde, na realidade, c daria o melhor caminho.
Ashwin 14/10
Para o primeiro comentário: a heurística admissível garante encontrar o caminho mais curto. A solução em si é ideal se a heurística for consistente .
Anton
Para o segundo comentário: se a heurística é admissível, A-> B pode ser escolhido para o próximo nó expandir, mas depois disso o A * escolherá A-> C e não A-> B-> G. E no final, terminará com A-> C-> G.
Anton
1
Porque A * funciona assim. Ele expande o nó com a menor soma de distância para aquele nó + estimativa heurística desse nó. d (A, G) + h (G) = 4 + 0 = 4 ed (A, C) + h (C) = 1 + algo <= 2 (porque é admissível). Portanto, C possui uma soma menor e o A * a escolhe. Do mesmo modo, ele expandirá G e encontrará o menor caminho.
Anton