* 탐색의 개요
- 문제 풀이 바업
> 절차 기반 : 성공 보장이 가능한 절차를 사용(확실한 절차가 존재한다). 이 절차는 알고리즘 형태로 변환이 가능하다.
> 탐색 기반 : 계산적인 방식으로 거의 해결이 불가능한 실세계 무제들에 대해 해를 구하는 방법. 인공지능의 접근이 필요.
- 탐색 방법의 성능 평가
> Cost : 최소한의 노력으로 얼마나 빨리 해를 발견하는가?
※ 탐색의 속도에 영향을 주는 것
1) 해를 발견하는데 방문한 실제 노드의 수
2) 해를 발견하기 위해 Backtracking을 최소화로 하는 것이 바람직함
> Good solution(좋은해) : 최적해에 가까운 해를 발견하는가?
※ 최적해와 좋은해
1) 최적해 : 해중에서 가장 좋은 것으로, 대부분 소모적인 탐색이 필요하다.
2) 좋은해 : 제약 조건을 만족하는 해로 보다 우수한 해의 존재여부와 관계 없이 쓸만한 해.
짧은 시간내에 허용 범위 내에 있는 해.
- 특정 경로를 찾을 때에는 사이클을 허용하지 않는다.
* 탐색 방법
- 매 단계마다 고민해야할 문제이며 정보의 양에 의해서 분류가 가능하다.
1) 망라적 탐색 : 정보가 없는 상태에서 탐색하는 것으로, 정보의 양이 많고 모든 경우를 다 따진다.
(깊이 우선 탐색/넓이 우선 탐색)
> 다음단계로 넘어갈 때 어디가 효율적인지를 알 수 없다.
> 깊지 않은 곳에 해가 있을 것이라고 추정 되며, 최적해 탐색이 목적일 경우 너비 우선 탐색을 실시
> 해가 왼쪽편 깊은 곳에 존재할 것이라고 추정될 경우 사용되며, 좋은해라도 무방할 경우 깊이 우선 탐색을 실시
> 문제점 : 소규모 문제에는 적용이 가능하지만, 대규모 문제에서는 실용적이지 않음.
연산시간 및 컴퓨터의 메모리 제한에 걸림.
2) 휴리스틱 탐색 : 정보의 양이 많고, 가능한 경우 중 좋은 것을 선택하여 다음 단계로 넘어간다.
> 경험적 지식(완벽한 정보는 아니지만, 대부분의 경우 유용하게 사용 가능한 경험적 지식)을 이용하여 탐색
> 목표 상태를 보다 신속하게 탐색하기 위해 경험적 지식을 활용하여 탐색하는 방법으로 평가함수를 사용
※ 평가 함수(가능성의 수치화)
> 탐색과정에서 노드들의 확장 순서를 정한다.
> 확장 시킬 노드들에 순위를 매겨 목표 노드까지의 최상의 경로가 있을 만한 것을 선택한다.
> 해로 가는데 필요한 비용 및 가능성을 계산하는 함수이다.
* 휴리스틱 탐색의 예) 언덕 오르기 탐색
- 언덕을 오르는 탐색 방법을 휴리스틱으로 푸는 방법을 알아보자.
1) 언덕 오르기 탐색(Hill-climbing search)
- 목표상태 : 언덕의 꼭대기
- 목적함수 : 언덕의 꼭대기에 가장 빨리 도달할 수있는 다음 노드를 선택
- 트리를 확장하는 방법을 사용하며 깊이 우선탐색과 휴리스틱을 이용
> 평가함수 : 목표까지 남아 있는 거리
- 특징
> 현재까지 도달한 비용은 생각하지 않는다. 오직 앞으로 남은 목표까지의 비용중 가장 작은 것만 선택
> 현재 진행중인 경로만 우선적으로 탐색한다.
> 남은 목표까지의 비용은 아직 가보지 못했기 때문에 정확한 값을 유추 할 수 없다. 예측비용으로 대체해서 사용한다.
- 문제점
ⓐ 지역극대값 : 정상이 아닌 다른 봉오리에 오르게 되면 정상으로 향할 수 없다.
ⓑ 평원 : 이동중 고도가 모두 같은 평원에 도착하면 이동이 불가능하다.
ⓒ 산등성이 : 양쪽다 높아지는 지형에 도착하면 오판으로 인해서 정상과 반대쪽으로 오를 수 있다.
2) 최적 우선 탐색(best-first search)
- 언덕 오르기 탐색의 문제점을 해결하기 위해서 나온 방법
- 여러 팀이 협동하여 움직이는 것으로 각 팀중 가장 좋은 방법을 계속 실시
- 현재까지 온 값에 기대 값을 더해서 우선순위를 정한다.
- Good solution을 보장한다.
* 게임에서의 탐색
- 혼자하는 것 : General problem solve로 해결 가능
- 서로 같이 하는 것 : 트리 형식으로 예측, 여기서 사용하는 트리를 특별히 게임트리라고 한다.
- 함께 적절히 사용하는 것이 효과적이다.
- 저장된 페턴의 데이터 베이스를 사용하여 게임을 최적으로 수행
- MINMAX 프로시저와 ALPHA-BETA 절단 기법이 존재한다.
ⓐ MINMAX 프로시저
- 이는 각각의 상황을 수치화하여 자신이 유리한 상황일 수록 큰 수를 부여한다.
- 넓이 우선 탐색을 이용해여 n수 앞을 바라보아서 다음 수를 어디에 두어서 상대방이 두어도 유리한지를 판단하는 방식이다.
이 예에서 현재 2수 앞을 바라본 상태이다. 2수 앞을 바라볼 경우 7이라는 수가 가장 커서 그쪽이 유리해 보이기도 한다.
하지만, 그의 형제 노드에 -2라는 자신에게 불리한 수도 존재한다. 즉 자신이 7을 바라보고 두었을 때 오히려 불리해 질
수 도있다. 이 단계를 MIN단계에서 걸러준다. MAX단계는 자신이 두었을 때 자신이 이길 확률이 높아지는 쪽을 걸러내주는
곳이 된다. 즉, MINMAX는 승리를 향해서 안정적이며 확실한 경로를 탐색하는 것이다.
ⓑ Alpha-Beta 절단 기법 / 가지치기 기법
MINMAX에서 속도향상을 위해서 가지를 치는 방식이다. 이는 깊이 우선을 기반으로 내려간 값을 통해서 크고 작음을
판별하여 그 노드에 속한 형제 노드를 삭제하는 방식이다. MAX와 MAX 단계를 비교하고, MIN과 MIN단계를 비교하는 것이다.
(이에 대해선 아직 불확실한 요소가 있으므로, 나중에 추가하도록 하겠다.)