탐색 방법

효율적인 탐색 방법은 깊이 우선 탐색과 너비 우선 탐색을 통해 탐색할 노드의 순서를 결정하는 방식으로 이루어진다. 이러한 탐색 방법을 고려하여 처리 시간을 단축하는 것은 매우 중요하다. 여기서 비용에 따른 탐색 방법은 사전 지식이나 경험, 즉 휴리스틱을 사용하여 처리 시간을 줄이는 접근 방식을 의미한다. 비용의 종류에는 초기 상태에서 상태 𝑠의 최적 경로 이동에 드는 비용의 총합을 𝑔(𝑠)으로 정의하고, 상태 𝑠에서 목표하는 최적 경로 이동에 드는 비용의 총합은 h(𝑠)로 나타낸다. 나아가 상태 𝑠를 거치는 초기 상태에 대한 최적 경로 이동에 드는 비용의 총합은 다음과 같은 식으로 표현된다: 𝑓(𝑠) = 𝑔(𝑠) + h(𝑠).

최적 탐색은 𝑔(𝑠)의 오픈 리스트에 있는 노드 탐색 전 누적 비용의 예측값을 기준으로 하여 𝑔(𝑠)를 최소화하는 노드를 탐색하는 탐색 방법이다. 한편, 최선 우선 탐색은 h(𝑠)의 비용 예측 평가 값을 최소화하도록 노드를 탐색하는 방법으로, 이는 스택이나 큐에 포함되는 노드의 순서를 변경하는 원리에 기반하여 작동한다.

하지만 최적 탐색은 탐색량이 많아지는 단점을 포함하고 있으며, 최선 우선 탐색은 잘못된 결과를 초래할 수 있는 단점을 내포하고 있다. 에이스타(A*) 알고리즘은 𝑓(𝑠)를 𝑔(𝑠)과 h(𝑠) 모두를 활용하여 예측값을 산출하고, 𝑓(𝑠)를 최소화하는 탐색 방법으로 특히 유용하다. 이 과정에서 상태 𝑠의 노드와 연결된 상태인 𝑠'의 노드 예측값 𝑓(𝑠')가 클로즈드 리스트에 포함되어 있을 때, 𝑓(𝑠) 값이 작으면 𝑠' 쪽을 클로즈드 리스트에서 오픈 리스트로 되돌리는 방식이 이루어진다.

게임 트리를 전략에 이용하는 방법은 매우 다재다능하다. 게임 트리는 턴마다 자신과 상대를 통해 노드를 구성하며, 게임 트리의 끝 지점은 해당 시점의 상태, 즉 자신의 유리 또는 불리를 점수로 나타내게 된다. 자신의 턴에서는 유리하다고 가정하고, 상대의 턴에서는 불리하다고 가정하여 효과적인 전략을 세운다. 이러한 게임 트리의 탐색 과정에서 탐색 노드를 줄여 시간 단축을 이루는 방법 중 하나는 미니맥스(Mini-max) 원리에 해당한다.

미니맥스 원리는 자신의 턴에서 점수를 최대화하고 상대의 턴에서 점수를 최소화하도록 노드를 선택하는 방식으로 구성된다. 이 방식은 두 명의 참가자가 존재하는 제로섬 게임 이론에서 기인했으며, 복잡한 게임 및 불확실성이 존재할 때의 일반적인 의사 결정에도 적용될 수 있다. 또한, 알파베타 가지치기(Alpha-beta Pruning)는 노드를 왼쪽부터 탐색하면서 더 이상 탐색할 필요가 없는 변을 잘라내는 작업을 수행하게 된다. 예를 들어, 𝛽컷 오프는 최대 점수를 선택하면서 이미 저장된 점수보다 작은 점수가 있는 노드를 탐색 대상에서 제외하는 방식이다. 반면, 𝛼컷 오프는 최소 점수를 선택하면서 이미 저장된 점수보다 큰 점수가 있는 노드를 검색 대상에서 제외하는 방법이다.

이러한 알고리즘은 바둑이나 장기와 같은 게임에서 탐색 공간이 방대한 경우, 즉 탐색할 노드 수가 많아 메모리 용량과 탐색 시간이 부족해질 수 있는 상황에서도 중요한 도구로 이용된다. 효율적인 탐색 대상 선택 방법으로는 몬테카를로 트리 탐색(Monte Carlo Tree Search, MCTS) 같은 체험적 탐색 알고리즘이 있으며, 이는 주로 게임의 의사 결정을 위한 도구로 활용된다.

또한, 효율적인 탐색 대상 선택 방법 중 하나로 이진 의사 결정 다이어그램(Binary Decision Diagram, BDD)이 불리안 함수를 표현하기 위해 사용되는 자료구조로, 관계 집합의 압축된 표현을 제공한다. 이러한 이진 의사 결정 다이어그램은 데이터의 구조를 효율적으로 절약하고, 여러 변수 간의 관계를 명확하게 나타내는 데 도움을 준다. ZDD(Zero-suppressed Decision Diagram)는 이진 의사 결정 다이어그램의 한 종류로, 불리안 함수의 함축적 표현을 가능하게 한다. ZDD는 particularly advantageous for representing sparse sets and can provide a more memory-efficient way of encoding relationships compared to traditional representation methods.

 

2. 동적 계획법 동적 계획법은 경로 탐색에서 체크포인트(경유지)를 통과해야 하는 필요성이 있을 때 또는 특정 상황에서 탐색이 요구되는 경우에 적용된다. 이 기법에서는 노드에서 노드로 이동하는 모습을 ‘시계열 기준 상태 변화’로 가정하고, 어떤 상태에서 다음 상태로 전환하는 과정에서 비용을 고려하면서 결정을 수차례 반복하는 다단계 결정 문제로 취급된다. 이 다단계 결정 문제를 다루면서 얻은 경로의 평가 함수 𝐽는 극대화하여 경로 탐색 목표를 결정하는 데 중요한 역할을 한다.

다단계 결정 문제의 평가 함수 식 𝐽는 다음과 같은 형태로 표현할 수 있다: 𝐽 = (𝑠1, 𝑠2, 𝑠3,…, 𝑠𝑛). 여기서 시간 𝑡는 1부터 𝑇까지 진행되며, 𝑠𝑡라는 상태 패턴을 𝑁으로 설정할 경우, 얻을 수 있는 상태의 개수가 𝑁𝑇으로 나타날 수 있다. 예를 들어, 𝑁이 3이고 단계 수가 𝑇 = 10인 경우, 총 𝑁𝑇는 약 6만 개에 달하며, 𝑇가 20일 경우에는 약 35억 개의 상태가 발생할 수 있다. 모든 경로를 열거하여 평가하고자 할 때 기하급수적인 계산량(𝑂(𝑁𝑇))이 발생하게 되어 현실적으로 불가능해진다.

다단계 결정 문제의 평가 함수 𝐽를 2개의 변수 함수의 합으로 변경하여 계산량을 𝑂(𝑁²𝑇)로 줄일 수 있으며, 이러한 처리 방식을 동적 계획법 또는 동적 프로그래밍(Dynamic Programming)이라고 한다. 경로 선택에 따라 시간 𝑡 = 1에서 𝑡 = 𝑇까지 순서적으로 𝐹𝑡 𝑠𝑡를 계산하고, 마지막 단계인 𝑇에서는 𝐹𝑇 𝑠𝑇까지만 구한 시점의 최대값을 𝑱로 설정한 후, 반대 순서로 𝐹𝑇(S∗𝑇)를 계산하여 최상의 경로(S∗ 1, S∗ 2, .. S∗𝑇)와 최고 점수 𝑱을 구할 수 있다.

메모리화 기술은 𝑠𝑡에 필요한 3개의 상태를 저장하고 이를 메모리에 기록하는 과정을 포함한다. 이러한 메모리화 방법은 여러 기존의 원본 데이터를 비교하는 데에도 유용하다. 예를 들어, 생물정보학에서는 두 개의 염기 서열과 아미노산 서열을 효율적으로 비교하여 상동성을 계산하는 데에 동적 계획법이 사용된다. 이때 레벤슈타인 거리를 이용해 점수나 페널티를 계산할 수 있으며, 종 간의 유사성이 높은 아미노산에 대한 상대 빈도나 치환 확률을 구한 확률 비율을 대수 행렬로 활용하게 된다.

또한, 경로가 증가함에 따라 메모리 양이 증가하므로 대규모 병렬 처리를 통해 효율적 계산을 수행할 수 있도록 발전하고 있다. 이러한 경향은 정보 기술과 데이터 과학의 결합으로 인해 더욱 두드러진다. 더욱 복잡해지는 데이터 처리 요구에 대응하기 위해서는 이러한 고급 자료 구조와 알고리즘을 폭넓게 이해하고 활용할 수 있는 능력이 필요하다.