Please enable JavaScript.
Coggle requires JavaScript to display documents.
문제 해결과 탐색 (2123 안혜원) - Coggle Diagram
문제 해결과 탐색
(2123 안혜원)
문제의 구조화
퍼즐이나 게임과 같은 문제
일반적인 수학 공식으로는 해결하기 어려움
이러한 문제들은 먼저 탐색할 수 있는 형태로 구조화한 후 각 상태를 차례로 탐색하면서 해결방법 찾는 것도 하나의 방법
탐색으로 문제를 해결하기 위한 구조화 과정
상태 정의
초기 상태와 목표 상태 설정
현재 상태로부터 다음 상태로 진행하기 위한 수행 작업 정의
초기 상태로부터 목표 상태까지 효율적으로 도달하기 위한 전략 수립
탐색을 활용한 문제 해결
맹목적 탐색을 활용한 문제 해결
맹목적 탐색
우선 탐색
너비 우선 탐색
문제의 모든 상태를 다 탐색하여 목표 상태 찾음
최악의 경우
모든 다음 상태들을 다 탐색하기 때문에 결국 문제를 해결하기 위해 모든 상태들을 다 방문해야 목표 상태에 도달할 수도 있다.
항상 목표 상태에 도달할 수 있지만 상태의 수가 너무 많은 문제는 해결할 수 없다.
최상 우선 탐색을 활용한 문제 해결
탐색 중에 얻은 정보를 바탕으로 하여 모든 상태를 탐색하지 않아도 목표 상태를 찾을 수 있도록 한다
효율적으로 탐색하기 위해 설정한 규칙에 따라 선택된 목표 상태가 존재할 가능성이 가장 큰 다음 상태로 확장하여 탐색
평가 함수
확장시킬 노드들에 순위를 매김으로써 어떤 것이 목표 상태까지 가는 데 최상의 경로가 있는지 결정하는 것