탐색을 통한 문제해결 ?

인류는 고대로부터 문명의 발전과 더불어 보다 효율적인 기계적 도구를 개발 해 왔으며 근래에는 컴퓨터까지 개발하게 되었다. 그에 따라 인간도 점차 생각하는 능력과 지능이 발달되었으며 독창적인 일의 구현에 많은 노력을 기울여 왔다.

컴퓨터를통한 문제해결의 방법에는 트리(t-ree)라는 구조가 사용된다. 생물 적인 나무를 닮았다고 해서 트리라고 명명되었으나 실제로는 뿌리(root) 가위로 올라가 있는 가상적인 나무인 것이다.

우리는문제 해결을 위해 탐색을 하게 되는데 탐색이란 트리 구조에 있는 노드 node 들을 조사하는 것이다. 탐색의 방법에는 여러가지가 있다. 그 중 대표적인 것들로는 폭우선 탐색(Br-eadth First Search)과 깊이우선 탐색 (De- pth First Search), 최적우선 탐색(Best F-irst Search)방법, 그리고 경험적 탐색(Heuristic Search)등이 있다.

폭우선탐색법은 어느 노드에서 전개될 수 있는 모든 노드들을 탐색하고 나서 그 노드들로부터 전개된 다른 노드들을 차례로 탐색해 가는 방법이다. 노드의 개수가 유한하고 구하고자 하는 해답이 존재할 경우에 이 방법을 사용하면 반드시 해답을 구할 수 있다는 장점을 가지고 있다. 그러나 이 경우에는 많은 양의 기억장소가 필요하다는 점과 해답이 트리의 깊은 곳에 존재 할 경우 기하급수적으로 많은 탐색이 요구된다는 점이 단점으로 지적된다.

깊이우선탐색이란 한 경로의 탐색을 시작하면 더 이상 전개할 수 없을 때까지 그 경로의 탐색을 계속하고 더 이상 진행할 수 없을 경우에는 바로 전의노드로 돌아와서 다른 경로를 선택하여 다시 탐색을 계속하는 방법이다.

최적우선탐색은 폭우선 탐색과 깊이우선 탐색의 장점들을 하나로 통합한 방법인데 각 단계에서 지금까지 생성된 가장 가능성 있는 노드를 선택하여 탐색하는 방법이다.

경험적탐색이란 노드의 각 단계에서 해답에 이를 수 있는 가능성이 가장 큰 노드를 탐색하는 방법이다. 이 방법은 최적의 해답에 대한 보장은 없지만 대부분의 문제들에 있어서 효율적인 해를 얻을 수 있다. 좋은 경험적 함수를 이용하면 "순회판매원 문제"와 같이 폭발적으로 많은 계산을 필요로 하는 문제들도 효율적으로 풀 수 있다.

"순회판매원문제"란 방문해야 할 도시들과 이들 사이의 거리가 주어졌을 경우 순회판매원이 여러개의 도시를 방문하는데 어떤 특정한 도시를 출발 하여 어떠한 도시도 두번 방문함이 없이 모든 도시들을 거쳐 처음 출발한 도시로 되돌아 오는 경우 총 여행 거리가 최소가 되는 경로의 순서를 정하는 문제다 이 문제는 도시의 개수가 30개일 경우에는 무려 10의 30승 이상의 천문학적 인 경우의 수가 존재하기 때문에 디지틀 컴퓨터를 이용한 문제의 해결은 거의 불가능하다. 따라서 통상적으로는 계산할 수 없는 전형적인 최적화 문제 로 분류되며 극도로 어려운 NP-컴플리트 클래스에 속한다.

이문제를 해결하는 경험적 규칙으로는 최단이웃(Nearest Neighbor)앨고리듬 이 있는데 그 과정은 다음과 같다. 첫째, 출발 도시를 임의로 정한다 . 둘째 다음에 방문할 도시를 정하기 위해 아직까지 방문하지 않은 모든 도시들 중에서 현재의 도시와 가장 가까운 도시를 선택하여 그 도시로 간다. 셋째, 모든 도시를 방문할때까지 둘째 단계를 반복한다. 이 경우에 최선의 답을 구할 수 있다는 보장은 없으나 상당히 빠르게 어려운 문제를 풀 수 있다.

탐색의문제는 얼핏 보기에는 중요하지 않은 것같아 보이나 대부분의 문제해 결에 있어서 매우 중요한 역할을 담당하여 우리 인간도 잘 드러나지 않더 라 도 경우에 따라 위의 방법들을 흔히 쓴다.

우수한탐색 앨고리듬의 사용은 지능적인 컴퓨터의 구현과 매우 밀접한 관련이 있으며 인공지능 관련 연구자들이 추구하는 있는 목표중의 하나다.