2022. 9. 15. 00:56ㆍ학부 강의/AI 입문
탐색 (search)
문제에 대한 최적의 해를 찾는 것.
문제의 해가 될 수 있는 후보 해의 집합 또는 공간을 체계적으로 검사.
용어 정리
- 세계 : 문제에 포함된 대상들과 이들의 상황을 포괄적으로 지칭
- 상태 : 특정 시점에 문제의 세계가 처해 있는 모습
- 상태 공간 : 문제 해결 과정에서 초기 상태로부터 도달할 수 있는 모든 형태들의 집합. 문제의 해가 될 가능성이 있는 모든 상태들의 집합
가. 상태 공간 트리
트리 (tree)
이미지 출처 : https://ko.wikipedia.org/wiki/트리_구조
계층적 구조 표현.
- 노드 (node) : 정보
- 간선 (edge) : 관계
상태 공간 트리
상태 공간에서 각 액션에 따른 상태의 변화를 나타낸 트리
나. 상태 공간 그래프
그래프 (graph)
이미지 출처 : https://en.wikipedia.org/wiki/Graph_theory
연결되어 있는 객체 간의 관계를 표현하는 자료구조
- 노드 (node) : 정보
- 간선 (edge) : 관계
- 사이클 (cycle) : 존재
상태 공간 그래프
상태 공간에서 각 액션에 따른 상태의 변화를 나타낸 그래프
대부분의 문제에서는 미리 상태 공간 그래프를 만들기 어렵다.
탐색 과정에서 그래프를 점진적으로 생성.
상태 공간 트리에서 해는 초기 상태에서 목표 상태로의 경로다.
탐색 방식의 종류
맹목적 탐색
정해진 순서에 따라 상태 공간 전체를 검사하면서 해를 탐색하는 방법
주요 기법
- 깊이 우선 탐색 (depth-first-search, DFS)
- 너비 우선 탐색 (breadth-first-search,)
- 반복적 깊이 심화 탐색 (iterative deepening search)
- 깊이의 한계를 설정하고 깊이 우선 탐색을 반복적으로 적용
- 양방향 탐색 (bidirectional search)
- 초기 노드와 목적 노드에서 동시에 너비 우선 탐색을 진행
- 중간에 만나도록 하여 초기 노드에서 목표 노드로의 최단 경로를 찾는 방법
| 탐색 방법 | 장점 | 단점 |
|---|---|---|
| 깊이 우선 탐색 | 메모리 공간 사용 효율적 | 최단 경로 해 탐색 보장 불가 (무한 루프) |
| 너비 우선 탐색 | 최단 경로 해 탐색 보장 | 메모리 공간 사용 비효율 |
| 반복적 깊이 심화 탐색 | 최단 경로 해 탐색 보장. | |
| 메모리 공간 사용 효율적. | 상대적으로 복잡 | |
| 양방향 탐색 | 최단 경로 해 탐색 보장 | 메모리 공간 사용 비효율 |
| 상대적으로 복잡 |
정보이용탐색
탐색 과정에 문제 영역에 대한 정보나 지식을 사용해 탐색을 최적화.
휴리스틱 탐색 (heuristic)이라고 하기도 한다.
주요 기법
- 언덕 오르기 기법
- 최상 우선 탐색
- 빔 탐색
- A* 알고리즘
언덕 오르기 기법
같은 평가값 중 하나만 선택하고 나머지는 기억하지 않는다.
그래서 해 혹은 최단 경로를 찾지 못할 수 있다.
최상 우선 탐색 & 빔 탐색
둘은 같은 평가값 중 하나만 선택하고 나머지는 버리는 언덕 오르기 기법과는 다르다.
최상 우선 탐색의 경우 동일 값은 저장 후 추후 탐색한다.
빔 탐색의 경우 매 계층마다 평가값이 우수한 상위 N개의 노드만을 선택해서 최상 우선 탐색을 적용한다.
A* 알고리즘
이미 투입된 비용 g(n)과 목표까지 남은 비용 h(n)의 합이 최소가 되도록 탐색한다.
게임 탐색
상대가 있는 게임에서 자신과 상대방의 각각에 대해 가능한 게임 상태를 나타낸 트리
일반적으로 많은 수를 볼 수록 유리한다.
게임 트리 탐색의 경우 모든 경우의 수를 탐색할 수 없다.
승리할 가능성(판세)가 더 큰 전략을 추구한다.
주요 기법
- mini-max 알고리즘
- alpha-beta 가지치기
- 몬테칼로 트리 검색
mini-max 알고리즘
각자 판세를 계산해서 서로에게 가장 좋은 선택을 반복하는 알고리즘이다.
- MAX 노드 : 자신에게 가장 유리한 값
- MIN 노드 : 상대방에게 유리하고 자신에게 불리한 값
alpha-beta 가지치기
우선 이해를 위한 참고 영상을 보고 오자.
참고 영상 : https://www.youtube.com/watch?v=iNorDNQ_IF4
쉽게 설명하면 깊이를 제한한 깊이 우선 탐색을 통하여 가능한 MAX 노드를 찾는다.
이때 상대와 자신의 상호작용으로 인하여 가능성이 없는 가지는 탐색에서 제외한다.
치열한 이해의 현장?
살려줘요...
'학부 강의 > AI 입문' 카테고리의 다른 글
| 2022-10-13 AI입문_6 (0) | 2022.10.13 |
|---|---|
| 2022-10-05 AI입문_5 (0) | 2022.10.05 |
| 2022-09-28 AI입문_4 (0) | 2022.09.29 |
| 2022-09-20 AI입문_3 (1) | 2022.09.20 |
| 2022-09-08 AI입문_1 (0) | 2022.09.08 |