인공지능 정보이용 탐색

먼저 맹목적 탐색과 정보이용 탐색의 개념으로 어떻게 다른지 알아보자

 

맹목적 탐색 vs 정보이용 탐색

맹목적 탐색은 파란색 공의 노드를 따라 탐색을 하며 파란색 공과 목표상태를 이어주는 파란 점선 즉 추정하는 값을 사용하지 않는다.

단순하게 맹목적 탐색은 현재 진행되는 노드중에 선택을 해야만 하는 것들을 골라 목표상태에 다다르지만 정보이용 탐색은 파란색 점선 즉 '?'의 값 추정하는 값들을 이용하여 목표상태를 결정한다.

 

정보이용 탐색

1. 휴리스틱: 정보가 불충분해서 정확히 판단할 수 없는 상황에 신속하게 어림짐작 가능한 곳 에서 탐색하는 방법.

                 ex)최단 경로 문제에서 목적지까지 남은거리

최단거리 문제

2. 언덕 오르기 방법: 지역탐색,휴리스틱탐색을 이용하는 방법이며 현재 노드에서 휴리스틱에 의한 평가값이 가장 좋은 이웃 노드를 가지고 그 곳에 하나씩 확장해 나가는 탐색방법이다.

이 방법은 가장 좋은 해를 무조건 얻을 준다는 보장이 없지만 국소 최적해는 얻어준다.

예를들어 위의 그림에서 가장높은 언덕을 찾아라 하였을 때 B근방에 있는 언덕이 가장 높다.

하지만 언덕 오르기 방법을 통해 A는 근방에 현재위치보다 높은 곳을 계속 찾다가 자기 근방에 있는 가장 높은 언덕을 발견하면 탐색을 종료한다.

이를통해 현재 자신이 위치해 있는 곳에 따라 얻는 해가 달라질수 있으며 A는 현재 가장 좋은 해를 얻지는 못하지만 국소 최적해를 얻는다고 볼 수 있다.

 

3. 최상 우선 탐색: 확장 중인 노드들 중에 목표 노드까지 남은 거리가 가장 짧은 노드를 확장하여 탐색하는 방법이다.

맨 처음에 보았던 그림에서 파란색 점선 즉 목표상태로 가기위한 길 중에서 제일 짧은 길을 선택하는 방식이며 남은 거리를 정확히 알 수 없기에 휴리스틱 방법을 사용한다.

밑에 그림은 예시이다.

 

8-퍼즐 문제

맨 오른쪽이 목표 상태이며 왼쪽 퍼즐의 4라는 숫자는 총 4번 위치를 바꾸면 목표상태로 도달할 수 있다는 평가값이다. 여기서 가장 짧은 노드를 알기위해 확장을 해보면

제일 숫자가 적은 노드는 c이므로 c를 통해 또 확장을 해보면

e와 f가 동일하게 나오기 때문에 둘중 아무거나 선택을 하여도 무방하다 e를 선택할 시

위와 같은 경우가 나오며 또 가장 짧은 노드를 선택을 해야하므로 h를 선택한다.

이렇게 가장 짧은 노드의 타일이 나온다. 이런식으로 계속 목표노드까지 가장 짧은 경로의 있는 노드를 선택하는 방식이 최상 우선 탐색이다.

 

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

 

예를들어 초기상태에서

맨 처음에 일정개수(K)를 2라 가정을 하고 이런 다섯가지의 노드가 생성이 되었다고 가정해보자.

특정 목표상태에 도달하기위해 최상 우선 탐색을 적용하였을 때 가장 우수한 것을 B와E라 하였을 때 나머지 A,C,D는 더이상 노드가 진행이 되는 않는 것이다.

이 B와 E를 필두로 노드를 확장해 나가면

각각 B와 E의 노드들이 생성이 되는데 K가 2이므로 각 노드가 생성될 때 선택 될 수있는 개수는 2개이다 위 그림은 B와E노드가 하나씩 선택이 되었지만 실제로는 B에서 계속 선택이 될 수도 있고, E에서 선택이 될 수도 있다. 단 2개가 초과가 되지 않고, 오직 목표상태로 도달하기 위한 K개를 찾는 탐색 방법이다.

 

5. A*알고리즘:  최상 우선 탐색방식을 보완한 탐색방식이다.

기존의 최상 우선 탐색방식은 목표노드까지 갈 수있는 가장 짧은 노드의 값만을 취해서 전체적인 값을 고려를 하지 않았다.

그래서 생기는 문제는 전체비용으로 따졌을 때 그 값이 가장 최적하다고 할 수 없는 것이다. 

A*알고리즘을 통해 추정한 전체 비용 f^(n)을 최소로 하는 노드를 확장해 가는 방법이며 밑에는 여기에 쓰이는 함수이다.

 

특정 노드n을 경유하는 전체 비용의 함수이며 현재 노드n까지 이미 투입된 비용g(n)과 목표 노드까지 남은 비용h(n)의 합을 나타내는 함수이다, f(n)= g(n) + h(n)

실제 남은 비용으로 정확한 예측이 불가한 함수

 

h(n)에 대응하는 휴리스틱 함수

 

노드 n을 경유하는 추정 전체비용이며 h에 대응하는 휴리스틱 함수와 이미 투입된 비용g(n)의 합이다.

 

8-퍼즐을 이용해 A*알고리즘 적용

위에 그림을 보다시피 최상 우선 탐색을 하고 이미 지나간 노드의 수를 합산하여 값을 계산하다. 목표상태까지 이르기까지  f^(n)의 값이 제일 작은값을 계속 선택을 하다보면 가장 최적의 값을 구할 수있다. 

하지만 A*알고리즘도 h^를 어떻게 잡는냐에 따라 값이 달라지는데 이런 경우를 막기 위해 사전에 h^ <= h 라는 전제조건을 설정을 하며 h^에 내포되어 있는 휴리스틱 함수가 실제 남은비용보다 크게 계산할 일이 없기에 오류가 발생하지 않는다.