UCS & A*

포스텍 컴퓨터공학과 유환조 교수님 강의자료를 참고하였습니다.

• UCS(Uniform Cost Search) : 다익스트라랑 같은 의미이다. 노드간 최단 경로를 찾아준다. 이전 글에 다익스트라에 대한 설명이 있다.

• A* : UCS의 시작점으로부터 목표 노드가 아니더라도 최단 경로를 구해주는 단점을 보완한 알고리즘이다. 휴리스틱 추정값 h(x)를 사용하여 목표하는 지점에 대한 최적(optimal)의 경로를 찾아간다.

  

  그림에서 살펴보면 UCS 알고리즘의 경우 end까지 모든 경로를 탐색하면서 진행이 된다. 빨간색의 Wasted effort 영역의 필요없는 부분까지 탐색을 하기 때문에 A* 알고리즘은 penalty를 준다.

  edge cost가 다음과 같이 정의되어 penalty를 주게 된다. $Cost'(s,a)=Cost(s,a)+h(Succ(s,a))-h(s)$
  하지만 이런 휴리스틱은 문제점이 존재한다.

  

  분명히 A->C->D로 가는 경로가 optimal한 경로지만 위는 A->B->D가 최적의 경로라고 잘못 탐색하는 것을 볼 수 있다. 이것은 바로 edge cost가 음수이기 때문에 발생하는 현상이다. 다익스트라에서도 edge cost에 대해서 항상 0이상일 때 사용할 수 있는데 같은 이유라 볼 수 있다.

  그래서 이러한 휴리스틱 h에 대해서 다음과 같은 조건을 만족하면 negative한 edge cost가 발생하지 않는다.
  $Cost'(s,a)=Cost(s,a)+h(Succ(s,a))-h(s)\ge 0$

  

  즉, 이러한 triangle 구조를 가져야 한다는 점이다.

---