Please enable JavaScript.
Coggle requires JavaScript to display documents.
문제 해결과 탐색 2226 최지혜 - Coggle Diagram
문제 해결과 탐색
2226 최지혜
문제의 구조화
탐색으로 문제를 해결하기 위한 구조화 과정
상태 정의
농부, 늑대, 염소, 양배추의 위치
초기 상태와 목표 상태 설정
농부는 농, 늑대는 늑, 염소는 염, 양배추는 추로 추상화하여 표현 가능, 강을 기준으로 각각의 현재 위치를 알 수 있음
수행 작업 정의
현제 싱테
농, 늑, 염, 추 (강)
강 건너기 (농부)
녹, 염, 추 (강) 농
강 건너기 (농부, 늑대)
염, 추 (강) 농, 늑
강 건너기 (농부, 염소)
늑, 추,(갱) 농, 염
강 건너기 (농부, 양배추)
늑, 염 (강) 농, 추
전략 수집
상태 공간 탐색 트리
탐색 구조를 트리 형태로 나타낸 것
탐색을 활용한 문제 해결
맹목적 탐색을 활용한 문제 해결
깊이 우선 탐색
너비 우선 탐색
사전 지식 없이 모든 상태들을 다 탐색하여 최악의 경우 탐색 트리의 모든 상태를 다 방문해야 목표 상태에 도달
항상 목표 상태에 도달
상태의 수가 너무 많은 문제는 해결할 수 없다
최상 우선 탐색
탐색 중 얻은 정보를 바탕으로 하여 모든 상태를 탐색하지 않아도 목표 상태를 찾을 수 있도록 하는 탐색 방법
효율적으로 탐색하기 위해 설정한 규칙에 따라 선택된 목표 상태가 존재할 가능성이 가장 큰 다음 상태로 확장하여 탐색함
평가 함수 규칙 설정하여 활용
초기 상태에서 현재 상태까지 오기 위한 최소 수행 작업의 ㅅ와 목표 상태와 현재 상태의 비교 값을 이용하여 만들 수 있음