Please enable JavaScript.
Coggle requires JavaScript to display documents.
문제 해결과 탐색
2214 한성원 - Coggle Diagram
문제 해결과 탐색
2214 한성원
-
문제의 구조화
개념: 퍼즐이나 게임과 같은 문제는 일반적으로 수학 공식으로 해결하기 어려우므로 이런 문제들을 해결하기 위해서는 먼저 탐색할 수 있는 형태로 구조화한 후, 각 상태를 차례대로 탐색하면서 해결 방법을 찾을 수 있음.
-
탐색으로 문제를 해결하기 위한 구조화 과정
1) 상태 정의
2) 초기 상태와 목표 상태 설정
3) 현재 상태로부터 다음 상태로 진행하기 위한 수행 작업 정의
4) 초기 상태로부터 목표 상태까지 효율적으로 도달하기 위한 전략 수립
맹목적 탐색을 활용한 문제 해결
맹목적 탐색: 깊이 우선 탐색, 너비 우선 탐색과 같은 방법으로 문제의 모든 상태를 다 탐색하여 목표 상태를 찾는 것.
또한, 사전 지식 없이 모든 다음 상태들을 다 탐색하기 때문에 결국 문제를 해결하기 위해 최악의 경우, 탐색 트리의 모든 상태를 다 방문해야 목표 상태를 도달할 수 있는 것.
예시) 깊이 우선 탐색을 이용한 목표 상태 찾기, 너비 우선 탐색을 이용한 목표 상태 찾기
최상 우선 탐색을 활용한 문제 해결
-
효율적 탐색 방법
-
평가 함수 규칙을 설장하여 활용하는 것.
평가 함수: 값이 작을수록 탐색의 우선순위가 높고, 성능에 따라서 전체 효율이 결정되는 것이므로, 평가 함수의 설정은 매우 중요함.
-
-