[AI]Unformed Search

1. 탐색

• 탐색: 상태 공간에서 시작 상태에서 목표상태까지의 경로를 찾는 것
• 상태 (state) : 문제 해결 과정에서의 현재 상황 (예: 8-puzzle에서 퍼즐 배열, Hanoi에서 탑 상태)
• 상태 공간 (state space) : 모든 가능한 상태들의 집합
• 연산자 : 다음 상태를 생성 (8-puzzle -> 조각 이동, Hanoi -> 원판 이동)
• 탐색 트리 (search tree) : 상태를 노드(node), 연산자를 간선(edge)로 표시

2. 문제 해결 과정의 두 가지 접근

(1). 직접적 기법

• 문제 해결을 위해 순차적 단계 프로그래밍을 하는 방식
• 문제의 모든 단계가 코드에 직접 명시
• 초기 상태가 바뀌면 프로그램 다시 수정
• 인공적인 판단 X

# N = 5일 때
result = 1 + 2 + 3 + 4 + 5
print(result)

• 문제 상태가 바뀌면 (예 N = 10) 코드 수정 필요
• Hanoi Tower 문제 => 디스크 3개를 A-> C로 옮기는 과정 직접 코딩 (이때 초기 상태 (디스크 계수)가 달라지면 코드 수정 필요

(2). 지능적 기법

• 현재 상태(state)와 목표 상태(goal)만 알려주면 컴퓨터가 스스로 해를 찾아가는 과정
• 탐색(Search)를 사용하여 상태 공간을 자동 탐색
• 탐색 과정에서 지능적 판단이 필요 => 최적해 혹은 적당한 해 도출
• Hanoi Tower 문제 : DFS, BFS 같은 탐색 알고리즘을 사용하여 목표 상태에 도달

4. 탐색 기법 분류

(1). 맹목적 탐색 (Uninformed / Blind / Random )

• 목표에 대한 정보 없이 모든 후보를 체계적으로 탐색
• DFS, BFS, Uniform-Cost Search

(2). 경험적 탐색 (Heuristic/Informed)

• 목표 상태와의 "거리"나 경험적인 정보를 활용
• Greedy Search, Hill Clmbing, Simulated Annealing, A* Search

3. BFS (Breadth-Frist Search) / DFS (Depth-First Search)

• BFS : 루트에서 시작하여 깊이 1 -> 깊이 2 -> 깊이 3 순으로 차례대로 검색
  ▫ 최단 경로 보장 (모든 간선 비용이 동일할 경우)
  ▫ 목표에 도달하는 가장 짧은 단계 탐색 가능
  ▫ 메모리 사용량 큼 (노드를 큐에 저장해야 하므로 상태 공간이 커지면 비효율적)
  ▫ Level-order 순서대로 노드 방문

• DFS : 한 경로를 끝까지 탐색한 후 막히면 뒤로 돌아와 다른 경로 탐색
  ▫ 메모리 절약 가능
  ▫ 목표해가 깊은 곳에 위치하면 빠르게 접근 가능
  ▫ 최적해 보장 불가 (먼저 발견된 해가 최단 경로가 아닐 수 있음)
  ▫ 무한 루프 가능 (깊이가 무한할 경우 대책 필요 -> depth limit)
  ▫ pre-order, In-order, Post-order

• 구분	BFS	DFS
  탐색 방식	너비 우선 (같은 깊이 노드 먼저)	깊이 우선 (한 경로 끝까지)
  자료구조	큐(Queue)	스택(Stack) / 재귀
  메모리	많이 사용	적게 사용
  최단 경로	보장	보장 X
  목표 깊이	얕은 목표 → 빠름	깊은 목표 → 빠름
  단점	상태 공간 크면 비효율	무한 루프 가능, 최적해 X