탐색 (Search), 상태공간, 연산자

• 탐색: 상태공간 내에서 시작 상태에서 목표 상태까지 도달하는 경로를 찾는 과정
• 상태공간 (State Space): 가능한 모든 상태들의 집합
• 연산자 (Operator): 한 상태에서 다른 상태로 전이하는 규칙
• 초기 상태 (Initial State) / 목표 상태 (Goal State): 탐색의 출발점과 도착점으로, 탐색의 대상이 되는 문제 정의의 핵심 요소

상태공간의 예시 1: 8-puzzle

• 8개의 숫자 타일과 1개의 빈칸으로 구성
• 초기 상태: 현재 퍼즐의 배치
• 목표 상태: 숫자가 오름차순으로 정렬된 상태
• 연산자: 빈칸을 위/아래/좌/우로 움직이는 연산

상태공간의 예시 2: N-Queen 문제

• 문제: NxN 체스판에 N개의 퀸을 서로 위협하지 않도록 배치
• 상태: 각 열에 퀸을 하나씩 배치한 배열 → 2차원 배열로 표현 가능
• 초기 상태: 아무 것도 배치되지 않은 상태
• 목표 상태: 모든 퀸이 충돌 없이 배치된 상태 (※ 목표상태가 유일하지 않을 수 있음)
• 연산자: place_i — i번째 행에 퀸을 배치하는 연산