A distância de Manhattan é monotônica quando usada como função heurística?

25

Eu tenho um mapa quadrado. Somente movimentos horizontais e verticais são permitidos (sem diagonais). O custo do movimento é sempre 1.

Estou implementando um algoritmo A * nesse mapa, usando a distância de Manhattan como uma heurística de distância. Essa heurística é consistente? Posso evitar a verificação g(node)nos nós que estão no conjunto FECHADO?

Edit: Por consistente eu quero dizer monotônico.

tiles path-finding geometry Emiliano
fonte
11
Se o seu custo de movimento é uniforme em cada telha, você poderia substituir A * com Ir Ponto Pesquisa
Nick Caplinger
Ei, isso é legal!
Emiliano

Respostas:

10

Para realmente responder à sua pergunta: a distância do manhatten é consistente quando você é obrigado a se deslocar vertical / horizontalmente ao longo de uma grade não ponderada (isso pode ser facilmente mostrado pela definição na wikipedia) . Portanto, sim, no seu caso, você pode evitar verificar novamente os nós no conjunto fechado.

No entanto, depois de permitir o movimento diagonal ou de qualquer ângulo, a distância de manhatten torna-se inadmissível porque superestima os custos diagonais, o que significa necessariamente que não é consistente.

BlueRaja - Danny Pflughoeft
fonte
Sim, esse é exatamente o tipo de resposta que eu estava procurando. Seria bom saber o que acontece se a função heurística for h(x) = min(manhattan(p1), manhattan(p2))(ou seja, p1 ou p2 são um bom ponto final e eu quero chegar ao mais próximo). Isso h(x)ainda é monotônico?
Emiliano
11
@happy_emi: Sim, se h(x, p1)e h(x, p2)são consistentes, min(h(x,p1), h(x,p2))também será consistente. Isso é fácil de mostrar a partir da definição na wikipedia (precisaríamos mostrar isso min(h(x, p1), h(x, p2)) <= distance(x,y) + min(h(y, p1), h(y, p2))para todos os nós xe ycom uma borda entre eles. Agora suponha que h(x, p1)seja o mínimo; você pode mostrar que é definitivamente <=o lado direito, usando o fato de que as duas heurísticas são consistentes?)
BlueRaja - Danny Pflughoeft 6/06
31

Sim, a distância de Manhattan entre dois pontos é sempre a mesma, assim como a distância regular entre eles. Você pode pensar na distância de Manhattan como sendo os componentes X e Y de uma linha que corre entre os dois pontos.

Esta imagem ( da Wikipedia ) ilustra bem isso:

Distâncias de Manhattan

A linha verde é a distância real.

As linhas azul , vermelha e amarela representam a mesma distância de Manhattan (12 unidades). Não importa qual combinação de movimentos para cima e para a direita você desenhe do ponto inferior esquerdo para o canto inferior direito, você terá a mesma distância total de Manhattan.

MichaelHouse
fonte
2
Ótima resposta: curta, doce, objetiva e com uma foto bonita.
Tom 'Blue' Piddock
11
Esta resposta está próxima, mas incorreta. Esta imagem não mostra que a distância de Manhattan é consistente (na verdade, se você considerar a linha verde como a distância, ela não é consistente!) , E o raciocínio de que ele não precisa verificar novamente os nós porque "a distância de Manhattan entre dois pontos é sempre o mesmo " não se aplica (a afirmação também é verdadeira h(x) = 1000, o que obviamente não é consistente) . Ele pode evitar verificar novamente os nós, mas apenas porque a distância de Manhatten é consistente, o que esta resposta não mostra.
BlueRaja - Danny Pflughoeft
2
Acredito que, pela definição que você vinculou, a distância de Manhattan é consistente. A distância da linha verde usaria uma heurística diferente. As linhas vermelha, azul e amarela mostram que a distância entre os dois nós permanece a mesma (ao usar a mesma heurística). Aproximar-se reduz a heurística e se afastar aumenta a heurística. Isso atende aos requisitos monotônicos do OP. À medida que o gráfico é construído, com um nó em cada "interseção", a distância de Manhattan é consistente. Se fosse um cenário diferente (como permitir movimento diagonal), a heurística seria ruim.
MichaelHouse
2
Eu já disse que a distância de Manhatten é consistente, mas não pelos motivos mencionados. Sua resposta não mostra consistência, nem seu argumento nos comentários. "Heurística consistente / monótona" tem uma definição precisa (fornecida no meu link acima) , que não é o mesmo que uma função monotônica que você parece estar confundindo. Declarar "aproximar-se reduz a heurística e afastar-se aumenta a heurística" não é suficiente para mostrar que é consistente, por exemplo. 2*manhattensatisfaz isso, mas não é consistente.
BlueRaja - Danny Pflughoeft
3
Não sei por que você diz que está incorreto , parece estar insistindo que esta resposta está incompleta . A prova em sua resposta parece ser igualmente fraca: "a distância do manhatten é consistente ...", você reitera as especificações originais da pergunta, seguindo como seria admissível se o cenário fosse diferente . Não achei que a resposta justificasse uma prova matemática completa. Se você acha que essa pergunta exige isso, inclua-a na sua resposta e votarei em seguida. Obrigado pela crítica construtiva.
MichaelHouse
6

Como extensão da resposta de Byte56, gostaria de salientar que, em seu conjunto de dados específico, usar a Distância de Manhattan como sua função heurística será sempre uma heurística perfeita, no sentido em que sempre retornará o custo real do caminho (supondo que exista nada "bloqueando" os caminhos).

Você também deve observar que todos os nós na direção correta (horizontal ou verticalmente) produzirão a mesma distância esperada (porque existem muitos caminhos igualmente curtos para a meta). Você deve estar ciente de que sua fila de prioridades (conjunto aberto) deve, em caso de prioridades vinculadas, remover da fila o nó adicionado mais recente primeiro (LIFO - Último a entrar, primeiro a sair). Ao fazer isso, você examinará apenas os nós que terminarão no caminho ideal . Se você examinar nós igualmente adequados da maneira FIFO (primeiro a entrar, primeiro a sair), estará examinando efetivamente todos os nós que fazem parte do melhor caminho. Esse problema surge porque existem vários caminhos igualmente bons para o nó da meta.

Thorkil Holm-Jacobsen
fonte
"(assumindo que não há nada bloqueando o caminho)" - essa é uma suposição bastante grande. Se não há nada bloqueando o caminho, não há necessidade de um algoritmo para encontrar o caminho!
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPflughoeft: Isso é verdade, foi apenas um pensamento aparecendo ao olhar para a imagem do Byte56. O resto é verdade, no entanto.
Thorkil Holm-Jacobsen
4

Não tenho certeza do que você quer dizer com "sempre" consistente. A distância de Manhattan em uma grade fixa é independente do caminho percorrido? Sim, como a resposta do Byte56 disse.

No entanto, por exemplo, a distância de Manhattan não é invariável em rotações. Por exemplo, a distância de Manhattan ( norma L1 ) entre a origem e um ponto (10,10)é |10-0| + |10-0| = 20. No entanto, se você girar suas coordenadas em 45 graus (agora o seu ponto fixo fica ao longo de uma das direções da grade), agora você encontrará o mesmo ponto agora (10sqrt(2),0), então há uma distância de Manhattan até a origem de 10sqrt(2)~14.14.

dr jimbob
fonte
+1 por apontar isso; OTOH, a distância de Manhattan é invariável em rotações de 90 graus, que são realmente as únicas que podem ser feitas 'consistentemente' em uma grade discreta.
Steven Stadnicki
11
Boa captura, embora ele tenha mencionado que apenas movimentos horizontais e verticais são permitidos.
Thorkil Holm-Jacobsen
11
A pergunta original era consistente como em monotônica.
Emiliano