Uma heurística *, superestimação / subestimação?

StackOverflow https://stackoverflow.com/questions/1012691

Pergunta

Estou confuso sobre os termos superestimação / subestimação. I perfeitamente entendo como A * algoritmo funciona, mas estou inseguro dos efeitos de ter uma heurística que superestimativa ou subestimativa.

É superestimação quando você tirar o quadrado da-line birdview direta? E por que faria o algoritmo incorreta? A mesma heurística é usada para todos os nós.

É subestimação quando você toma o squareroot da-line birdview direta? E porque é que o algoritmo ainda correto?

Não consigo encontrar um artigo que explica-lo agradável e limpar isso espero que alguém aqui tem uma boa descrição.

Foi útil?

Solução

Você está superestimando quando a estimativa do heurística é maior do que o custo do caminho final efectivo. Você está subestimando quando é menor (você não tem que subestimado, você só tem que não superestimativa; correta estimativas são muito bem). Se os custos da borda do seu gráfico são todos 1, então os exemplos que você dá daria superestimativa e subestima, embora a planície coordenar distância também funciona peachy em um espaço cartesiano.

superestimando não exatamente fazer o algoritmo "incorreta"; o que significa é que você já não tem um admissível heurística , que é uma condição para A * a ser garantido para produzir um comportamento ideal. Com uma heurística inadmissível, o algoritmo pode acabar fazendo toneladas de caminhos examinando trabalho supérflua que deve ser ignorando e, possivelmente, encontrar caminhos abaixo do ideal por causa de explorar esses. Se isso realmente ocorre depende do seu problema de espaço. Isso acontece porque o custo do caminho é 'fora do comum' com o custo estimado, o que dá essencialmente o algoritmo confuso idéias sobre quais caminhos são melhores do que outros.

Eu não tenho certeza se você vai tê-lo encontrado, mas você pode querer olhar para o Wikipedia Um artigo *. Menciono (e link) principalmente porque é quase impossível Google para ele.

Outras dicas

A partir da Wikipedia A * artigo , a parte relevante da descrição do algoritmo é:

O algoritmo continua até que um nó objectivo tem um menor f valor do que qualquer nó na fila (ou até que a fila está vazia).

A idéia fundamental é que, com understimation, A * só vai parar de explorar um caminho potencial para a meta, uma vez que sabe que o custo total do caminho irá exceder o custo de um caminho conhecido para o gol. Desde a estimativa do custo do caminho é sempre menor ou igual ao custo real do caminho, A * pode descartar um caminho tão logo o custo estimado excede o custo total de um caminho conhecido.

Com superestimação, A * não tem idéia de quando ele pode parar de explorar um caminho potencial como pode haver caminhos com menor custo real, mas maior custo estimado do que o melhor caminho conhecido atualmente para o gol.

Tanto quanto eu sei, você quer geralmente subestimado de modo que você ainda pode encontrar o caminho mais curto. Você pode encontrar uma resposta mais rápida por superestimar, mas você não pode encontrar o caminho mais curto. Daí porque superestimação é "incorreto", enquanto subestimar ainda pode fornecer a melhor solução.

Eu sinto muito que eu não pode fornecer qualquer visão quanto à linhas Birdview ...

Resposta curta

@chaos resposta é pouco enganador imo (pode deve ser destacado)

superestimando não exatamente fazer o algoritmo "incorreta"; o que significa é que você não tem mais uma heurística admissível, que é uma condição para A * a ser garantido para produzir um comportamento ideal. Com uma heurística inadmissível, o algoritmo pode acabar fazendo toneladas de trabalho supérfluo

como @AlbertoPL está insinuando

Você pode encontrar uma resposta mais rápida por superestimar, mas você não pode encontrar o caminho mais curto.

No final (ao lado do ótimo matemático), a solução ideal depende fortemente se você considerar os recursos de computação, tempo de execução, tipos especiais de "Mapas" / Espaços estaduais, etc.

Resposta longa

Como exemplo, eu poderia pensar em uma aplicação em tempo real, onde um robô fica mais rápido ao destino usando uma heurística superestimação porque a vantagem de tempo, iniciando mais cedo é maior do que a vantagem tempo tomado o caminho mais curto, mas esperando mais tempo para calcular este solução.

Para lhe dar uma melhor impressão, compartilho alguns resultados exemplares que eu rapidamente criados com Python. Os resultados derivam do mesmo algoritmo A *, apenas os difere heurísticos. Cada nó (célula de grade) tem bordas para todos os oito vizinhos, exceto paredes. bordos diagonais sqrt custo (2) = 1.41

A primeira imagem mostra os caminhos retornados do algoritmo para um exemplo simples caso. Você pode ver alguns caminhos sub-óptimos de heurísticas superestimando (vermelho e ciano). Por outro lado, existem múltiplos caminhos ideais (azul, amarelo, verde) e que depende da heurística que um se encontra em primeiro lugar.

As diferentes imagens mostram nós todos expandida quando o alvo é atingido. A cor mostra o custo de caminho estimado usando este nó (considerando o caminho "já tomada" do início ao este nó, bem como, matematicamente é o custo até agora mais a heurística para esse nó). A qualquer momento o algoritmo expande o nó com o menor custo total estimado (descrito antes).

Caminhos

1. Zero (azul)

  • Corresponde ao algoritmo Dijkstra
  • nós expandidos: 2685
  • O comprimento do caminho: 89,669

Zero

2. Em linha recta (amarelo)

3. Ideal (verde)

  • caminho mais curto, sem obstáculos (se você seguir as oito direções)
  • estimativa mais elevada possível sem superestimar (daí o "ideal")
  • Nós expandido: 854
  • O comprimento do caminho: 89,669
  • https://i.stack.imgur.com/VqMtF.png

4. Manhattan (vermelho)

  • caminho mais curto, sem obstáculos (se você não se mover na diagonal, em outras palavras: custo de "movendo na diagonal" é estimado como 2)
  • superestima
  • Nós expandido: 562
  • O comprimento do caminho: 92,840
  • https://i.stack.imgur.com/gD9t4.png

5. Em linha recta vezes dez (ciano)

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top