과소 평가/과소 평가라는 용어에 대해 혼란 스럽습니다. 나는 A * 알고리즘이 어떻게 작동하는지 완벽하게 알 수있다. 그러나 과대 평가하거나 과소 평가하는 경험적 방법의 효과에 대해 확신 할 수 없다.A * 추론, 과대 평가/과소 평가?
당신은 직접 birdview 라인의 사각형을 때 과대 평가인가요? 왜 알고리즘을 잘못 만들었 을까요? 동일한 휴리스틱이 모든 노드에 사용됩니다.
직접적인 birdview-line의 squareroot를 가져 가면 과소 평가됩니까? 왜 알고리즘은 여전히 올바른가요?
내가 설명하는 기사를 찾을 수 없습니다. 여기에 누군가의 설명이 잘 나타나기를 바랍니다.
휴리스틱의 추정치는 실제 최종 경로 비용보다 높을 때 당신은 과대 평가하고 있습니다. 당신은 그것이 낮을 때 과소 평가하고 있습니다 (과소 평가할 필요가 없으며 과대 평가하지 말아야합니다.) 정확함 견적은 정확합니다. 그래프의 가장자리 비용이 모두 1이면 평범한 좌표 거리가 데카르트 공간에서 복숭아로 작동하지만 사용자가 제시 한 예는 과대 평가 및 과소 평가를 제공합니다.
과대 평가가 알고리즘을 "잘못"하게하지는 않습니다. 그것이 의미하는 바는 더 이상 허용 가능한 휴리스틱을 가지지 않아서 A *가 최적의 동작을 생성 할 수있는 조건입니다. 허용 할 수없는 발견 적 기법을 사용하면, 알고리즘은 무시해야하는 많은 경로를 검사하는 불필요한 작업을 수행 할 수 있으며,이를 탐색하기 때문에 차선 경로를 찾을 수도 있습니다. 실제로 발생하는지 여부는 문제 공간에 따라 다릅니다. 이것은 경로 비용이 추정 비용과 '합쳐져서'나온 것이므로 본질적으로 알고리즘이 어떤 경로가 다른 경로보다 낫다는 생각이 엉망이되기 때문에 발생합니다.
나는 당신이 그것을 발견 할 지 확신하지 않지만, Wikipedia A* article을보고 싶을 수도 있습니다. 나는 Google에 대해 거의 불가능하기 때문에 주로 (그리고 링크)를 언급합니다. Wikipedia A* article 가입일
내가 아는 한, 당신은 여전히 가장 짧은 경로를 찾을 수 있도록 일반적으로 과소 평가하고 싶습니다. 과대 평가하여 답을 빨리 찾을 수는 있지만 최단 경로를 찾지 못할 수도 있습니다. 따라서 과소 평가가 왜 "틀린"것인지, 과소 평가가 여전히 최상의 솔루션을 제공 할 수있는 이유는 무엇입니까?
나는 내가 birdview 라인으로 어떤 통찰력을 제공 할 수 없습니다 죄송합니다 ...
알고리즘 정보의 중요한 부분이다
목표 노드 큐에서 임의의 노드보다 낮은 F 값을 갖는다 (또는 대기열까지까지 알고리즘은 계속 비었다).
의 핵심 아이디어는 understimation로, A *는이 경로의 총 비용은 목표에 알려진 경로의 비용을 초과 할 것을 알고 한 번 목표에 잠재적 인 경로를 탐색 중지한다는 것입니다. 경로 비용의 추정치는 항상 경로의 실제 비용보다 작거나 같기 때문에 A *는 예상 비용이 알려진 경로의 총 비용을 초과하는 즉시 경로를 삭제할 수 있습니다.
과소 평가로 인해 A *는 실제 비용은 낮지 만 예상 비용은 목표에 가장 잘 알려진 경로보다 높을 수 있으므로 잠재 경로 탐색을 중단 할 수 있는지 알 수 없습니다.
이 위키 백과 항목에주의하십시오. 나는 지난 여름에 그 페이지가 매우 틀린 알고리즘을 발견하고 발견 한 뒤 1 주일이나 2 일 후에 다시 확인한 알고리즘을 발견했다. 위키 피 디아 (및 인터넷)의 모든 것과 마찬가지로, 답변이 아니라 다음을보기위한 가이드로 사용하십시오. –
포인트를 찍었지만 인용 한 부분이 정확하고 내 대답과 관련이 있습니다. – Eric
과대 평가하는 방법으로 알고리즘은 과소 평가하는 방법보다 더 빠르게 (차선책의) 솔루션을 찾는 경향이 있습니까? 극단적으로 과소 평가 방식 (항상 0을 반환하는 것처럼)을 사용하면 최적의 솔루션을 얻을 수 있지만 본질적으로 광범위한 검색을 수행합니다. – chtz