탐색과 최적화 기법 (1)

3-1 상태 공간과 탐색

탐색

• 상태의 변화를 통해 문제의 해를 찾는 과정

상태 공간과 탐색의 중요 개념

• 상태 공간(State Space): 문제의 초기 상태부터 도달할 수 있는 모든 상태의 집합 또는 문제의 해가 될 가능성이 있는 상태들의 집합
• 탐색으로 해 구하기: 상태 공간을 체계적으로 탐색해 목표 상태에 도달하게 하는 일련의 동작을 찾거나 문제의 해가 되는 상태 자체를 찾는 것
• 상태 공간 그래프: 변하는 상태를 표현한 그래프

상태 공간 그래프의 예

3-2 탐색의 종류

맹목적 탐색(Blind Search)

• 문제의 상태 공간 정보를 이용하지 않고 정해진 순서에 따라 상태 공간 그래프를 생성하면서 순서대로 모든 경우를 탐색해 해를 찾는 것
• 깊이우선 탐색(Depth-First Search, DFS)
• 너비우선 탐색(Breadth-First Search, BFS)
• 반복적 깊이 심화 탐색(Iterative-Deepening Search)
• 양방향 탐색(Bidirectional Search)

정보 이용 탐색(Informed Search)

• 상태 공간에 대한 정보를 이용해 탐색 효율을 높이는 탐색
• 휴리스틱 탐색(Heuristic Search)이라고도 함
• 언덕 오르기 방법(Hill Climbing Method)
• 최상우선 탐색(Best First Search)
• 빔 탐색(Beam Search)
• A 알고리즘(A Algorithm)
• 다익스트라 알고리즘(Dijkstra Algorithm)
• ID3 알고리즘

게임 탐색(Game Search)

• 게임의 참가자가 이기기 위해 매순간 최고의 방법을 찾는 것을 모방
• 미니맥스 알파베타 가지치기(Minimax Alpha-Beta Pruning)
• 몬테카를로 트리 탐색

제약 조건 만족 문제(Constant Satisfaction Problem)

• 주어진 제약 조건을 만족하는 해를 찾는 것
• 백트래킹 탐색(Backtracking Search)
• 제약 조건 전파 방법(Constraint Propagation)

최적화(Optimization)

• 허용되는 값 중 주어진 기준을 가장 잘 만족하는 것을 찾는 것
• 조합 최적화(Combination Optimization)
• 계산 과정(Calculation Process)의 최적화
• 함수(Function) 최적화

3-3 맹목적 탐색

그래프 이론과 트리 구조

• 그래프: 점을 선으로 연결한 것

그래프의 종류

• 연결 그래프
• 비연결 그래프
• 유향 그래프
• 가중 그래프
• 무향 그래프

그래프 표현 방법

• 그림으로 표현
• 행렬로 표현
• 가중치를 그림과 행렬로 표현

트리의 구조와 탐색

• 트리구조: 그래프의 한 형태로, 그래프에 있는 여러 정점에서 출발점이 되는 정점으로 돌아가는 경로가 유일하며, 출발점이 되는 정점이 막다른 정점인 그래프

깊이우선 탐색

• 1단계: 정점A에서 깊이 우선 탐색 시작
• 2단계: A에 방문하지 않은 B,C가 있으므로, A를 스택에 넣고, 오름차순으로 B를 선택해 탐색 수행
• 3단계: B에 방문하지 않은 D, E가 있으므로 B를 스택에 넣고, 오름차순으로 D를 선택해 탐색을 수행
• 4단계: D에 방문하지 않은 G가 있으므로 D를 스택에 넣고, G를 선택해 탐색을 수행
• 5단계: G에 방문하지 않은 E가 있으므로 G를 스택에 넣고, E를 선택해 탐색을 수행
• 6단계: E에 방문하지 않은 C가 있으므로 E를 스택에 넣고, C를 선택해 탐색을 수행
• 7단계: C에 방문하지 않은 F가 있으므로 C를 스택에 넣고, F를 선택해 탐색을 수행
• 8단계: F에 방문하지 않은 곳이 없으므로 스택을 POP해 얻은 C에 방문하지 않은 곳이 있는지 확인함
• 9단계: C에 연결된 곳 중 방문하지 않은 곳이 없으므로 스택을 POP해 얻은 E에 방문하지 않은 곳이 있는 지 확인함
• 10단계: E에 연결된 곳 중 방문하지 않은 곳이 없으므로 스택을 POP해 얻은 G에 방문하지 않은 곳이 있는지 확인
• 11단계: G에 연결된 곳 중 방문하지 않은 곳이 없으므로 스택을 POP해 얻은 D에 방문하지 않은 곳이 있는지 확인
• 12단계: D에 연결된 곳 중 방문하지 않은 곳이 없으므로 스택을 POP해 얻은 B에 방문하지 않은 곳이있는지 확인
• 13단계: B에 연결된 곳 중 방문하지 않은 곳이 없으므로 스택을 POP해 얻은 A에 방문하지 않은 곳이 있는지 확인
• 14단계: A에서 방문하지 않은 인접 정점이 없으므로 스택을 POP해야 되는데, 스택이 공백이므로 깊이 우선 탐색을 종료

깊이 우선 탐색의 과정

• 깊이우선 탐색은 스택을 사용한다

너비우선 탐색

• 1단계: 정점A에서 너비 우선 탐색을 시작한다. 큐에 A를 넣음
• 2단계: 큐에서 A를 꺼내 1차로 연결된 곳에 방문하지 않은 B, C가 있으므로 B, C를 큐에 넣고, B를 선택해 탐색 수행
• 3단계: B에 1차로 연결된 곳에 방문하지 않은 D, E가 있으므로 D, E를 큐에 넣고 C를 선택해 탐색을 수행
• 4단계: C에 1차로 연결된 곳에 방문하지 않은 E, F가 있으므로 중복되는 E를 빼고, F를 큐에 넣고 D를 선택해 탐색을 수행
• 5단계: D에 1차로 연결된 곳에 방문하지 않은 G가 있으므로 G를 큐에 넣고 E를 선택해 탐색을 수행
• 6단계: E에 1차로 연결된 곳에 방문하지 않은 곳이 없으므로 큐에서 F를 선택해 탐색을 수행
• 7단계: F에 1차로 연결된 곳에 방문하지 않은 곳이 없으므로 큐에서 G를 선택해 탐색을 수행
• 8단계: G에 1차로 연결된 곳에 방문하지 않은 곳이 없으므로 큐에서 노드를 선택해야 하는데, 큐가 비어있으므로 종료

너비우선 탐색의 과정

• 너비우선 탐색은 큐를 사용한다

너비우선 탐색과 깊이우선 탐색 비교

 

 

 

 

 

※ 해당 내용은 <인공지능 바이블>의 내용을 토대로 학습하며 정리한 내용입니다.