반응형
체계적 탐색과 경험적 탐색
체계적 탐색이란 선험적인 지식 없이 상태공간을 탐색하여 해를 찾는 것을 말하며, 상태 공간을 모두 탐색하므로 해의 발견이 보장되지만, 상태 공간이 커지면 목표 상태가 존재하는 위치에 따라 해를 발견할 때까지의 시간이 매우 길어지는 단점이 있다.
경험적 탐색은 탐색 지점(노드)을 사전에 축적된 평가 기준을 바탕으로 우선순위를 붙여서 그 순서대로 조사해 나감으로써 탐색 효율을 향상시키는 방법으로, 휴리스틱 탐색법이 이에 속한다.
휴리스틱 탐색법(Heuristic Search)
- 경험적으로 얻을 수 있는 지식에 기반하여 탐색을 수행하는 방법을 말하며, 휴리스틱 함수(h(n))를 평가 함수로 사용한다.
- 탐색을 효율적으로 수행하기 위해 목표 상태를 기준으로 현재 상태가 어느정도로 평가되는지 알아보기 위한 방법이다
- 대표적인 휴리스틱 탐색 방법으로 언덕 오르기, 최적 탐색, 최고 우선 탐색, A* 알고리즘 등이 있다.
- 휴리스틱 함수 h(n)은 현재 노드에서 목표까지의 최적의 비용을 추정하는 함수이며, 휴리스틱 함수를 어떻게 설정하느냐에 따라 가능한 해에 대한 평가 결과가 다르게 나타난다.
- 항상 최적의 해를 보장할 수는 없지만, 인간의 판단과 유사하게 그럴 듯한 수준의 해를 발견할 가능성이 높다.
- 8-퍼즐 예시의 경우 '현재 목표 상태에 있지 않는 퍼즐의 수'나 '개별 퍼즐의 현재-목표 상태 간의 맨하탄 거리의 합' 등의 휴리스틱 함수(평가 기준)을 적용하여 우선적으로 탐색할 순서를 정의할 수 있다.
언덕 오르기 탐색(Hill-climbing Search)
- 알고리즘이 단순하며, 현재 상태 개선을 목표로 자주 이용되는 탐색법
- 현재 상태보다 휴리스틱 함수의 평가값이 높은 경우 다음 상태로 이동
- 국소 최고해(언덕의 정상이지만 다른 언덕에 비해 가장 높지는 않은 경우)에 머무를 수 있다는 단점이 있음
알고리즘
- 시작노드 S를 탐색 노드 n이라고 한다.
- 만약 노드 n에 적용 가능한 연산자가 없다면 노드 n을 해 노드라고 하고 탐색을 종료하고, 연산자가 존재한다면 다음 단계를 진행한다.
- 노드 n에서 1단계로 도달할 수 있는 자식 노드 중 휴리스틱 함수의 평가값이 현재 노드보다 좋은 경우가 존재하지 않으면 n을 해 노드로, 존재 한다면 평가값이 가장 좋은 자식 노드를 탐색 대상 노드(n)으로 설정하고 2단계를 다시 수행한다.
최적 탐색(Optimal Search)
- 탐색하고자 하는 문제에서 연산자를 적용했을 때의 비용을 사전에 알고 있다면, 비용을 고려하여 최적의 탐색을 수행할 수 있음
- 탐색 비용을 사전에 알고 있다는 것을 전제로 함
- 실제로는 탐색 비용을 사전에 알고 있을 가능성이 크지 않음
알고리즘
- 시작 노드(A)를 OpenList에 추가하고 ClosedList와 비용 값(c(a) : 시작 노드에서 현재 탐색 대상 노드 a까지의 최단경로 비용 합) 초기화
- OpenList가 Null이면 탐색 중단
- OpenList의 가장 첫 요소 n을 가져와 ClosedList에 추가
- n이 목표 노드이면 탐색을 종료, 그렇지 않으면 다음 단계 진행
- n으로부터 1단계로 도달 가능한 자식 노드 b 중에 ClosedList에 포함되지 않은 것들을 OpenList에 넣고 각각에 대해서 비용값 c(b)를 계산, 이미 OpenList 안에 존재하는 노드의 비용값을 재계산하여 OpenList의 노드들의 비용값이 작은 순으로 재배열(가장 평가값이 좋은 프린지를 찾아 확장하기 위해)
- Step 2로 복귀하여 루프 수행
최고 우선 탐색(Best-first Search)
- 탐색 도중 다음에 나아갈 노드를 선택할 때 가능하면 목표까지 추정 비용이 작은 노드를 선택(탐색 비용을 추정함)
- 최적해는 보증할 수 없지만 최고해가 되도록 탐색을 수행
- 문제 해결을 유효 시간 안에 수행
- 현재 노드까지의 확정된 비용과 목표까지의 추정 비용을 함께 고려
알고리즘(최적 탐색과 동일하나, c(b)는 추정 함수임)
- 시작 노드(A)를 OpenList에 추가하고 ClosedList와 비용 값(c(a) : 시작 노드에서 현재 탐색 대상 노드 a까지의 최단경로 비용 합) 초기화
- OpenList가 Null이면 탐색 중단
- OpenList의 가장 첫 요소 n을 가져와 ClosedList에 추가
- n이 목표 노드이면 탐색을 종료, 그렇지 않으면 다음 단계 진행
- n으로부터 1단계로 도달 가능한 자식 노드 b 중에 ClosedList에 포함되지 않은 것들을 OpenList에 넣고 각각에 대해서 비용값 c(b)를 계산, 이미 OpenList 안에 존재하는 노드의 비용값을 재계산하여 OpenList의 노드들의 비용값이 작은 순으로 재배열(가장 평가값이 좋은 프린지를 찾아 확장하기 위해)
- Step 2로 복귀하여 루프 수행
균일 비용 탐색(노드 단위로 평가값을 비교)
- 최고 우선 탐색 알고리즘의 특수한 경우
- 이전에 탐색된 노드들의 대기열을 갖고 있으며, 비용 함수 f(n)이 각 노드에 적용(비용 정보를 가짐)
- 노드들을 f(n) 값 순서에 따라 OpenList에 배치
- 순서대로 추출(적은 비용을 가진 노드가 먼저 확정)
탐욕적 탐색(Greedy Search)
- 목표에 도달히기 위한 추정 소요 비용이 가장 낮은 노드를 확장시키는 것으로, 추정 함수로 경험 함수 h(n)을 사용한다.
- 항상 최적은 아니지만 양질의 해결책을 빠르게 찾을 수 있는 알고리즘이다.
- ex) 경로 탐색에서 경험 함수를 n에서 목표 간의 직선 거리로 설정하고, 직선 거리에 가장 가까운 경로를 선택
- 위의 경우 직선 거리는 가깝지만 실제 비용이 더 많이 드는 경우(최적 해가 아닌 경우)가 발생할 수 있음
A* 탐색(A-star Search)
- 최고 우선 탐색 알고리즘으로, 평가함수 f(n)은 경로비용 g(n)과 경험 함수 h(n)의 합으로 구성된다. 즉, 현재까지의 실제 거리에 대한 비용과 앞으로 남은 거리에 대한 추정 비용의 합이다.
- 경험 함수 h(n)은 실제로 알 수 없기 때문에 추정값인 h'(n)으로 대치하여 계산하는데, 이때 h'(n)보다 h(n)가 크거나 같을 경우(추정한 비용보다 실제 비용이 크거나 같을 경우), 알고리즘은 반드시 최적해를 보장한다(실제 최소 비용보다 같거나 작게 소요되었기 때문).
- (단점) 탐색한 노드에 인접한 노드의 평가값을 모두 조사하기 위해 문제에 따라 탐색 비용이 드는 경우도 있으며, 미탐색 노드를 보관할 필요가 있기 때문에 사용하는 메모리가 방대해진다(최대 깊이에 도달했는데도 해를 찾지 못하면 이전의 노드로 돌아가야 하므로).
IDA* 알고리즘
- 반복적 심화 깊이 우선 알고리즘과 유사하나 깊이 제한 값인 f-limit을 설정하여 탐색을 제한
- 탐색하고자 하는 노드가 제한 값보다 작으면 계속 수행, 제한을 넘으면 중단
적대적 탐색
- 2인 이상의 게임을 형식화하기 위한 프레임워크를 다루는 방법
- 게임의 참가자들이 스코어링 함수의 최대/최소화를 위한 시도 또는 이동 등의 행동을 하는 게임
- 2인 이상의 게임을 형식화하기 위한 프레임워크를 다룸
- 전제 조건 : 참가자들의 결탁은 없으며, 항상 승자와 패자로 구분(제로섬)되는 환경만을 고려
- 문제를 보다 쉽게 해결하기 위해 원래의 문제(원 문제)를 분할하여 작은 문제들(하위 문제)로 만듦, 하위 문제를 하나씩 해결하여 최종적으로 원문제를 해결하는 형태
AND/OR 그래프(하위 문제들의 그래프)
- AND 노드 : 복수의 하위 문제가 동시에 달성되지 않으면 원 문제가 해결되지 않음을 나타내며, 자식 노드와의 연결을 원호로 묶어서 표시
- OR 노드 : 복수의 하위 문제 중 어떤 하나가 달성되면 원문제가 해결되는 것을 나타내는 노드
- 터미널 노드 : AND/OR 그래프의 말단에 있는 (가장 작게 분할되어) 해결 가능한 노드, 터미널 노드가 모두 해결이 가능하다면 그때 얻어진 부분 그래프를 해 그래프라고 한다.
- 하나의 부모 노드에 대해 AND와 OR 노드가 같이 있을 때는 보조 노드를 도입하여 분할해야 함, A and B or C 일 때 A and B를 묶어 D라는 새로운 노드로 만들고 B or D의 관계를 구성함
문제의 재귀 표현
- 하위 문제가 재귀적인 요소를 포함하고 있을 경우, 소수의 하위 문제(의 반복)에 의해 원 문제가 해결될 가능성이 있음(
- 하노이 타워가 이런 방식으로 해결 가능하며, 수행 시간(순서) 순으로 하위 문제를 구분하고, 이 중 일부를 재귀적으로 활용
- 하노이타워의 형식화
- 연산자 1 : HANOI(n, x, y, z) - n장의 원반을 막대 x로부터 z를 이용하여 막대 y의 이동 행위를 표현
- 연산자 2 : MOVE(x, y) : 한 장의 원반을 막대 x로부터 막대 y로 이동하는 행위를 표현
- HANOI(n, A, C, B) = [HANOI(n-1, A, B, C) -> MOVE(A, C) -> HANOI(n-1, B, C, A)]의 재귀 형태로 표현 가능
게임 트리
- 컴퓨터와 대결하는 게임 등은 상대와의 상호작용에 의해 상태 공간이 지속적으로 변화함
- 상태 공간 속에서 상대의 행동을 예측하면서 최적의 해를 발견할 필요가 있음
- 최적의 해를 탐색하기 위해 게임 트리(Game Tree)라고 하는 AND/OR 그래프가 많이 사용됨
- 게임트리는 두 명의 플레이어가 교대로 플레이하며 게임을 진행해가는 천이 상태를 트리 구조로 표현한 것
- 선수의 국면 : 가능한 몇 가지 수 중 하나만을 실제로 둠(OR 노드)
- 후수의 국면 : 가능한 수는 후수에 의해 결정되고 선수는 알 수 없으므로 모든 수에 대응해야 함(AND 노드)
최소-최대 알고리즘(Mini-max)
- 자신과 상대방의 상호 득실을 고려한 게임 진행 방법을 실현한 것으로, 자신의 차례에서 평가값이 최대가 되도록 / 상대방의 차례에서 자신에 대한 평가값이 최소가 되도록(상대방이 선택할 수 있도록) Bottom-Up(말단의 노드부터 평가하여 시작지점으로) 전파
- 전제 조건 : 게임 트리에서 몇 수 앞의 평가값이 명확해야 함
- 바둑, 체스 등의 게임에서 활용될 수 있으며, 수읽기가 정확할수록, 더 많은 수를 읽을 능력이 있을수록 게임에서 유리함
- 게임 트리의 깊이에 따라 탐색에 걸리는 시간과 메모리가 많이 소요될 수 있음, 따라서 짧은 시간과 적은 메모리로 탐색을 수행하는 여러 탐색 방법이 고안되고 있음(α-β 가지치기 등)
- α-β 가지치기
- 최소 최대 알고리즘의 탐색 공간 크기 문제를 해결하기 위한 방법 중 하나로, 불필요한 탐색을 피함으로서 탐색의 효율화를 꾀하는 방법
- 종형 탐색(최소-최대 알고리즘의 기본적인 탐색 방식) 하에서 최대-최솟값이 교대로 취해지는 특성을 살려 게임 트리의 탐색공간을 제한
- β 가지치기 : 후수 차례에서 최소 평가값이 발견되면 이후에는 탐색이 필요치 않아 탐색을 종료함
- α 가지치기 : 선수가 두는 수에 의한 평가값의 최대화 국면에서 가지치기
잡스9급 PDF 교재
✽ 책 구매 없이 PDF 제공 가능
✽ adipoman@gmail.com 문의
✽ 유튜브 강의
반응형