인공지능 - 탐색

 상태공간 탐색 방법 (그래프 탐색)

---

  출발 노드는 초기상태 표현과 관련된다

 

  후계 노드는 어떤 노드에 해당되는 상태표현에 적용 가능한 연산자를 적용하여 얻어진다. 어떤 노드에 연산자를 적용하여 후계 노드를 만드는 과정을 "노드를 확장한다" 라 표현한다

 

  후계 노드들은 목표 노드인지를 확인한다. 후계 노드에 해당하는 상태표현이 목표상태를 표현하고 있는지 확인한다. 만일 목표 노드가 찾아지지 않았다면, 노드를 계속 확장한다.

 

  후계 노드들은 각각 그 부모 노드를 가리키는 포인터를 가지고 있다. 목표 노드가 최종적으로 찾아졌을 때 이 포인터를 사용하여 출발 노드부터 최종 노드까지의 경로를 얻을 수 있다. ( 출발 노드에서부터 현재까지의 경로를 기억시키는 것 보다 목표 노드가 발견되었을 때만 포인터를 이용하여 출발 노드까지의 경로를 역으로 얻어내어 이를 풀이경로로 하는 것이 편리하다) 출발 노드로부터 최종 노드까지의 경로상의 아크에 해당하는 연산자들이 모여 풀이순서를 이룬다

 

탐색의 종류

---

  그래프 탐색을 이용할 경우 문제를 해결하기 위해 출발 노드부터 시작하여 정해진 순서대로 노드를 확장하여 목표 노드를 찾아나간다. 이 경우 탐색과정에서 사용되는 정보에 따라 ( 또는 목적에 따라) 다양한 선택이 이루어질 수 있다.

 

  응용분야에 따라서 어떤 경로를 거치든 신속하게 목표를 탐색하는 것이 목적일 수도 있고 단순히 경로를 찾는 것이 아닌 최적의 경로를 찾는 것이 목적일 수 있다. 목표상태에 도달하기 위해 탐색과정에서 문제영역에 유용하게 적용될 수 있는 정보를 사용하는 경우(경험적 탐색)와 상태공간을 아무런 기준 없이 무작정 탐색해 나가는 경우(무정보 탐색)이 있다

 

종류	임의의 경로 탐색	최적경로 탐색
무정보 탐색	깊이우선 방법, 너비 우선 방법	균일비용 방법
경험적 탐색	언덕 오르기 방법, 최적우선 방법	A* 알고리즘

 

  무정보 탐색의 경우 목표 노드의 위치에 무관한 순서의 노드를 확장하는 방법으로, 언젠가는 해를 찾을 수 있겠지만 체계적이거나 효율적인 방법은 아니다. 거대한 박물관에서 특정 소장품을 이리저리 찾아다니는 것과 비슷하다 하여 영국 박물관 알고리즘(BMA; British Museum Algorithm)이라 하기도 한다

  박물관 알고리즘은 최악의 알고리즘이지만, 탐색영역이 제한적이거나 적절히 축소될 수 있다면 간단하고 유용하게 사용 가능하다

 

  경험적 탐색은 문제영역에서 사용할 수 있는 목표 노드의 위치와 관련된 정보를 사용하므로 이 정보가 완벽하다면 이를 이용하여 목표 노드에 쉽고 빠르게 접근이 가능하다.

  대부분의 경우 경험적 정보에 의존한다 (경험적 정보는 항상 옳지는 않지만 대부분 잘 맞는 정보를 의미)

 

무정보 탐색

---

  사전에 정보가 제공되지 않는 상태에서 탐색하는 방법. 초기상태, 연산자, 목표상태인지를 판정하는 검사로 이루어져 있고 사전에 예정된 순서나 무작위로 노드를 탐색하는 방법과 같이 조직적이고 체계적인 방법을 사용해야 한다. 보통 그래프 형태로 이루어져 있다

 

깊이우선 방법 (depth-first search)

  탐색 트리의 수직방향으로 점차 깊은 곳 까지 목표 노드를 탐색해 나가는 기법. 목표 노드를 만나지 못하고 더 이상 진행할 경로가 없을 때에는 거꾸로 올라오며 다른 경로의 탐색한 적이 없는 경로로 탐색을 진행한다.

 

  해가 없는 경로를 계속해서 따라 갈 수 있으므로 필요에 따라서 상위 노드로 되돌아가는 (백트래킹) 방안을 마련해 두어야 한다. 이를 위해 일반적으로 적당한 깊이제한을 두어 어떤 노드가 그 이상의 깊이를 갖게 되면 이 노드를 더 이상 확장하지 않고 깊이제한을 넘지 않는 것 중 가장 깊은 최근에 생성된 노드를 골라 확장시킨다

 

깊이우선 방법

 

  현 경로상의 노드만을 기억하면 되므로, 저장 공간의 수요가 상대적으로 작고 목표 노드가 깊은 단계에 있을 경우 비교적 해를 빠르게 구할 수 있으며, 구현하기가 용이하다는 장점을 가진다

 

  반대로, 해가 없는 깊은 경로에 깊이 빠질 가능성이 있고, 얻어진 해가 최단경로가 된다는 보장이 없다는 단점을 지닌다.

 

너비우선 방법

  깊이우선 방법과는 달리 노드의 모든 자녀 노드를 탐색한 후에도 해가 발견되지 않으면 다시 이들을 확장하고 새로이 생성된 노드를 모두 탐색하는 식으로, 목표 노드를 만날 때 까지 단계별로 너비방향의 탐색을 진행해 나간다

 

너비우선 방법

 

  목표에 이루는 최단의 경로를 찾고 (목표에 이루는 경로가 다수일 때 너비우선 탐색방법을 통해 최초로 만나는 목표 노드는 최저의 깊이에 있으므로 최단경로를 얻게 된다) 각 깊이 단계마다 모든 노드를 차례로 점검해 나가므로 해가 있다면 반드시 찾을 수 있으며, 가지가 많지 않고 해가 얕은 곳에 있을 경우에는 더욱 유리한 장점을 지닌다

 

  대부분의 문제가 깊이가 깊어질수록 노드의 수도 급격히 늘어나므로 자칫하면 해를 찾는 탐색시간이 비현실적으로 늘어날 수 있고, 탐색을 위해 거친 모든 노드의 경로를 기억해야 하므로 저장공간이 많이 필요하다는 단점을 가진다

 

균일비용 방법

  출발 노드로부터의 경로비용이 최소인 노드를 선택하여 확장시키는 방법이다. 깊이우선 방법에서는 나중에 생성된 것이 먼저 확장되고 너비우선 방법에서는 먼저 생성된 것이 먼저 확장되는데, 이들 탐색방법에서 비용은 고려되지 않는다. 균일비용 방법은 출발 노드로부터 경로비용이 최소인 노드를 선택하여 확장하므로 발견된 목표 노드는 최소의 비용이 소요되는 경로가 된다.

 

무정보 탐색 정리

종류	장점	단점
깊이우선 방법	현 경로상의 노드만을 저장하면 되므로, 저장공간의 수요가 상대적으로 적다   목표 노드가 깊은 단계에 있을 경우 해를 비교적 빠르게 구할 수 있다   구현이 용이하다	해가 없는 경로에 깊이 빠질 가능성이 있다   얻어진 경로가 최단경로일 보장이 없다
너비우선 방법	목표에 이르는 최단의 경로를 찾는다	자칫하면 해를 찾는 탐색시간이 비현실적으로 늘어날 수 있다   탐색을 위해 거친 모든 노드의 경로정보를 저장하므로 기억공간이 많이 필요하다
균일비용 방법	출발 노드로부터 비용이 최소가 되는 경로를 찾는다

 

경험적 탐색

---

  무정보 탐색방법은 간단한 규칙을 통해 목표 노드까지의 경로를 찾는 문제에 대한 해를 제공하지만, 경로를 발견하기까지 너무 많은 노드들을 확장시켜 가능한 영역을 소모적으로 탐색해야 하므로 효율적이지 못한 경우가 많다.

  

  많은 문제에서 탐색작업을 축소하기 위해 경험에 따른 규칙들을 사용하는 경우를 경험적 탐색방법(heuristic search method)라 한다

 

순회 세일즈맨의 문제 (traveling salesman problem)

세일즈맨이 4개의 도시를 순회할 수 있는 3가지 경로

 

  도시 n개를 순회하는 모든 경우를 탐색한다 가정하자, n개의 도시에 1개의 도시만 추가하더라도 탐색량은 n배가 늘어난다. 이 문제는 많은 가능성을 비교한 후 최적의 경로를 찾는 것으로, 해를 찾는 것이 쉽지 않다.

 

  만일 문제에 대한 정보나 지식을 가지고 있다면 쉽게 목표에 도달할 수도 있을 것이다. 여기서 정보는 흔히 완전하지 않고 수학적으로 최적의 해를 제공하기보다는 막연히 도움이 될 것이라는 경험적인 정보일 수도 있다. 이와 같이 비록 부정확하고 보장되지는 않지만 빠르게 해를 발견하거나 최적해를 발견하거나 또는 둘 다를 만족할만할 가능성을 증가시키는 방법을 경헙적 탐색방법이라 한다

 

  가장 가까이에 있는 곳부터 방문하는 것이 경로의 총 연장을 줄일 수 있다는 직관을 이용하여 규칙을 정해보자

 

1. 임의의 도시를 출발지로 한다
2. 다음 방문할 도시는 방문하지 않은 도시 중 현재의 도시에서 가장 가까운 곳으로 정한다
3. 더 이상 방문할 도시가 없으면 지금까지 방문한 도시의 순서가 해가 되며, 그렇지 않다면 다시 2번으로 가서 방문을 계속한다

 

도식도

 

  경험적 탐색방법을 이용하는 경우 탐색과정에서 노드들의 확장순서를 정하기 위해 평가함수(evaluation function)을 사용한다. 평가함수의 목적은 확장시킬 노드들에 순위를 매김으로써 어떤 것이 최상의 경로에 있는지를 결정하는 것이다. 평가함수는 어떤 노드에 대해 이것이 최상의 경로에 있을 확률을 이용하기도 하고 임의의 노드와 목표 노드 사이의 거리나 차이를 이용하기도 한다.

 

언덕 오르기 방법

  목표 노드를 언덕의 꼭대기에 비유하고 각 노드에서 언덕의 꼭대기에 가장 빨리 도달할 수 있는 다음 노드를 선택하는 방법을 언덕 오르기 방법 (hill climbling search)라 한다. 어떤 방법이 최선인지를 결정하기 위해 관련 정보가 필요하고 이 방법은 깊이우선 탐색방법과 비슷한 방법으로 가장 유망한 자녀 노드를 선택한다. 즉 자녀 노드들이 알려져 있을 때 평가함수를 사용하여 노드를 선택한다.

 

  앞으로 소요되는 비용만을 고려하며 또한 현재 진행중인 경로를 우선적으로 탐색하므로 최적경로 탐색을 보장하지는 않는다. 어떤 평가함수를 사용하는가에 따라 탐색결과가 달라진다.

 

최적우선 방법

  깊이우선 탐색방법에서 국부 최대에 빠지는 단점을 해결하는 방법은 각 상태마다 해를 찾는 데 가장 유망한 노드만을 확장함으로써 탐색범위를 줄이는 방법이다. 이 것을 최적우선 탐색이라 하는데, 지역적으로 확장된 트리의 모든 노드 중 가장 좋은 노드부터 탐색하는 방법이다

 

  기본적으로 우선순위가 정해져야 하고 메모리가 많이 필요하며, 구현이 복잡한 것이 단점이다

 

  최적우선 탐색방법은 두 가지에서 언덕 오르기 탐색방법과 구분된다

  첫째로 언덕 오르기 방법에서는 하나의 노드가 선택되면 같은 단계에 있는 다른 노드들은 모두 무시되고 다시 고려하지 않지만, 최적우선 방법에서는 열린 노드들을 대상으로 평가함수를 계산하여 비교함으로써 선택되지 못한 노드도 다음에 선택될 가능성이 있다는 것이다

  둘째로 언덕 오르기 방법에서 자녀 노드에 더 좋은 함수값을 가지는 노드가 없을 경우(지역 최대를 만난 경우) 탐색하는 데 어려움이 있지만, 최적 우선 탐색에서는 열린 노드들을 대상으로 가장 좋은 함수값을 가지는 노드를 선택하므로, 탐색을 계속할 수 있다.

 

A* 알고리즘

  언덕오르기 방법이나 최적우선 방법에서 사용한 평가함수는 각 노드의 목표 노드와의 근접도였다. 그러나 최적의 경로는 뿌리 노드에서 목표 노드까지의 최단의 경로를 의미한다

  A* 알고리즘은 출발 노드로부터 목표 노드까지의 최적경로를 탐색하기 위한 것이다

 

  평가함수

f(n) = g(n) + h(n)

g(n) : 초기 노드에서 n 노드까지의 최단거리
h(n) : n 노드에서 목표 노드까지의 최단거리

  따라서 가장 작은 평가함수 f(n)을 가지는 노드를 따라 탐색해 나가면 가장 빠른 해에 이르게 된다. 그런데 식 f(n)은 초기 노드에서 목표 노드에 이르는 경로를 찾되 노력 n을 거치는 것을 제약조건으로 하는 것을 의미한다. h(n)은 아직 탐색되지 않은 경로이므로 실제 평가함수는 다음과 같이 수정되어야 한다

f(n) = g(n) + h'(n)

g(n) : 초기 노드에서 n 노드까지의 최단거리
h'(n) : n 노드에서 목표 노드까지의 예측 최단거리

  여기서 모든 n에 대해 h'(n) <= h(n)의 조건이 성립하면 평가함수는 허용성을 가진다 말한다.