gksrudtlr
|2025. 5. 20. 16:29
- 정의
- 최단 경로를 찾기위한 정보 기반 탐색 알고리즘
- 다익스트라의 확장 버전으로, 휴리스틱 함수를 사용해 탐색 효율성 크게 향상
- 핵심 개념
- 휴리스틱 함수
- 목표 노드까지 예상 비용 추정
- 추정 값은 완벽할 필요 없음
- 실제 비용을 절대 초과하지 않아야 효과적
- 평가 함수 $f(n) = g(n) + h(n)$
- g(n) : 시작 노드부터 현 노드까지 실제 비용
- h(n) : 현재 노드에서 목표 노드까지 추정 비용(휴리스틱)
- 열린 목록 / 닫힌 목록: 탐색 과정에서 방문 예정인 노드와 이미 방문한 노드 관리
- 알고리즘 작동 방식
- 시작 노드를 열린 목록에 추가
- 반복
- 열린 목록에서 f(n) 값이 가장 낮은 노드 선택
- 목표노드면 탐색 종료
- 아니라면, 이 노드를 닫힌 목록으로 이동하고 인접 노드들을 처리
- 각 인접 노드에 대해 f(n)을 계산, 열린 목록에 없으면 추가, 있다면 더 나은 경로인지 확인하여 업데이트
- 열린 목록 비어있다면 경로 존재하지 않음
- 일반적 휴리스틱 함수
- 맨해튼 거리 : $|x1 - x2| + |y1 - y2|$(격자 기반 맵에서 주로 사용)
- 유클리드 거리: $\sqrt{(x1 - x2)^2 + (y1 - y2)^2}$(자유로운 이동이 가능한 경우)
- 대각선 거리 : $max(|x1 - x2|,|y1 - y2|)$(8방향 이동이 가능한 격자
- 장단점
- 장점
- 다익스트라보다 효율적
- 휴리스틱 함수가 허용적이면 항상 최적의 경로
- 휴리스틱 정확도에 따라 성능 조절 가능
- 단점
- 메모리 사용량 많을 수 있음
- 휴리스틱 함수 선택에 따라 성능 크게 영향받음
- 그래프가 매우 크면 계산 비용이 높음
- 사용 분야
- 게임 AI
- 로봇 경로 계획
- 네비게이션 시스템
- 네트워크 라우팅
