[인공지능] 탐색과 최적화 - 정보이용 탐색

정보이용 탐색(Informed search)

• 상태 공간에 대한 정보를 이용하여 탐색 효율을 높이는 탐색
• 휴리스틱 탐색(heuristic search)이라고도 한다.
  • 휴리스틱(heuristic) = 시간이나 정보가 불충분하여 합리적인 판단을 할 수 없거나 굳이 체계적이고 합리적인 판단을 할 필요가 없는 상황에서 신속하게 어림짐작하는 것을 의미.
  • 휴리스틱을 사용하는 탐색 방법으로 언덕 오르기 방법, 최상 우선 탐색, 빔 탐색, A* 알고리즘 등이 있다.
  • 검색 효율은 좋으나 일반적으로 최적해를 찾는다는 보장은 하지 못한다.
  • 어떤 휴리스틱을 사용하는가에 따라 성능 차이가 크게 나타날 수 있다.

 

언덕 오르기 방법(hill climbing method)

• 현재 노드에서 확장 가능한 이웃 노드들 중에서 휴리스틱에 의한 평가값이 가장 좋은 것 하나만을 선택해서 확장해 가는 탐색 방법.
• 지역 탐색(local search), 휴리스틱 탐색(heuristic search), 그리디 알고리즘(greedy algorithm)이라고도 한다.
• DFS나 BFS처럼 여러 개의 확장 중인 노드들을 관리하지 않고, 현재 확장 중인 노드만을 관리한다.
• 출발 위치(상태)에 따라 최적이 아닌 해(낮은 정상, 국소 최적해(local optimal solution))에 빠질 가능성이 있다.

 

최상 우선 탐색(best-first search)

• 확장 중인 노드들 중에서 목표 노드까지 남은 거리가 가장 짧은 노드를 확장하여 탐색.
• 남은 거리를 정확히 알 수 없으므로 휴리스틱을 사용하여 추정한다.

 

빔 탐색(beam search)

• 휴리스틱에 의한 평가값이 우수한 일정 개수의 확장 가능한 노드만을 메모리에 관리하면서 최상 우선 탐색을 적용.

 

A* 알고리즘

• 전체 비용이 최소인 노드를 확장해 가면서 해를 찾는 방법.
• 노드 n에서 목표 노드까지 남은 비용을 정확히 계산할 수 없기 때문에, h(n)에 대응하는 휴리스틱 함수 h ^(n)을 사용하여 전체 비용 추정 함수 f^(n)을 정의한다.
• f^(n) = g(n) + h ^(n)
• f(n) = 노드n을 경유하는 전체 비용, g(n) = 현재 노드 n까지 이미 투입된 비용, h(n) = 목표 노드까지 남은 비용
• 널리 사용되는 대표적인 휴리스틱 탐색 알고리즘.