연산자

개념

연산자는 상태 공간에서 현재 상태를 다음 상태로 바꾸는 동작이다. 탐색 문제에서 어떤 연산자를 허용하느냐에 따라 가능한 경로가 결정된다.

상태 전이 함수로 쓰면 연산자 $a$는 현재 상태 $s$를 다음 상태로 바꾼다.

$$T:S\times A\to S,s^{\prime }=T(s,a)$$

예시

8-Puzzle에서는 빈칸을 위, 아래, 왼쪽, 오른쪽으로 움직이는 것이 연산자이다. 로봇 이동에서는 전진, 회전, 정지 같은 행동이 연산자가 될 수 있다.

탐색에서의 역할

탐색 알고리즘은 현재 상태에 적용 가능한 연산자를 사용해 자식 상태를 생성한다. 이 자식 상태들을 어떤 순서로 방문하느냐에 따라 깊이 우선 탐색, 너비 우선 탐색, 휴리스틱 탐색 등이 달라진다.