[인공지능]2. 탐색

목차
1. 탐색
2. 상태공간의 예
3. 탐색 트리
4. 기본적인 탐색 기법
5. 맹목적인 탐색 #1: 깊이 우선 탐색(DFS)
6. 맹목적인 탐색 #2: 너비 우선 탐색(BFS)
7. DFS와 BFS 프로그램
8. 경험적 탐색 방법
9. 언덕등반 기법(Hill-Climbing)
10. 최고 우선 탐색
11. A* 알고리즘

---

1. 탐색
탐색(search)이란 상태공간에서 시작상태에서 목표상태까지의 경로를 찾는 것
상태공간(state space): 상태들이 모여 있는 공간
연산자: 다음 상태를 생성하는 것
초기 상태
목표 상태

2. 상태공간의 예
8-puzzle: 섞여 있는 타일을 옮겨 순서대로 배치하는 게임
하노이 탑: 기둥에 꽂혀 있는 원판을 다른 원판에 옮기는 게임

3. 탐색 트리
상태 = 노드(node)
초기 상태 = 루트 노드
연산자 = 간선(edge)

참고: 연산자를 적용하기 전까지는 탐색 트리는 미리 만들어져 있지 않음

4. 기본적인 탐색 기법

• 맹목적인 탐색(Blind Search Method): 목표 노드에 대한 정보를 이용하지 않고 기계적인 순서로 노드를 확장하는 방법으로 매우 소모적인 탐색을 수행. >> 탐색 방법에서 노트 확장 순서만 달라지는 경우가 많은 uniformed search
  • 깊이 우선 탐색
  • 너비 우선 탐색
  • 균일 비용 탐색
• 경험적 탐색 방법(Heuristic Search Method): 목표 노드에 대한 경험적인 정보를 사용하는 방법 >> 효율적인 탐색 가능
  • 탐욕적인 탐색
  • A* 탐색

5. 맹목적인 탐색 #1: 깊이 우선 탐색(DFS)
깊이 우선 탐색(depth-first search)은 탐색 트리 상에서, 해가 존재할 가능성이 존재하는 한, 앞으로 계속 전진하여 탐색하는 방법이다.
장점: 구현이 쉽다.
단점: 굉장히 비효율적일 수 있다.

탐색에서는 중복된 상태를 막기 위하여 다음과 같은 2개의 리스트를 사용한다.

• OPEN 리스트: 확장은 되었으나 아직 탐색하지 않은 상태들이 들어 있는 리스트
• CLOSED 리스트: 탐색이 끝난 상태들이 들어 있는 리스트

Algorithms

depth_first_search() open = [시작노드] closed = [] while open != [] do X = open 리스트의 첫 번째 요소 if X == goal then return SUCCESS else X의 자식 노드를 생성한다. X를 closed 리스트에 추가한다. X의 자식 노드가 이미 open이나 closed에 있다면 버린다. 남은 자식 노드들은 open의 처음에 추가한다.(스택처럼 사용) return FAIL

6. 맹목적인 탐색 #2: 너비 우선 탐색(BFS)
루트 노드의 모든 자식 노드들을 탐색한 후에 해가 발견되지 않으면 한 레벨 내려가서 동일한 방법으로 탐색을 계속하는 방법이다.
Algorithms

breadth_first_search() open = [시작노드] closed = [] while open != [] do X = open 리스트의 첫 번째 요소 if X == goal then return SUCCESS else X의 자식 노드를 생성한다. X를 closed 리스트에 추가한다. X의 자식 노드가 이미 open이나 closed에 있다면 버린다. 남은 자식 노드들은 open의 끝에 추가한다.(큐처럼 사용) return FAIL

7. DFS와 BFS 프로그램

# 상태를 나타내는 클래스 class State: def __init__(self, board, goal, moves=0): self.board = board self.moves = moves self.goal = goal # i1과 i2를 교환하여서 새로운 상태를 반환한다. def get_new_board(self, i1, i2, moves): new_board = self.board[:] new_board[i1], new_board[i2] = new_board[i2], new_board[i1] return State(new_board, self.goal, moves) # 자식 노드를 확장하여서 리트에 저장하여서 반환한다. def expand(self, moves): result = [] i = self.board.index(0) # 숫자 0(빈칸)의 위치를 찾는다. if not i in [0, 1, 2]: # UP 연산자 result.append(self.get_new_board(i, i - 3, moves)) if not i in [0, 3, 6]: # LEFT 연산자 result.append(self.get_new_board(i, i - 1, moves)) if not i in [2, 5, 8]: # RIGHT 연산자 result.append(self.get_new_board(i, i + 1, moves)) if not i in [6, 7, 8]: # DOWN 연산자 result.append(self.get_new_board(i, i + 3, moves)) return result # 객체를 출력할 때 사용한다. def __str__(self): return str(self.board[:3]) + "\n" + \ str(self.board[3:6]) + "\n" + \ str(self.board[6:]) + "\n" + \ "--------------------" # 초기 상태 puzzle = [1, 2, 3, 0, 4, 6, 7, 5, 8] # 목표 상태 goal = [1, 2, 3, 4, 5, 6, 7, 8, 0] # open 리스트 open_queue = [] open_queue.append(State(puzzle, goal)) closed_queue = [] moves = 0 while len(open_queue) != 0: # 디버깅을 위한 코드 # print("START OF OPENQ") # for elem in open_queue.queue: # print(elem) # print("END OF OPENQ") current = open_queue.pop(0) # OPEN 리스트의 앞에서 삭제 print(current) if current.board == goal: print("탐색 성공") break moves = current.moves + 1 closed_queue.append(current) for state in current.expand(moves): if (state in closed_queue) or (state in open_queue): # 이미 거쳐간 노드이면 continue # 노드를 버린다. else: open_queue.append(state) # OPEN 리스트의 끝에 추가

8. 경험적 탐색 방법

• 경험적 탐색 방법(heuristic search method): 문제 영역에 대한 정보나 지식을 사용하여 탐색 작업 수행
• 이때 사용되는 정보를 휴리스틱 정보(heuristic information)라고 한다.
• 8-puzzle에서 경험적 탐색

9. 언덕등반 기법(Hill-Climbing) - 노드의 평가 함수 값 활용

• 평가 함수의 값이 좋은 노드를 먼저 처리
• 평가 함수로 제 위치에 있지 않은 타일의 개수 사용
• 경험적인 탐색 방법은 무조건 휴리스틱 함수 값이 가장 좋은 노드만 선택
• 이것은 등산할 때 무조건 현재의 위치보다 높은 위치로만 이동하는 것과 같다.
• 일반적으로는 현재의 위치보다 높은 위치로 이동하면 산의 정상에 도달할 수 있다.

Algorithms
1. 먼저 현재 위치를 기준으로 해서, 각 방향의 높이를 판단한다.(노드의 확장)
2. 만일 모든 위치가 현 위치보다 낮다면 그 곳을 정상이라고 판단한다.(목표상태인가의 검사)
3. 현 위치가 정상이 아니라면 확인된 위치 중 가장 높은 곳으로 이동한다.(후계노드의 선택)

Local Minima Problem

• 순수한 언덕 등반 기법은 오직 h(n) 값만을 사용한다.(OPEN 리스트나 CLOSED 리스트도 사용하지 않는다)
• 이런 경우에는 생성된 자식 노드의 평가함수 값이 부모 노드보다 더 높거나 같은 경우가 나올 수 있다. 이것을 지역 최소 문제(local minima problem)라고 한다.

10. 최고 우선 탐색

• 언덕 등반 기법을 개선 >> 평가 함수와 open/closed list도 함께 사용
• open 리스트에서 다음 처리할 노드를 선택할 때, 기계적 순서가 아닌 평가 함수 값이 가장 좋은 노드를 선택하여 처리

Algorithms

best_first_search() open = [시작노드] closed = [] while open != [] do X = open 리스트에서 평가 함수의 값이 가장 좋은 노드 if X == goal then return SUCCESS else X의 자식 노드를 생성한다. X를 closed 리스트에 추가한다. if X의 자식 노드가 open이나 closed에 있지 않으면 자식 노드의 평가 함수 값을 계산한다. 자식 노드들을 open에 추가한다. return FAIL

11. A* 알고리즘 - 최소 비용 경로 찾기

• 최고 우선 탐색은 목표 노드와의 차이 h(n)만을 고려 >> 그러나 시작 노드에서 멀어지면 그만큼 비용이 추가로 발생 >> 경로의 비용도 평가 함수에 추가
• A* 알고리즘의 평가 함수
  • f(n) = g(n) + h(n)
  • h(n): 현재 노드에서 목표 노드까지의 거리
  • g(n): 현재 노드에서 목표 노드까지의 비용

Algorithms

AStar_search() open = [시작노드] closed = [] while open != [] do X = open 리스트에서 가장 평가 함수의 값이 좋은 노드 if X == goal then returns SUCCESS else X의 자식 노드를 생성한다. X를 closed 리스트에 추가한다. if X의 자식 노드가 open이나 closed에 있지 않으면 자식 노드의 평가 함수 값 f(n) = g(n) + h(n)을 계산한다. 자식 노드들을 open에 추가한다. return FAIL

import queue # 상태를 나타내는 클래스, f(n) 값을 저장한다. class State: def __init__(self, board, goal, moves=0): self.board = board self.moves = moves self.goal = goal # i1과 i2를 교환하여서 새로운 상태를 반환한다. def get_new_board(self, i1, i2, moves): new_board = self.board[:] new_board[i1], new_board[i2] = new_board[i2], new_board[i1] return State(new_board, self.goal, moves) # 자식 노드를 확장하여서 리스트에 저장하여서 반환한다. def expand(self, moves): result = [] i = self.board.index(0) # 숫자 0(빈칸)의 위치를 찾는다. if not i in [0, 1, 2]: # UP 연산자 result.append(self.get_new_board(i, i - 3, moves)) if not i in [0, 3, 6]: # LEFT 연산자 result.append(self.get_new_board(i, i - 1, moves)) if not i in [2, 5, 8]: # RIGHT 연산자 result.append(self.get_new_board(i, i + 1, moves)) if not i in [6, 7, 8]: # DOWN 연산자 result.append(self.get_new_board(i, i + 3, moves)) return result # f(n)을 계산하여 반환한다. def f(self): return self.h() + self.g() # 휴리스틱 함수 값인 h(n)을 계산하여 반환한다. # 현재 제 위치에 있지 않은 타일의 개수를 리스트 함축으로 계산한다. def h(self): return sum([1 if self.board[i] != self.goal[i] else 0 for i in range(8)]) # 시작 노드로부터의 경로를 반환한다. def g(self): return self.moves # 상태와 상태를 비교하기 위하여 less than 연산자를 정의한다. def __lt__(self, other): return self.f() < other.f() # 객체를 출력할 때 사용한다. def __str__(self): return "-------------------- f(n)=" + str(self.f()) + "\n" + \ "-------------------- h(n)=" + str(self.h()) + "\n" + \ "-------------------- g(n)=" + str(self.g()) + "\n" + \ str(self.board[:3]) + "\n" + \ str(self.board[3:6]) + "\n" + \ str(self.board[6:]) + "\n" + \ "--------------------" # 초기 상태 puzzle = [1, 2, 3, 0, 4, 6, 7, 5, 8] # 목표 상태 goal = [1, 2, 3, 4, 5, 6, 7, 8, 0] # open 리스트는 우선순위 큐로 생성한다. open_queue = queue.PriorityQueue() open_queue.put(State(puzzle, goal)) closed_queue = [] moves = 0 while not open_queue.empty(): # 디버깅을 위한 코드 # print("START OF OPENQ") # for elem in open_queue.queue: # print(elem) # print("END OF OPENQ") current = open_queue.get(0) print(current) if current.board == goal: print("탐색 성공") break moves = current.moves + 1 for state in current.expand(moves): if state not in closed_queue: open_queue.put(state) closed_queue.append(current) else: print("탐색 실패")