Please enable JavaScript.
Coggle requires JavaScript to display documents.
문제 해결과 탐색
2410 김다연 - Coggle Diagram
문제 해결과 탐색
2410 김다연
문제의 구조화
-
-
- 현재 상태로부터 다음 상태로 진행하기 위한 수행 작업 정의
- 초기 상태로부터 목표 상태까지 효율적으로 도달하기 위한 전략 수립
탐색을 활용한 문제 해결
맹목적 탐색을 활용한 문제 해결
-
-
맹목적 탐색은 사전 지식 없이 다음 모든 상태들을 다 탐색하기 때문에 결국 문제를 해결하기 위해 최악의 경우, 탐색 트리의 모든 상태를 다 방문해야 목표 상태에 도달할 수 있다.
맹목적 탐색은 모든 상태를 탐색하기 때문에 항상 목표 상태에 도달할 수 있다. 하지만 상태의 수가 너무 많은 문제는 해결할 수 없다. 강 건너기 문제에서 배를 탈 수 있는 대상의 수가 100개만 되어도 상태의 수는 2의 100제곱 개다. 즉 실제 탐색해야 할 공간의 크기가 최소 2의 100제곱개가 되어 모두 탐색할 수 없을 만큼 많기 때문에 효울적으로 문제를 해결할 수 없다.
최상 우선 탐색을 활용한 문제 해결
-
최상 우선 탐색은 상태를 효율적으로 탐색하기 위해, 설정한 규칙에 따라 선택된 목표 상태가 존재할 가능성이 가장 큰 다음 상태로 확장하여 탐색한다.
-