Por que a heurística de pesquisa A * é ideal, mesmo que subestime os custos?

Uma pesquisa * encontra a solução ideal para os problemas, desde que a heurística seja admissível, o que significa que nunca superestima o custo do caminho a partir de qualquer nó (e consistente, mas vamos nos concentrar em ser admissível no momento).

Mas por que ele sempre encontra a solução ideal se a heurística subestima? Por exemplo, se subestima um caminho não ideal em mais do que subestima o caminho ideal, isso não equivale a superestimar?

A * mantém uma fila prioritária de opções que está considerando, ordenada pelo quão boas elas podem ser. Ele continua pesquisando até encontrar uma rota para a meta tão boa que nenhuma das outras opções possa torná-la melhor. A qualidade de uma alternativa pode ser baseada na heurística e nos custos reais encontrados na pesquisa até agora.

Se a heurística subestimar, as outras opções parecerão melhores do que realmente são. A * acha que essas outras opções podem melhorar a rota e, portanto, faz o check-out. Se a heurística subestimar apenas um pouco, talvez algumas dessas rotas se mostrem úteis. Por outro lado, se a heurística superestimar, A * pode pensar que as alternativas à rota já são todas terríveis, por isso não se dará ao trabalho de olhar para elas. Mas a heurística superestima para que eles possam ser muito melhores do que parecem.

Por exemplo, suponha que você esteja tentando dirigir de Chicago para Nova York e sua heurística seja o que seus amigos pensam sobre geografia. Se seu primeiro amigo disser "Hey, Boston está perto de Nova York" (subestimando), você perderá tempo procurando rotas através de Boston. Em pouco tempo, você perceberá que qualquer rota sensata de Chicago a Boston já se aproxima bastante de Nova York antes de chegar a Boston e que, na verdade, via Boston apenas acrescenta mais quilômetros. Então, você parará de considerar rotas por Boston e seguirá em frente para encontrar a rota ideal. Seu amigo subestimado lhe custou um pouco de tempo de planejamento, mas, no final, você encontrou o caminho certo.

Suponha que outro amigo diga: "Indiana fica a um milhão de milhas de Nova York!" Em nenhum outro lugar do mundo fica a mais de 21.000 quilômetros de Nova York, portanto, se você seguir o conselho de um amigo literalmente, nem sequer considerará nenhuma rota por Indiana. Isso faz com que você dirija quase o dobro do tempo e cobre 50% a mais de distância . Opa

É verdade que, se subestimar um caminho não ideal em mais do que subestima o caminho ideal, ele explorará esses caminhos antes de explorar o caminho ideal. O que é importante, e é isso que a admissibilidade garante, é que, enquanto estiver explorando os caminhos não ideais, não encontrará o objetivo e concluirá a pesquisa antes de explorar o caminho ideal. Isso ocorre porque, ao seguir esses caminhos não ideais, mesmo que pareçam ótimos no início, o custo / comprimento deles começará a aumentar e, em algum momento, o algoritmo retornará para explorar o caminho ideal. Se pudéssemos superestimar o custo da meta e o seguirmos no caminho ideal, poderíamos realmente seguir o caminho não ideal e encontrar a meta (que finaliza a pesquisa,

A diferença importante entre A * e a pesquisa Best-First é que A * combina o valor fornecido pela função de estimativa com o comprimento do caminho (o menor atualmente conhecido) para o nó em consideração.$e$

Suponha que seu caminho ideal para a meta tenha comprimento ; então a estimativa para o seu estado inicial é no máximo , e para o ésimo nó no caminho ideal, a estimativa é no máximo . Isso fornece um limite para o quão longe o algoritmo seguirá qualquer caminho espúrio ; assim que você executar mais de etapas ao longo de , o prefixo atualmente explorado do caminho ideal ficará melhor e será abandonado.$k$$k$$i$$k-i$$p$$k$$p$$p$

Essencialmente, a pesquisa A * fica entre a Largura Primeiro (desinformada, garantida para encontrar o caminho mais curto, mas lento) e a Melhor Primeira (guiada por uma função de estimativa, potencialmente rápida, mas muito dependente da qualidade das estimativas).