탐색과 추론

본 내용은 인공지능의 이해의 내용을 참조하여 작성하였습니다.

탐색과 추론

우리는 문제에 직면했을 때 이를 해결하려한다.
이때, 여러가지 접근법을 이용하여 해결하는데 이 사고는 컴퓨터 알고리즘에서도 비슷하게 적용 된다.

하나의 문제에 대해 한가지의 방법으로 해결하는 것이 아닌 여러 방법을 적용해 본다.
이와 같이 문제에 대해 적절한 해답을 찾는 것을 탐색 기법이라고한다.
문제에 대해 여러 접근 방법이 있듯이 탐색 기법에도 여러가지가 존재한다.

1. 맹목적 탐색
2. 정보 이용 탐색
3. 게임 탐색
4. 제약조건 만족 문제
5. 최적화
6. 몬테카를로 방법

맹목적 탐색

맹목적 탐색은 문제에 대한 특성을 고려하지 않고 일정한 순서에 따라 탐색하는 것을 말한다.

이 방법은 크개 2가지의 방법이 존재한다.
깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) 이다.

깊이 우선 탐색(DFS)

깊이 우선 탐색은 루트 노트에 연결된 경로 중 하나를 선택해 막다른 다른 노드에 도착할 때까지 탐색한다. 이후, 이 전 노드로 이동해 다음 막다른 노드까지의 탐색을 반복하는 기법이다.

이때, 막다른 노드에 직면했을 때 이 전 노드로 돌아가는 것을 백트래킹이라 한다.

너비 우선 탐색(BFS)

너비 우선 탐색은 루트 노드와 연결 된 노드를 모두 탐색한 후 다음 깊이의 노드들을 전부 탐색하는 과정을 반복하는 기법이다.

두 탐색기법은 각각의 장단점을 갖고 있다.
깊이 우선 탐색의 경우 탐색 중간중간에 백트래킹 기법을 사용하므로 속도면에서 너비 우선탐색보다 느리지만,
깊이 만큼의 메모리만 사용해 너비 만큼의 메모리가 필요한 너비 우선탐색보단 메모리 효율이 좋다.
너비 우선 탐색의 경우 깊이 우선 탐색과 반대적 특성을 지닌다.

여기서, 두 개의 장점만 이용해서 탐색하고 싶다는 생각이 들것이다.
이를 구현한것이 바로 반복적 깊이 심화 탐색이다.

반복적 깊이 심화 탐색

반복적 깊이 심화 탐색은 깊이 우선 탐색을 기반으로 깊이 한계를 조정하여 실행하는 탐색 방법이다.

정보 이용 탐색

우리는 문제에 대해 모든 가능한 요소를 찾아볼 수 없기 때문에, 적절한 값을 대입하여 문제를 해결하게 된다. 이때, 이와 같은 방법을 휴리스틱이라고 한다.

휴리스틱

휴리스틱은 시간이나 정보가 불충분하여 합리적인 판단을 할 수 없거나 굳이 체계적이고 합리적인 판단을 할 필요가 없는 상황에서 어림짐작하여 탐색하는 기법을 말한다.
하지만, 검색 효율은 좋으나 최적해를 찾을 수 있다는 보장을 하지 못한다.

정보 이용 탐색은 크게 4가지로 구성된다.
언덕오르기 방법, 최선 우선 탐색, 빔 탐색, A* 알고리즘

언덕오르기 방법

언덕오르기 방법은 현재 노드에서 휴리스틱 평가 값이 가장 좋은 이웃 노드로 확장해서 탐색하는 기법이다.

최선(최장) 우선 탐색

최선 우선 탐색은 확장 중인 노드들 중 목표 노드까지 거리가 가장 짧은 노드를 확장하여 탐색 기법이다.

빔 탐색

빔 탐색은 휴리스틱을 사용하여 가장 평가 값이 준수한 노드들만 확장하여 탐색하는 기법이다.

A* 알고리즘

A* 알고리즘은 주어진 문제의 초기 상태에서 목적 상태까지 소요되는 전체 비용이 최소인 노드를 확장해 가면서 해를 찾는 방법이다.

게임이론

게임이론은 상대방과 내가 게임을 하여 얻을 수 있는 점수를 트리 형태로 만든 이론이다.

게임이론은 크게 3가지로 구성된다.
mini-max 게임 트리, 알파-베타 가지치기

mini-max 알고리즘

mini-max 알고리즘은 게임이 끝나고 나서 일정 깊이까지의 값을 계산하여 가장 최적의 경로를 탐색하는 기법이다.

알파-베타 가지치기

알파-베타 가지치기는 mini-max 알고리즘 단점 해결하기 위해 등장한 방법으로,
일정 깊이의 게임 트리 생성 후 자르기 기법을 이용하여 불필요한 부분은 탐색에제 제외하는 기법이다.

이때, 자르기의 기법은 두 개로 나눠진다.

• 알파-자르기 : 최소 점수를 선택하면서 부모노드 보다 작은 점수는 검색 대상에서 제외
• 베타-자르기 : 최대 점수를 선택하면서 부모노드 보다 큰 점수는 탐색 대상에서 제외

제약 조건 만족 문제

제약 조건 만족 문제는 조건을 만족하는 문제의 해를 찾는 방법이다.
이때, 제약 조건을 만족하지 않는 상태들은 탐색시 제외한다.

제약 조건 만족문제는 두 개로 나눠진다.
백트랙킹, 제약 조건 전파

백트랙킹

백트랙킹은 깊이 우선 탐색에서 변수를 하나식 대입하여 해를 찾는다.
이때, 한 번에 한 변수의 값을 선택하여 적용할 값이 없는 변수가 발견되면 역추적으로 탐색하고 해의 가능성이 없는 것은 미리 잘라버리는 방법이다.

제약 조건 전파

제약 조건 전파는 인접 변수 간 제약 조건에 따라 각 변수에서 허용되지 않는 값들을 제거하는 방법이다.

최적화

최적화는 허용된 값들 중 주어진 기준을 가장 잘 만족하는 것을 찾는 방법이다.

대표적인 예로는 유전 알고리즘, 최소제곱평균법, 경사하강법이 있다.

유전 알고리즘

유전 알고리즘은 생물 진화를 모방해서 만든 집단 기반의 확률적 탐색 기법으로,
계산을 여러번 반복해 궁극적인 결과에 수렴하도록 하는 기법이다.

이때, 새로운 개체를 혼합하는 교차 방법을 사용하거나 새로운 개체를 생성 돌연변이 방법을 이용하여 궁극적인 결과에 수렴하게 한다.

최소제곱평균법

최소제곱평균법은 수치적인 접근 방식으로,
관측 오차 및 시스템의 불확정성으로 인한 오차를 최소화 하는 방법이다.

경사하강법

경사하강법은 함수의 최소값을 구하는 과정에서 각 지점에서의 기울기를 구해 손실함수를 최소화 하는 지점을 찾아 가는 방법이다.

몬테카를로 방법

몬테카를로 방법은 무작위 시뮬레이션을 이용해 형세에 유리한 정도를 결정하여 게임 트리를 구성하는 기법이다.

이때, 게임에서의 단말노드의 형세를 평가 하기위해 여러가지 기법을 사용하는데
대표적인 것이 선택, 확장, 시뮬레이션, 역전파이다.

• 선택 : 승산 있는 다음 노드 선택
• 확장 : 트리가 없을 시 자식 노드로 확장
• 시뮬레이션 : 해당 노드에서 무작위로 게임 수행
• 역전파 : 해당 경로의 노드 정보 수정