A* 알고리즘 요약

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