A* 휴리스틱, 과대 평가/과소 평가?

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

문제

나는 과대 평가/과소 평가라는 용어에 대해 혼란스러워합니다. 나는* 알고리즘이 어떻게 작동하는지 완벽하게 얻지 만, 과대 평가하거나 과소 평가하는 휴리스틱이 있다는 효과는 확실하지 않습니다.

직접 Birdview-line의 제곱을 할 때 과대 평가입니까? 그리고 왜 알고리즘을 틀리지 않습니까? 모든 노드에 동일한 휴리스틱이 사용됩니다.

직접 Birdview-Line의 Squareoot를 취할 때 과소 평가됩니까? 그리고 왜 알고리즘이 여전히 정확합니까?

나는 그것을 멋지고 명확하게 설명하는 기사를 찾을 수 없으므로 여기 누군가가 좋은 설명을 가지고 있기를 바랍니다.

도움이 되었습니까?

해결책

휴리스틱의 견적이 실제 최종 경로 비용보다 높은 경우 과대 평가하고 있습니다. 당신은 그것이 낮을 때 과소 평가하고 있습니다 (당신은 과소 평가할 필요가없고 과대 평가할 필요가 없습니다. 옳은 추정치는 괜찮습니다). 그래프의 모서리 비용이 모두 1이면, 당신이 제공하는 예제는 과대 평가 및 과소 평가를 제공하지만, 평범한 좌표 거리도 직교 공간에서 복숭아로 작동합니다.

과대 평가는 알고리즘을 "잘못된"것으로 만들지 않습니다. 의미는 더 이상 허용되는 휴리스틱, 이는 최적의 행동을 생성하도록 보장되는 조건입니다. 허용되지 않는 휴리스틱을 사용하면 알고리즘은 무시 해야하는 경로를 검사하고 그를 탐색하기 때문에 차선책 경로를 찾는 데 수많은 불필요한 작업을 수행 할 수 있습니다. 실제로 발생하는지 여부는 문제 공간에 따라 다릅니다. 경로 비용이 추정 비용으로 '공동 외'이기 때문에 발생하며, 이는 본질적으로 다른 경로가 다른 경로보다 더 나은 경로에 대한 아이디어를 혼란스럽게합니다.

당신이 그것을 찾을 것인지 확실하지 않지만 당신은 Wikipedia a* 기사. Google에 거의 불가능하기 때문에 주로 언급하고 링크합니다.

다른 팁

로부터 Wikipedia a* 기사, 알고리즘 설명의 관련 부분은 다음과 같습니다.

골 노드가 더 낮을 때까지 알고리즘이 계속됩니다. 에프 큐의 어떤 노드보다 값 (또는 대기열이 비어있을 때까지).

핵심 아이디어는 과소 평가를 통해 A*는 경로의 총 비용이 목표에 대한 알려진 경로의 비용을 초과한다는 것을 알게되면 목표에 대한 잠재적 경로를 탐색하는 것을 중단한다는 것입니다. 경로 비용의 추정치는 항상 경로의 실제 비용보다 적거나 동일하기 때문에, 예상 비용이 알려진 경로의 총 비용을 초과하자마자 경로를 버릴 수 있습니다.

과대 평가를 통해 A*는 실제 비용이 낮지 만 현재 목표에 가장 잘 알려진 경로보다 높은 경로가있을 수 있기 때문에 잠재적 경로 탐색을 중단 할 수있는시기를 알지 못합니다.

내가 아는 한, 당신은 일반적으로 가장 짧은 경로를 찾을 수 있도록 일반적으로 과소 평가하기를 원합니다. 과대 평가하여 더 빨리 답변을 찾을 수 있지만 가장 짧은 경로는 찾을 수 없습니다. 따라서 과대 평가가 "잘못된"이유는 왜 과소 평가는 여전히 최상의 솔루션을 제공 할 수 있습니다.

Birdview 라인에 대한 통찰력을 제공 할 수 없어서 죄송합니다 ...

짧은 대답

@chaos 답변은 약간 오해의 소지가있는 IMO입니다 (강조해야 함)

과대 평가는 알고리즘을 "잘못된"것으로 만들지 않습니다. 의미는 더 이상 허용되는 휴리스틱을 가지고 있지 않다는 것입니다. 이는 최적의 행동을 보장 할 조건입니다. 허용되지 않는 휴리스틱, 알고리즘 ~할 수 있다 불필요한 일을 많이합니다

@albertopl이 암시 될 때

과대 평가하여 더 빨리 답변을 찾을 수 있지만 가장 짧은 경로는 찾을 수 없습니다.

결국 (수학적 최적 외에) 최적의 솔루션은 컴퓨팅 리소스, 런타임, 특수 유형의 "맵"/상태 공간 등을 고려하는지 여부에 따라 크게 좌우됩니다.

긴 대답

예를 들어, 초기에 시작하는 시간 이점이 가장 짧은 경로를 가져 와서이 솔루션을 컴퓨팅하기 위해 더 오래 기다리는 시간 이점보다 더 크기 때문에 과대 평가 휴리스틱을 사용하여 로봇이 대상에 더 빨리 얻는 실시간 응용 프로그램을 생각할 수 있습니다.

더 나은 인상을주기 위해, 나는 파이썬으로 빠르게 만든 모범적 인 결과를 공유합니다. 결과는 동일한 a* 알고리즘에서 비롯되며 휴리스틱 만 다릅니다. 각 노드 (그리드 셀)는 벽을 제외한 8 개의 이웃 모두에게 가장자리를 갖습니다. 대각선 가장자리 비용 SQRT (2) = 1.41

첫 번째 그림은 간단한 예제 케이스에 대한 알고리즘의 반환 된 경로를 보여줍니다. 과대 평가 휴리스틱 (빨간색 및 청록색)의 차선 경로를 볼 수 있습니다. 반면에 여러 가지 최적의 경로 (파란색, 노란색, 녹색)가 있으며 먼저 발견되는 휴리스틱에 따라 다릅니다.

다른 이미지는 대상에 도달 할 때 모든 확장 된 노드를 보여줍니다. 색상은이 노드를 사용하여 추정 경로 비용을 보여줍니다 (처음 부터이 노드로의 "이미 채취 된"경로를 고려하십시오. 수학적으로 그것은 지금까지 비용 과이 노드의 휴리스틱입니다). 언제든지 알고리즘은 총 비용이 가장 낮은 상태로 노드를 확장합니다 (이전 설명).

Paths

1. 0 (푸른)

  • dijkstra 알고리즘에 해당합니다
  • 노드 확장 : 2685
  • 경로 길이 : 89.669

Zero

2. 까마귀가 날아갈 때 (노란색)

3. 이상 (초록)

  • 장애물이없는 가장 짧은 경로 (8 방향을 따르는 경우)
  • 과대 평가하지 않고 가능한 가장 높은 추정치 (따라서 "이상")
  • 노드 확장 : 854
  • 경로 길이 : 89.669
  • https://i.stack.imgur.com/vqmtf.png

4. 맨해튼 (빨간색)

  • 장애물이없는 가장 짧은 경로 (대각선으로 움직이지 않으면; 다시 말하면 : "대각선 이동"의 비용은 2로 추정됩니다)
  • 과대 평가
  • 노드 확장 : 562
  • 경로 길이 : 92.840
  • https://i.stack.imgur.com/gd9t4.png

5. 까마귀가 날아갈 때 10 번 (시안)

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top