탐색

[인공지능] 탐색(Search) 요약

맹목적 탐색: 정해진 순서에 따라 상태 공간 그래프를 점차 생성해 가면서 해를 탐색 하는 방법 깊이 우선 탐색 (DFS) 해가 존재할 가능성이 존재하는 한 앞으로 계속 전진, 즉 깊이 방향으로 탐색 • 최근에 생성된 노드를 가장 먼저 확장 • 노드의 깊이 Root node의 깊이는 1 자손인 노드의 깊이 = 부모노드의 길이 + 1 • 백트래킹(backtracking)을 위해 깊이 제한을 둔다. DFS의 알고리즘 출발노드를 OPEN에 넣는다. OPEN에 노드가 남아있는 동안 다음을 반복한다. OPEN의 제일 앞에 있는 노드를 꺼내어 CLOSED에 넣는다.(이 노드를 n이라고 부름) n의 길이가 깊이 제한에 도달하지 않았다면 다음을 실행한다. 노드 n을 확장하여 모든 후계노드를 생성 생성된 후계노드들에게 부..