A * 검색은 동일한 노드를 두 번 이상 확장합니까?

A * 검색은 Arad, Sibiu 및 기타 반복 된 상태의 f 값을 다시 계산하는 것처럼 보입니다.이 노드는 이미 확장되어 닫혀진 상태이므로 수행하면 안됩니다. 그래서 나는 무엇을 여기에서 놓치고 있냐? 러셀과 노르 빅에서 (이미지 - 인공 지능A * 검색은 동일한 노드를 두 번 이상 확장합니까?

는 이미지

:., 그게 무슨 자신의 F-값이 최적의 경로보다 더 때문에이 경우

는,이 노드가 확장되지 않습니다 아닙니다 인 경우 예 : 가장 가까운 f 값이 선행 노드로 되돌아 간다면 A *는 그렇게할까요?

출처

2017-03-19 Kirtiman

노드와 그 전임자 사이의 거리가 음수 인 경우에만 발생할 수 있습니다. – beaker

하지만 이미지에서 보는 바와 같이 사실이 아닙니다. – Kirtiman

교과서는 보이지 않는지 여부에 관계없이 모든 연결 노드를 맹목적으로 트리에 추가 한 것처럼 보입니다. 노드가 반복되는 경로가 결코 최단 경로가 될 수 없으므로 (약간 낭비 임에도 불구하고) 괜찮습니다 (음수가 아닌 거리라고 가정). 계속 점검 될 것이지만 결코 최단 거리가 될 수는 없습니다. – beaker

대부분의 A * 알고리즘은 역 추적을합니다. 그렇지 않으면 노드를 한 번만 방문 할 수 있습니다. 백 포인터가 손상되어 경로를 복구 할 수 없지만, 우선 순위 대기열의 하위 노드가 대각선 이동 ar 일 경우 저렴한 비용으로 방문한 노드에 액세스 할 수있는 상황이 발생할 수 있습니다. 정사각형 움직임보다 비싸다. 보통 당신은 그것을 무시하고 방문한 노드를 이해할 수없는 것으로 취급합니다. 이상하고 멋진 경험적 방법을 사용하거나 아주 이상한 그래프를 사용하지 않는 한, 경로 길이에 거의 차이를 만들지 않습니다.

출처

2017-03-19 20:29:04

아라드의 발견 적 사고 방식은 초기에 변경되지 않았습니다. 그러나 f 값이 있습니다. – Kirtiman

A * 검색은 동일한 노드를 두 번 이상 확장합니까?

답변

관련 문제