탐색 2
03 May 2018
휴리스틱 기법 : 인삭의 사고와 유사하게 근사값 계산
경험이나 직관에 의해 효율적으로 해를 얻을 수 있다. 유일하지 않은 해를 갖으며, 최적의 해는 보장하지 않는다.
해의 결정에 허용치를 부과하는 방법이 유용하다. 새롭게 생성되는 노드들은 heuristic information에 따라 재조정한다.
평가 함수 (evaluation = objective = cost) function
확률, 거리, 차이 등을 활용한다.
-
hill climbing
평가 함수를 사용해 값이 optimize 되는 방향으로 탐색을 한다. 깊이 우선 탐색과 평가함수를 활용하며 local optimimum은 보장하지만 global optimum은 보장하지 않는다. 이는 과정 회복불가능 (irrevocable)하기 때문에 local optimum에서 중단한다. -
Back Tracking
어떤 노드의 가능성을 평가한다. 유망한 노드가 아니면 node의 parent node로 돌아가 다음 child node(현재의 sibling)을 분기한다. -
Branch & Bound
각 노드가 유효한지 검사 (직접 분기하지는 않는다) 한계 (Bound)를 계산해서 가능성이 있다면 분기한다. -
best-first
모든 말단 노드를 대상으로 평가 함수 값을 비교 최적 경로를 보장하지 않는다. (hill climbing에서 local이 나오면 중단하는 것과 대비)열린 노드를 모두 유지한다. -
A*알고리즘
f(n) = g(n) + h^(n)
평가함수를 활용하는 알고리즘이다. 시작에서 현재까지 비용 g(n) + 현재부터 목표까지 비용 h(n)을 계산해서 최적을 선택한다. h(n)은 미래의 비용이므로 실값을 계산할 수 없어서 근사값을 사용한다.
게임 탐색 트리
상호 배타적인 환경에서 승리하기 위한 경로 탐색으로 완벽한 평가함수를 구할 수 없다. 따라서 휴리스틱 방법을 적용한다.
Min Max Search w/ 알바 - 베타 pruning
minimizer과 maximizer를 가정해서 사용한다. 몇 수 앞을 보느냐에 따라 전략이 달라진다. 탐색 영역을 축소하기 위해 ‘알바 - 베타 pruning’을 사용한다. 이는 다음 단계의 예상 값중 최소의 최대와 최대의 최소를 비교해서
최소의 최대가 최대의 최소보다 작으면 더 이상 탐색을 하지 않는 방법이다.
Constraint Satisfation Problems
제약 조건들을 만족하는 경우를 탖는 방법으로 N-Queen이 대표적인 문제다