티스토리 뷰
A* 알고리즘
1) 기본 분기와 한정 탐색
-. 누적 경로 이용
-. 최적 우선 탐색과정과 유사
-. 최초의 경로가 발견될 때 끝낸다.
2) 개선 1
-. 종료 조건 개선
경로가 발견될 때 끝내지 않고,
가장 짧은 미완성의 경로 길이가 가장 짧은 완성된 경로 길이보다 클 때에야 종료.
3) 개선 2
-. 평가 함수를 하나 더 이용
저평가치(underestimate) 추가 이용
남은 거리에 대한 평가 함수와 누적 거리를 합한 최저한계예측값(lower bound) 이용
4) 개선 3
-. 중복되는(redundant) 경로를 버린다.
동적 프로그래밍 기법(dynamic programming principle) 이용
기존에 나왔던 노드 목록 관리
5) A*알고리즘
-. 분기와 한정 탐색을 1,2,3방법으로 개선시킨 알고리즘.
-. 알고리즘
1. 큐가 비었거나 목표에 도달할 때까지
1.a 만일 큐의 첫 번째 노드가 목표 노드에 도달하는지 결정한다.
1.b 만일 큐의 첫 번째 노드가 목표 노드에 도달하지 못하면
1.b.1 첫 번째 노드를 큐에서 제거
1.b.2 제거된 경로에 대해 노드를 확장
1.b.3 새로운 경로를 큐에 추가
1.b.4 누적비용과 남은비용에 대한 최저한계추측값을 더한 값으로 큐정렬
1.b.5 만일 하나의 노드에 둘 이상의 경로가 존재하면
최소 비용을 가지는 경로를 제외하고는 모든 경로를 제거한다.
2. 목표 노드가 발견되면 성공, 아니면 실패.
Note.
Open Nodes : 생성되 노드 중 평가 함수는 적용되었지만 목표 노드인지 아직 조사된지
않은 노드들
Closed Nodes : 이미 조사된 노드들
평가함수 F' (노드의 참값을 주는 F의 근사함수) = G + H'
G :출발상태에서 현재 노드까지 오는데 소요된 비용, 추정값 아님.
최적 경로를 따라 규칙을 적용하며 노드를 만들 때 소요되는 비용의 합.
H' : 현재 노드로부터 목표 상태로 갈 때 필요한 것으로 추정되는 비용의 추정값.
문제 영역의 지식이 필요.
G의 역할 : 노드 자체의 유용성 뿐 아니라, 그 노드를 포함한 경로의 유용성을 평가
항상 목표에 가까운 방향으로 확장하도록 한다.
풀이를 얻기 위한 경로에 관심이 있다면, G가 유용
경로에 관계없이 풀이만 원한다면, G = 0
최소 단계의 경로를 원하면 G = 1(상수)
최소 비용을 원한다면 G = 각 노드로 오는데 드는 비용
H의 역할 : 한 노드에서 목표 노드까지의 거리를 나타내는 H의 추정값
H'가 H의 완전한 추정값이라면?
H'= 0 -> G에 의해 탐색 제어
G = 0 -> 임의 탐색
H'=0, G=1 ->너비 우선 탐색
http://blog.naver.com/mydaylee/140007014525
'기억하자정보 > 알고리즘' 카테고리의 다른 글
A* algorithm 설명 (0) | 2006.12.27 |
---|---|
길찾기(A*) 알고리즘 테스트 (0) | 2006.12.26 |
A* 알고리즘 (0) | 2006.12.26 |
A*(A Star)는 최적인가? (0) | 2006.12.26 |
최단 경로 다익스트라 알고리즘 (0) | 2006.12.26 |
- 안내
- 궁금한 점을 댓글로 남겨주시면 답변해 드립니다.