OPEN과 CLOSED

개념

OPEN과 CLOSED는 탐색에서 중복 방문을 줄이고 아직 탐색할 상태를 관리하기 위한 리스트이다.

OPEN

OPEN 리스트에는 생성되었지만 아직 탐색하지 않은 노드가 들어간다. 어떤 자료구조로 운영하느냐에 따라 알고리즘이 달라진다.

• 깊이 우선 탐색: 스택처럼 사용
• 너비 우선 탐색: 큐처럼 사용
• 최상 우선 탐색과 A star 알고리즘: 우선순위 큐처럼 사용

CLOSED

CLOSED 리스트에는 이미 탐색이 끝난 노드가 들어간다. 같은 상태를 다시 넣지 않도록 확인해 무한 반복을 막는다.

노드 $n$을 확장할 때 집합의 이동은 다음처럼 나타낼 수 있다.

$$\begin{array}{rl}\mathrm{OPEN}& \leftarrow \mathrm{OPEN}\setminus \{n\},\\ \mathrm{CLOSED}& \leftarrow \mathrm{CLOSED}\cup \{n\}\end{array}$$