a* 비용계산

Question

A*알고리즘이 G는 시작점에서 해당 좌표까지 이동하는데 드는 비용이고 H는 목적지로부터 얼마나 가까운지를 따지는 비용이라고 알고 있었는데 맵매니저를 만들 때 G를 왜 0으로 두는지 잘 이해가 안되고 H는 원래 (목적지까지 남은 X 방향의 타일 + Y 방향의 타일)로 계산했었는데 (목적지까지 남은 X 방향의 타일^2 + Y 방향의 타일^2)으로 바뀐건지 잘 이해가 안됩니다ㅠㅠ

Rookiss · Answer

휴리스틱 공식은 스스로 정하는 것이지
꼭 뭘 어떻게 해야 한다는 규칙이 있는 것이 아닙니다.
마찬가지로 G, H 합산한 것을 cost로 치는데
이 또한 스스로 어떻게 우선순위를 판단할지 정하는 부분일 뿐
공식처럼 뭘 하는 것이 아닙니다.

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴이에요. A* 알고리즘은 최단 경로를 찾는 알고리즘으로, G는 시작점에서 현재 위치까지의 이동 비용, H는 현재 위치에서 목적지까지의 예상 이동 비용으로 사용되는 것이 일반적입니다. G를 0으로 둔 이유는 시작점부터 현재 위치까지의 이동 비용이 초기에는 0이기 때문입니다. 즉, 시작점에서 현재 위치까지 이동한 거리를 의미하는 것이 아니라, 현재 위치까지의 총 비용을 나타냅니다. H는 현재 위치에서 목적지까지의 예상 이동 비용을 결정하는데 사용됩니다. 일반적으로 유클리드 거리(목적지까지 남은 X 방향의 타일^2 + Y 방향의 타일^2의 제곱근)를 사용하지만, 실제로는 다른 형태의 휴리스틱 함수도 사용할 수 있습니다. 이 함수는 목적지로부터 얼마나 가까운지를 계산하는 용도로 사용되며, 좀 더 정확한 예상 비용을 계산하는 데 도움을 줍니다. 따라서 G는 현재 위치까지의 총 비용을, H는 목적지까지의 예상 비용을 나타내는 것이 일반적인 사용 방법입니다. 해당 맵 매니저에서 G가 0으로 두어진 이유와 H가 유클리드 거리의 제곱으로 계산되는 이유에 대해서는 맵 매니저에서 지정한 규칙이나 요구사항 때문일 수 있습니다. 좀 더 자세한 설명을 원하시면 맵 매니저의 개발자에게 문의해보시는 것이 좋을 것 같아요. 어떤 경우에든 도움이 되었으면 좋겠습니다. 감사합니다.