인공지능 - 6. 탐색 과정

그래프 탐색

- 문제에 대한 상대공간이 있으면, 해는 초기 상태에서 목표상태까지 연산을 반복하여 얻을 수 있음.

 

 

탐색 종류

- 맹목적 탐색 blind search : 목표 노드 위치와 무관한 순서대로 노드 확장. 소모적

- 경험적 탐색 heuristic search : 목표 노드와 관련된 정보나 경험적 정보를 이용한 탐색

  * 경험적 정보 heuristic information : 항상 옳지는 않지만 대부분 잘 맞는 정보

	임의경로 탐색	최적경로 탐색
맹목적 탐색	깊이우선 탐색 너비우선 탐색	균일비용 탐색
경험적 탐색	언덕오르기 탐색 최적우선 탐색	A* 알고리즘

 

깊이 우선 탐색 depth first search; dfs

- 해가 존재할 가능성이 있는한 앞으로 계속 전진하는 탐색

- 더 진행할수 없으면 다른 경로를 선택가능한 노드로 복귀하여 탐색 계속 =>백트래킹

 

 

너비 우선 탐색 breadth-first search, bfs

- 생성 순서에 따라 노드를 확장하는 방법

- 출발 노드에서 목표노드까지 최단길이 보장 -> 경로가 긴경우 탐색 가지가 매우 증가

 

 

균일 비용 탐색 uniform cost search

- 출발 노드서 경로비용이 최소인 노드를 확장시켜나가는 방식

 

 

 

 

경험적 탐색방법 heuristic search method

- 맹목적 탐색 방법의 한계 : 경로 찾는데 너무 많은이 노드 확장

- 경험적 정보로 보다 빠르게 탐색 진행하는 방법

- 바람직한 노드를 선택하기 위해 평가 함수 evaluation function 사용

 

 

언덕 오르기 탐색 hill climbing search

- 목표까지 경로비용 h(n)을 기준으로 노드 선택.

- 실제 h(n)을 구할수 없으니 예측치 hat{h}(n) 이용

   * hat{h}(n) 은 경험적 정보를 이용한 h(n) 예측치

 - 경로 비용이 작은 노드만 선택하여 지역적 최대치에 도달하나 전역적 최대치인지는 보장못함.

 

 

모의 담금질 simulated annealing

- 언덕 오르기 탐색이 지역 최대치에서 멈출수 있는 문제를 개선하기 위한 방법

- 가열하면 원자들이 움직이며 식으면서 더 낮은 에너지를 찾을 가능성이 높아지므로 모의 담금질이라 부름.

 

최적 우선 탐색

- 임의의 노드에 대한 평가함수 사용. 목표 노드까지 비용 예측치.(언덕 오르기 탐색과 동일)

- 언덕 오르기 탐색은 진행 방향의 후계 노드 중에서 가장 적합한 노드 선택

- 최적 우선 탐색은 전체 노드 대상으로 선택

 

 

A* 알고리즘

- 언덕오르기, 모의담금질과는 달리 출발 노드서 도착 노드까지 비용을 평가 함수로 고려

 ->  평가 함수 f(n) = g(n) + h(n)

    * g(n) : 출발노드서 n노드까지 비용

    * h(n) : 노드 n에서 목표노드 n까지 비용

- h(n)은 아직 탐색하지 못했으므로 계산하기 어렵거나 알 수 없음.

     -> 경험적 정보에 의한 예측 평가 함수

        hat{f}(n) = g(n) + hat{h)(n)

        * g(n) : 출발노드서 n노드까지 비용

        * hat{h}(n) : 노드 n에서 목표노드 n까지 비용

- hat{h}(n)이  잘 예측되어야 f(n)에 가까워져 효율적 탐색 수행.