39. search tree [14 2주차]

39. Search Tree [14-2주차]

2024년 1월 14일 일요일

오후 5:23

<Search Trees and Cutoff>

15퍼즐의 경우 State Space Graph를 만들려면 노드 16!개가 필요하다. 만들어야 할 노드 개수가 너무 많으므로, 실제로 컴퓨터로 15퍼즐을 풀 때는 처음 두 줄은 휴리스틱으로 풀고(일반적으로 사람이 풀 때랑 비슷한 풀이) 밑의 두 줄은 8!개의 노드를 가진 State space graph의 shortest path를 구해 푼다.

이와 같이 State Space 그래프가 너무 커서 전부 만들기 힘든 경우가 자주 있다. 이런 경우 Search Tree와 Cutoff를 사용할 수 있다.

• Search Tree : State Space 그래프의 일부를 트리로 만든 것. 일반적으로 모든 노드를 전부 만들지 않고, 루트 노드부터 아래로 노드를 생성하다 특정 조건을 만족하지 못하면 cutoff 시키는 방식으로 구현한다.
• Cutoff : search tree의 노드가 특정 조건을 만족하지 않아 그 자손 노드가 답을 구하는 데 도움이 되지 않는다고 판단되면, 해당 노드의 자손 노드들은 생성하지 않는 것.

<Subset Sum Problem>

NP-Complete 문제이다. 자연수 집합 A={a1, a2, a3, …, an}와 타겟S가 주어진다. 합이 S가 되는 A의 부분 집합을 모두 구해야 한다.

Search Tree는 이진 트리 형태가 되며, a_i가 부분집합에 포함되는지 포함되지 않는지를 기준으로 만들어진다. (여기서 Search Tree의 노드가 State Space의 원소와 약간 차이가 있다는 것에 주의)

• 루트 노드는 A각각의 원소 모두가 포함될지 포함되지 않을지 결정되지 않은 상태를 의미한다.
• 루트의 자식 노드는 하나는 a1을 포함하는 경우, 다른 하나는 a1을 포함하지 않는 경우이다.
• 깊이 2인 노드들은 a2를 포함하는지 포함하지 않는지에 따라 생성된다. a1을 포함하는지 여부는 부모 노드를 따른다.
• 깊이 k의 노드들은 a_k를 포함하는지 포함하지 않는지에 따라 생성된다. a1, a2, …, a_k-1을 포함하는지 여부는 부모 노드를 따른다.

이런 식으로 Search Tree를 만들어 나간 뒤 리프 노드의 선택된 원소의 합을 구하면 정답을 찾을 수 있다. 그러나 수행시간을 줄이려면 다음과 같이 cutoff를 해야 한다.

• 특정 노드에 대해, C를 "선택하기로 결정된 A의 원소들의 합"으로 정의한다.
• 노드의 C값이 S를 넘는 경우 cutoff한다. 즉 그 노드의 자손 노드는 생성하지 않는다.
• 노드의 C값에 아직 포함 여부가 결정되지 않은 A의 원소들을 전부 더한 값이 S보다 작으면 cutoff한다.

<N-Queen 에서 Search Tree>

N-Queen 문제를 푸는 알고리즘도 Search Tree로 이해할 수 있다.

• 루트 노드는 퀸의 위치가 하나도 정해지지 않은 상태를 의미한다.
• 깊이 1인 노드들은 체스판의 첫 번째 행의 퀸의 위치가 정해진 상태이다.
• 깊이 2인 노드들은 첫 번째 행의 퀸의 위치는 부모 노드를 따르고, 2번째 행의 퀸의 위치에 따라 갈린다.
• 깊이 k인 노드들은 체스판의 k-1번째 행까지의 퀸의 위치는 부모 노드를 따르고, k행의 퀸의 위치에 따라 갈린다.
• 어디에도 퀸을 놓을 수 없는 행이 생기면 cutoff한다.

(N-Queen 문제를 푸는 알고리즘이 실제로 트리를 만들 필요는 없다. 보통 크기가 N인 배열 하나로 구현한다)