정의

패스파인딩 알고리즘에서 현재 위치에서 목표 지점까지의 최소 비용을 추정하는 함수입니다.

• 데이터를 기반으로 각 분기 단계에서 어느 한 분기를 선택하기 위한 추정값을 설정합니다.

휴리스틱 함수

Shortest Distance (최단 거리)

• 가장 기본적인 휴리스틱으로, 현재 포인트에서 목표 포인트까지의 직선 거리나 맨해튼 거리를 사용합니다.
  • 맨해튼 거리는 격자 기반 맵에서 4방향 이동이 가능할 때 주로 사용됩니다.
• h(n)이 실제 최소 비용을 과대평가하지 않는 '허용 가능한(admissible)' 휴리스틱이 되어야 최적 경로이 가능합니다.

Feedback

• 이전에 계산된 경로에서 사용되지 않은 포인트와 엣지를 선호하는 휴리스틱입니다.
• 여러 경로를 계산할 때 다양성을 제공하며, 이미 사용된 경로를 피하게 합니다.
• 여러 유닛이 같은 경로를 사용하지 않도록 하거나, 이전 경로가 막혔을 때 대안 경로를 찾는 데 유용합니다.