[인공지능] 균일비용탐색 / 최상우선탐색 / A* 알고리즘

 

균일 비용 탐색 / 최상우선탐색 / A* 알고리즘 

 

1. OPEN에 출발노드를 넣는다. 출발노드의 비용은 0이다.
2. OPEN에 노드가 남아있는 동안 다음을 반복한다.
   1. OPEN의 제일 앞에 있는 노드를 꺼내어 CLOSED에 넣는다. 이 노드를 n이라고 한다.
      1. 여기서 OPEN안에 있는 노드들은 비용 기준으로 오름차순 정렬되어 있다. -> 우선순위 큐 사용
   2. 노드 n이 목표노드라면 탐색은 성공적을 ㅗ끝난다. 포인터를 역으로 추적하며 탐색 경로를 얻는다.
   3. 노드 n을 확장하여 후계노드 n1, n2, .. , ni를 생성한다. 
      이들 후계노드에 부모노드인 노드 n을 가리키는 포인터 만든다.
   4. 후계노드 n1, n2, ... ni의 경로비용을 계산한다.
      1. 경로비용은 균일비용탐색, 최상우선탐색, A* 알고리즘 각각 다르다. 
         1. 균일비용탐색 - 출발노드로부터 현재노드까지 거리
         2. 최상우선탐색 - 현재노드로부터 목표노드까지의 거리 (휴리스틱)
         3. A* 알고리즘 - 출발노드로부터 현재노드까지 거리 + 현재노드로부터 목표노드까지 거리
   5. 각각의 후계노드에 대해 다음을 수행한다.
      1. n_j와 동일한 노드가 OPEN에 존재
         1. 그 노드의 경로비용이 새롭게 구한 경로비용보다 크다면 그 노드를 n_j로 대체하고
         2. 그렇지 않으면 n_j는 무시
      2. n_j와 동일한 노드가 CLOSED에 존재
         1. 그 노드의 경로비용이 새롭게 구한 경로비용보다 작다면 n_j 무시
         2. 새롭게 구한 경로비용이 더 작으면 OPEN에 추가
      3. OPEN이나 CLOSED에 존재하지 않으면
         1. OPEN에 n_j 추가
   6. OPEN에 저장된 노드를 오름차순 정렬한다.

 

• 균일비용탐색, 최상우선탐색(BFS), A* 탐색 알고리즘 모두 위의 과정과 유사하다. 차이점은 노드의 값을 계산하는 방식
  • 균일비용탐색 - 출발 노드로부터 현재 노드까지의 거리
  • 최상우선탐색 - 현재 노드로부터 목표 노드까지의 거리 (휴리스틱 목적함수)
  • A* 탐색 - (출발 노드 ~ 현재 노드까지의 거리) + (현재 노드~목표 노드까지의 예상 거리)