A * 허용 성을 깨는 것은 기하 급수적 인 속도 향상을 가져 왔습니까?

Question

저는 타일에 숫자가없는 슬라이딩 타일 퍼즐의 일반화 된 버전에서 작업 해 왔습니다. 대신 각 위치에 타일 또는 구멍이 있으며 true 또는 false (부울 또는 구멍)로 부울 값으로 나타납니다.

검색의 요점은 n 개의 타일을 가진 초기 상태와 n 개의 목표 위치를 가진 목표 상태를 취하고 모든 목표 위치가 채워지도록 타일을 이동하는 방법을 찾기 위해 A *를 사용하는 것입니다.

Initial State: 
T F T F 
F F T F 
F F T T 

Goal State 
T T T T 
T F F F 
F F F F 

나는이 작업을 수행하기 위해 다른 추론에 일하고 있었다

가장 성공적인 이런 식으로 뭔가 갔다 논리했다 : 불행하게도

int heuristicVal = 0 

for every tile (i)... 
int closest = infinity 
for every goal location (j)... 
if (manhattan distance of ij < closest) closest = manhattan distance of ij 
end for 
heuristicVal += closest 
end for 

return heuristicVal 

을이, 다음은 4x3의 격자 아래 예입니다 두 개 이상의 타일이 동일한 대상 위치에 대한 휴리스틱으로 안내되는 상황에서 여전히 너무 느립니다. 타일 ​​수로 heuristicVal을 곱하려고 시도했는데 갑자기 지수가 올라갔습니다. 28 초 전의 문제는 1 초도 걸리지 않았습니다.

편집 :이 변경으로 인해 최적의 솔루션이 항상 생성되는 것은 아닙니다. 그러나, 나는 그것이 왜 그렇게 빨리 일어 났는지 이해할 수 없거나 더 이상 받아 들일 수 없는데도 여전히 올바른 답을 찾지 못하는 이유를 이해하지 못한다.

Answer 1

수용 가능성을 깨면 A *는 더 이상 올바르게 작동하지 않습니다. 은 더 이상 올바르게 작동하지 않습니다.은 결코 최적의 결과를 얻지 못할 것이라는 의미는 아닙니다. 더 이상 보장 할 수는 없습니다. 또한 솔루션에서보다 빠르게 수렴을 끝낼 수도 있지만, 그 솔루션이 옳지 않다면 무엇이 중요한가?