탐색 (Search)

• 탐색 (Search) : 상태 공간에서 시작 상태(초기 상태)에서 목표 상태까지의 경로
• 상태 공간 (State Space) : 상태들이 모여있는 공간
• 연산자 : 다음 상태를 생성하는 것

Blind Search (맹목적 탐색, Uninformed Search)

 Blind Search란, 현재 상태에서 목표 상태까지의 Step 개수(Path Cost)를 모르는 것을 의미한다. 다시 말해, Blind Search에서는 현재 상태에서 목표 상태까지 얼마나 남았는지 보여주는 함수인 H(n)을 계산하지 않는다. 이러한 특성으로 인해 최적 해에 도달하기 어렵다는 단점이 존재한다.

 Blind Search는 경험적으로 분석을 할 수 없기에 Goal State로 탐색이 진행될 때 각 Search들만의 규칙을 가지고 탐색하긴 하지만, 현재 State에서 Goal까지의 Path Cost를 구할 수 없기에 모든 방향으로 뻗어나가고, 무한 루프에 빠질 가능성이 존재한다.

 Blind Search의 예시에는, Breath-First Search (너비 우선 탐색), Uniform-Cost Search (일정 비용 탐색), Depth-First Search (깊이 우선 탐색), Depth-Limited Search (깊이 제한 선택), Iterative Deepening Search (점차적 깊이 제한 탐색), Bidirectional Search (양방향 탐색) 등이 존재한다.

Heuristic Search (경험적 탐색, Informed Search)

 Heuristic Search란, 어떤 상태가 목표 상태로 가는 데 적합한지를 아는 것을 의미한다. 이는 맹목적 탐색의 단점을 극복하기 위해 탄생한 탐색법으로, Solution을 좀 더 효율적으로 찾을 수 있다는 장점이 존재하며, 대체로 Uninformed Search보다 효율적이다.
Best-First Search, A* Search, Hill Climbing이 Heuristic Search의 대표적인 예시이며, 이때, Best-First Search가 가장 기본적인 접근 방법이며, 대다수의 경험적 탐색 알고리즘의 기반이 된다.

• Best-First Search는 평가 함수 F(n)을 기반으로 한 Tree/Graph Search의 확장으로, 평가 함수는 G(n)과 H(n)으로 구성되며, 이는 n부터 Goal State까지의 비용(=거리)을 의미함.
  • G(n) : 시작 노드에서 현재 노드까지 걸린 Path Cost
  • H(n) : 현재 노드에서 목표 노드까지의 가장 빠른 거리
  • (ex) 현재 위치 = 목표 노드, H(n) = 0
• Greedy Best-First Search에서 그리디는 '탐욕적인'이라는 의미로, 현재 상태에서 가장 좋아보이는 것을 선택해 최적인지 아닌지를 항상 확인하는 알고리즘이며, 평가 함수는 오직 H(n)만으로만 구성됨. (G(n)으로만 구성되면 Uniform-Cost Search)
• A* Search의 평가 함수식은 F(n) = H(n) + G(n)으로 구성되며, 결과적으로 Optimal하고 Complete함.
• Hill Climbing Search는 주변 값을 탐색하여 점차적으로 좋은 값으로 올라간다는 점에서 그 이름이 붙여졌으며, 현재 위치에서 주변 값을 탐색하여 후보 값들을 선정한 뒤, 그 중 하나를 골라 점차적으로 값을 업데이트 하는 방식임.
  • 대표적인 Local Search Algorithm으로, 전체를 한 번에 탐색하는 것이 아닌, 주변(local)을 계속 탐색하면서 optimum을 찾아 나가는 방식임.
  • 순수한 Hill Climbing 기법은 OPEN, CLOSED 리스트를 사용하지 않고, 오직 H(n) 값만을 사용해 탐색함.
  • 현재 상태에서 인접한 상태들(neighbors)을 살펴보고, 그 중 가장 좋은 방향으로 한 단계씩 이동하는 탐색 방법으로, 전체 탐색 공간을 한 번에 보지 않고 위치 주변에서 조금씩 더 나은 해로 올라가는 탐색임. (이러한 특성 때문에 Local Search Algorithm의 대표적인 예시라고 함)
  • 초기 상태 선택 → 초기 상태의 이웃 상태 평가 → 이웃 중 가장 좋은 상태로 이동 → 더 나은 상태가 없을 때까지 반복하여 local optimum 도달 시 종료됨.
• "휴리스틱하다"는 것은 최적 해를 반드시 찾는다는 것이 아닌, 제한된 정보로 최대한 효율적인 근사 해를 찾는 방법임을 의미함. 따라서 Hill Climbing Search가 Global Optimum을 보장하지 않아도, 현재 상태를 평가해서 더 나은 방향을 선택한다는 점에서 휴리스틱한 탐색이라고 할 수 있음. (A* Search와 같이 Optimal하거나 Complete하지 않으나, Heuristic함.)
• 실제로 가장 유용하고 많이 사용되는 것은 A* 알고리즘이며, 이러한 Heuristic Search는 길찾기 알고리즘에 많이 사용됨.

** 맹목적 탐색과 경험적 탐색은 여행에서 길을 찾는 것과 고향에서 길을 찾는 것의 차이로 이해할 수 있음. (여행 - 지도 앱을 통해 길을 따라감 / 고향 - 어떤 버스가 빠르고, 어디서 환승하는 게 더 나은지에 대한 판단이 가능함)

탐색 알고리즘 성능 측정

• 완결성 (completeness) : 문제에 해답이 있다면, 반드시 해답을 찾을 수 있는지 여부 (탐색 알고리즘이 무한 루프에 빠지지 않고 언젠가 목표 상태를 찾아낼 수 있으면 완결성이라고 함)
• 최적성 (optimality) : 가장 비용이 낮은 해답을 찾을 수 있는지 여부
• 시간 복잡도 (time complexity) : 해답을 찾는 데 걸리는 시간 (탐색 완료까지 걸리는 시간)
• 공간 복잡도 (space complexity) : 탐색을 수행하는 데 필요한 메모리 양
  • b : 탐색 트리의 최대 분기 개수 (자식 수)
  • d : 목표 노드의 깊이
  • m : 트리의 최대 깊이

Blind Search 예시

8-puzzle 문제

• 8-puzzle은 3×3 격자 위에 8개의 숫자 타일과 1개의 빈칸(blank) 이 있는 슬라이딩 퍼즐 문제로, 타일을 상/하/좌/우로 움직여 목표 상태(Goal State)에 도달하는 것을 목표로 함.
• Initial State → Intermediate States → Goal State
• 상태 (state) : 길이 9의 리스트 (0은 빈칸)
• 연산자 (operator) : 빈칸을 상/하/좌/우로 이동
• 상태 공간 (state space) : 가능한 모든 보드 배치 집합

from collections import deque
import math
import time
import matplotlib.pyplot as plt

class State:
  __slots__ = {'board', 'depth', 'goal', 'parent', 'move'}
  def __init__(self, board, goal, depth=0, parent=None, move=None):
    # 왜 튜플로 묶이는지를 이해하기 위해선 자료형에 대한 이해 필요
    # -> 튜플은 "수정 불가능한 순서 있는 집합"
    # 탐색 과정에서 여러 노드들이 같은 리스트 객체를 공유하면, 하나를 수정했을 때 다른 것도 바뀌는 문제가 발생할 수 있기에 tuple을 사용함.
    # 또한, 해시를 활용하기 위해선 불변성이 필요한데, 리스트나 딕셔너리 같은 변경 가능한 객체들은 Hashable하지 않으므로 수정 불가능한 tuple을 사용함.
    self.board = tuple(board) # 길이 9 리스트 (현재 퍼즐 상태)
    self.depth = depth # 시작으로부터의 깊이, g(n)
    self.goal = tuple(goal) # 목표 상태
    self.parent = parent # 경로 복원을 위한 부모 포인터
    self.move = move # 현재 상태를 만들게 한 이동

  # 해시 -> 어떤 데이터를 숫자(정수)로 반환한 값으로, 객체를 set, dict과 같은 자료구조에서 빠르게 찾을 수 있도록 하기 위해 사용함.
  # set과 dict는 내부적으로 해시 테이블(Hash Table) 구조로 되어 있고, 각 객체는 hash() 함수를 통해 정수 해시값을 얻고 그 값을 테이블의 인덱스(버킷 위치) 로 사용해 저장함.
  # 이로 인해 비교 대상이 매우 적어져 시간 복잡도가 줄어듦.
  # 여기서는 State 객체를 visited 집합에 넣기 위해 해시값을 사용함. (중복 체크 빠르게 하고, State 객체 해시 가능하게 만들기 위해)
  def __hash__(self):
    return hash(self.board)

  def __eq__(self, other):
    return isinstance(other, State) and self.board == other.board

  def __lt__(self, other):
    return self.depth < other.depth

  def is_goal(self):
    return self.board == self.goal

  def index0(self):
    return self.board.index(0) # 보드에서 값이 값이 0인 칸 인덱스 번호 반환

  def expand(self):
    i = self.index0()
    # divmod(a, b) -> (몫, 나머지) 튜플 반환
    # 여기서는 divmod(index0, 3)이므로 보드에서 값이 0인 칸 인덱스 번호가 몇 열에 있는지 알 수 있음.
    # (ex) i = 4라면, divmod의 결과값은 (1, 1)이고, 다음과 같이 인덱스 값이 대응됨.
    # 즉, 이를 통해 값이 0인 퍼즐 위치를 찾아낼 수 있음.
    # 0 1 2   →   (0,0) (0,1) (0,2)
    # 3 4 5   →   (1,0) (1,1) (1,2)
    # 6 7 8   →   (2,0) (2,1) (2,2)
    r, c = divmod(i, 3)
    children = []
    def swap_and_make(nr, nc, move): # nc, nr -> 0을 옮길 위치의 좌표
      j = nr * 3 + nc # 2차원 좌표를 1차원 인덱스로 변환함 (ex. (2,1) -> 7)
      new_board = list(self.board) # 현재 board는 튜플이라 불변하므로 list로 만들기
      new_board[i], new_board[j] = new_board[j], new_board[i] # 위치 옮기고
      return State(new_board, self.goal, self.depth+1, self, move)  # 새로운 상태로 State 객체 생성
    if c > 0:
      children.append(swap_and_make(r, c-1, 'L')) # 왼쪽
    if r > 0:
      children.append(swap_and_make(r-1, c, 'U')) # 위
    if c < 2:
      children.append(swap_and_make(r, c+1, 'R')) # 오른쪽
    if r < 2:
      children.append(swap_and_make(r+1, c, 'D')) # 아래
    return children

  def pretty(self):
    b = list(self.board)
    return (f"{b[0:3]}\n{b[3:6]}\n{b[6:9]}\n")

# 탐색 끝난 뒤 부모 포인터 따라가면서 목표 상태까지 온 경로(탐색 경로) 복원
def reconstruct_path(s: State):
  path = []
  while s is not None:
    path.append(s) # 현재 상태 path 추가
    s = s.parent # 부모 상태로 이동 (이걸 부모가 없는 시작점까지 반복)
  path.reverse() # 순서 뒤집기 (자식부터 거꾸로 추가했으니까)
  return path

def print_path(path):
  for i, st in enumerate(path):
    print(f"Step {i}  (move={st.move})\n{st.pretty()}")

List, Dictionary, Set, Tuple의 정리

• List : 파이썬에서의 배열 표현으로, 크기 조정/서로 다른 데이터 타입 가능
  • modifiable, resizeable, different data type
• Dictionary : (key, value) 쌍으로 이루어진 표현
  • 존재하지 않는 키 값 사용 시 keyError가 발생하므로 get() 함수 활용
  • 값 삭제 : del 변수[key]
  • key, value unpacking : 변수.items()
• Set : 고유한 원소들의 순서 없는 집합
  • add(), remove() 활용
  • distinct(고유한), Unordered
• Tuple : 수정 불가능한 순서 있는 집합으로 리스트와 비슷하나 딕셔너리의 키, Set의 element와 같은 역할
  • immatable(수정 불가능한), Ordered list

Hashable하려면 값이 불변해야 하는 이유

• 해시는 해시값을 키로 사용해 데이터를 저장하는데, 해시 값이 변하면 그 객체의 저장 위치가 변하거나 위치를 잘못 참조해 데이터 무결성이 깨질 수 있음. (https://velog.io/@naringst/python-hashable)

BFS (Breath-First Search)

• 분기 계수 b가 유한하면 너비 우선 탐색은 반드시 해답을 발견할 수 있음.
• 시간 복잡도와 공간 복잡도는 모두 지수 복잡도 $O(b^d)$

def bfs(start_board, goal_board):
  start = State(start_board, goal_board) # 시작 상태 생성
  if start.is_goal(): # 시작 상태가 목표 상태면 그대로 반환
    return reconstruct_path(start), 0, 0 # path, expanded, t1 - t0
  q = deque([start])
  visited = {start} # 방문한 상태
  expanded = 0 # 확장한 노드
  t0 = time.time()
  while q:
    cur = q.popleft() # 큐에서 맨 앞 노드 꺼냄
    expanded += 1
    for child in cur.expand(): # 가능한 모든 자식 상태 생성
      if child in visited: # 현재 상태에서 나온 자식 이미 봤으면 넘기기
        continue
      if child.is_goal(): # 목표 상태 도달
        t1 = time.time()
        path = reconstruct_path(child)
        return path, expanded, t1 - t0 # 리턴
      visited.add(child)
      q.append(child)
  return None, expanded, time.time() - t0 # 목표 상태에 도달하지 못함 -> 시작 노드 = 목표 노드이므로 기존 Path가 없음 -> None

deque(Double-Ended Queue)를 사용한 큐 관리

• 양쪽에서 요소를 추가하거나 제거 가능한 데이터 구조로, '양방향 큐'라고도 한다.
• 스택처럼 사용할 수도 있고, 큐 처럼 사용할 수도 있다.
• 일반적인 리스트(list)가 이러한 연산에 O(n)이 소요되는 데 반해, deque는 O(1)로 접근하기 때문에 리스트보다 빠른 추가/제거 연산이 가능하며, push/pop 연산이 빈번한 알고리즘에서 리스트보다 월등한 속도를 자랑하기 때문에 자주 사용된다.
• deque는 스레딩과 무관하며, 기본적으로 스레드 안전하지 않다. 그러나 리스트보다 빠른 큐 작업을 제공하며, 회전(Rotation) 및 슬라이스(Slicing) 같은 추가적인 기능도 지원하기 때문에 주로 사용한다.
• 주요 메서드
  • append(item) : 끝에 요소 추가
  • appendleft(item) : 앞에 요소 추가
  • remove(item) : 특정 요소 제거
  • rotate(num) : 요소를 num만큼 회전해 앞뒤를 변경 (양수면 오른쪽 회전, 음수면 왼쪽 회전)

DFS (Depth-First Search)

• 무한 상태 공간에서의 깊이 우선 탐색은 무한 경로를 따라 끝없이 나가므로 완결적이지 않음.
• 최적성 또한 없으며, 가장 왼쪽(leftmost)에 있는 해답만을 발견함.
• 시간 복잡도는 $O(b^m)$, 공간 복잡도는 $O(bm)$이므로 공간 복잡도는 선형 복잡도만을 지님.

def dfs(node:State, limit, visited, expanded):
  if node.is_goal(): # 현재 노드 == 목표 상태
    return reconstruct_path(node), expanded # (path, expanded)
  if limit == 0:
    return None, expanded # 목표 도달도 전에 깊이 제한 도달 & 깊이 제한이 0이라 루트 노드 이상 탐색 X
  visited.add(node) # 노드 방문 기록
  for child in node.expand(): # 자식 탐색
    if child in visited:
      continue
    expanded += 1
    res, expanded = dfs(child, limit - 1, visited, expanded) # 자식 상태에 대해 재귀적 실행
    if res is not None: # res -> reconstruct_path(node)로 반환받은 값
      return res, expanded
  return None, expanded # 목표 상태에 도달 못함

# 깊이 제한 탐색 : 특정 깊이 이상으로 들어가지 못하게 하는 dfs
def dfs_with_depth_limit(start_board, goal_board, limit=20):
  start = State(start_board, goal_board)
  t0 = time.time()
  path, expanded = dfs(start, limit, set(), 0) # set() -> visited 집합
  return path, expanded, time.time() - t0

IDDFS (점증적 깊이 증가 DFS, Iterative Deepening DFS)

• 한계 깊이를 차례로 늘려가며서 제한 탐색을 진행하는 것
• 깊이 우선 탐색의 공간 효율성과 너비 우선 탐색의 완전성을 결합함.
• BFS처럼 최단 경로를 찾을 수 있음. (최적성)
• 노드를 여러 번 방문할 가능성이 있어 비효율적일 수 있고, 간단한 문제에 대해서는 BFS, DFS가 더 쉬울 수 있음.

def iddfs(start_board, goal_board, max_depth=30):
  start = State(start_board, goal_board)
  total_expanded = 0 # 탐색 과정에서 확장한 전체 노드 수
  t0 = time.time()
  # max_depth까지 하나씩 늘려가면서 DFS 실행
  for depth in range(max_depth + 1):
    path, expanded = dfs(start, depth, set(), 0)
    total_expanded += expanded
    if path is not None: # goal 도달
      return path, total_expanded, time.time() - t0
  return None, total_expanded, time.time() - t0

Heuristic Search 예시

Heuristic 정의

def h_misplaced(board, goal):
  return sum(1 for i in range(9) if board[i] != 0 and board[i] != goal[i]) # 잘못 놓인 타일 수 반환

def h_manhattan(board, goal):
  pos = {v: i for i, v in enumerate(goal)} # 목표 상태 위치 인덱스 딕셔너리 형태 저장
  dist = 0 # 전체 맨해튼 거리 합
  for i, v in enumerate(board):
    if v == 0: # 0은 빈칸이니까 무시
      continue
    gi = pos[v] # 현재 값 v가 목표 상태에서 어디에 있어야 하는지 확인
    r1, c1 = divmod(i, 3) # 현재 위치
    r2, c2 = divmod(gi, 3) # 목표 위치
    dist += abs(r1 - r2) + abs(c1 - c2) # h(n) 거리 계산
  return dist

A* Search (f(n) = g(n) + h(n))

 A* Search는 지금까지 온 거리 + 남은 거리를 합산해 총 예상 비용이 낮은 후보부터 탐색해 나가는 알고리즘을 의미하며, A* 알고리즘이 Optimal하고 Complete하게 동작하려면, 휴리스틱 조건을 만족해야 한다.

• Admissibility : 휴리스틱 비용이 0≤h(n)≤h∗(n)의 조건을 만족해야 한다는 것. 다시 말해, 휴리스틱 값은 항상 실제 최단 거리보다 크지 않아야 함. (낙관적인 추정을 통해 Optimal한 해를 추정하기 위해) (이때, h*(n)은 실제 최단 거리, 즉 true cost를 의미함)
  • 0 이상 : 휴리스틱이 0보다 작으면 오히려 잘못된 방향으로 탐색이 유도될 수 있음.
  • h*(n) 이하 : 실제 남은 거리보다 작거나 같은 값만큼만 추정해야 탐색이 너무 비관적이지도 않고, 너무 낙관적이지도 않은 “올바른 방향으로의 탐색”이 가능함.
  • 다시 말해, 과대평가하지 않는 범위에서 가장 현실적인 추정치가 최적의 휴리스틱이라고 할 수 있음.
• Consistency (일관성) : 경로를 따라가면서 휴리스틱 값이 일관되게 감소해야 한다는 것으로, h(n)≤c(n,n')+h(n')의 조건을 만족함. (이때, c(n,n')는 n에서 n'으로 이동할 때의 실제 비용, h(n')는 다음 상태의 휴리스틱 값임)
  • 즉, 연결된 두 노드 간의 휴리스틱 값의 차이는 실제 이동 비용보다 크지 않아야 한다. (c(n, n') >= h(n) - h(n'))
  • 두 노드를 건너는 실제 비용보다 휴리스틱 값의 차이가 크면, 휴리스틱이 일관되지 않게 되어 탐색이 불안정해지고 중복 탐색이 발생할 수 있다.

heapq

• 순위가 가장 높은 자료(data)를 가장 먼저 꺼내는 우선순위 큐를 구현한 모듈 (https://docs.python.org/3/library/heapq.html)

import heapq

def astar(start_board, goal_board, h_func=h_manhattan):
  start = State(start_board, goal_board)
  if start.is_goal(): # 시작 상태 = 목표 상태
    return reconstruct_path(start), 0, 0
  open_heap = [] # 우선 순위 큐 (F 값 작은 순서대로 탐색해 나가야 하니까)
  gscore  = {start.board: 0}
  f0 = h_func(start.board, start.goal) # 시작 상태의 f(n) -> 0 + h(start)
  heapq.heappush(open_heap, (f0, 0, start)) # 우선순위 큐에 시작 상태 저장, g = 0
  closed = set() # set은 중복 방지 & 빠른 탐색(해시 기반 구조)을 위해 사용됨.
  expanded = 0
  t0 = time.time()

  while open_heap:
    f, g, cur = heapq.heappop(open_heap) # F(n) 값이 가장 작은 상태 pop
    if cur.board in closed: # 이미 처리된 것들 (visited 처리)
      continue
    if cur.is_goal(): # 목표 상태 도달
      t1 = time.time()
      return reconstruct_path(cur), expanded, t1-t0
    closed.add(cur.board)
    expanded += 1
    for child in cur.expand(): # 현재 상태에서 이동할 수 있는 모든 자식 상태 생성
      tentative_g = g+1 # 자식 G(n)
      # tentative_g -> 시작 노드에서 현재 노드까지 걸린 Path Cost, gscore.get(child.board, math.inf) -> 지금까지 발견된 child 최단 경로 g
      if child.board in closed and tentative_g >= gscore.get(child.board, math.inf): # 닫힌 경로 + 경로 별로
        continue
      if tentative_g < gscore.get(child.board, math.inf): # 더 짧은 경로 찾음
        gscore[child.board] = tentative_g # gscore 갱신 (G(n))
        fchild = tentative_g + h_func(child.board, child.goal) # F(n) = H(n) + G(n)
        heapq.heappush(open_heap, (fchild, tentative_g, child)) # open_heap에 넣음 (F(n), G(n), 현재 상태)
  return None, expanded, time.time() - t0

기본 보드를 통한 각 알고리즘 비교

START = [2, 8, 3, 1, 6 , 4, 7, 0, 5]
GOAL = [1, 2, 3, 8, 0, 4, 7, 6, 5]

def run_all(start=START, goal=GOAL):
  results = {}
  # BFS
  path, expd, t = bfs(start, goal)
  results['BFS'] = (len(path)-1 if path else None, expd, t)

  # DFS (depth-limited) - 무한 상태 공간에서의 깊이 우선 탐색은 무한 경로를 따라 끝없이 나가므로 완결적이지 않음 (expanded = 5369)
  path, expd, t = dfs_with_depth_limit(start, goal, limit=20)
  results['DFS(d<=20)'] = (len(path)-1 if path else None, expd, t)

  # IDDFS - 노드를 여러 번 방문할 가능성이 있어 비효율적일 수 있음 (expanded = 91)
  path, expd, t = iddfs(start, goal, max_depth=30)
  results['IDDFS'] = (len(path)-1 if path else None, expd, t)

  # misplaced와 manhattan은 모두 휴리스틱 함수 H(n)로 사용될 수 있으며,
  # 어떤 휴리스틱 함수를 넘기느냐에 따라 탐색 효율성이 다르다는 것을 결과를 통해 확인 가능함.
  # manhattan -> 계산은 조금 더 복잡하지만 정보량이 많음.
  # 그럼에도 두 A* 모두 완결성과 최적성은 동일하게 유지됨.
  # A* (misplaced)
  path, expd, t = astar(start, goal, h_func=h_misplaced)
  results['A*(misplaced)'] = (len(path)-1 if path else None, expd, t)

  # A* (manhattan)
  path, expd, t = astar(start, goal, h_func=h_manhattan)
  results['A*(manhattan)'] = (len(path)-1 if path else None, expd, t)
  return results

res = run_all()
for k, v in res.items():
  print(f"{k:16s} | path_len={v[0]} expanded={v[1]} time={v[2]:.4f}s")

코드 실행 결과

BFS              | path_len=5 expanded=26 time=0.0002s
DFS(d<=20)       | path_len=17 expanded=5369 time=0.0167s
IDDFS            | path_len=5 expanded=91 time=0.0002s
A*(misplaced)    | path_len=5 expanded=6 time=0.0001s
A*(manhattan)    | path_len=5 expanded=5 time=0.0001s