전체 글 (291) 썸네일형 리스트형 탐색과 최적화 기법 (3) 3-5 게임 탐색 게임의 참가자가 이기기 위해 매순간 최선의 방법을 찾는 것을 모방한 것 미니맥스 알파베타 가지치기 자신의 순서에서 최댓값을 선택하고, 상대방의 순서에서 최솟값을 선정하는 과정을 반복적으로 수행하는 것 알파 컷오프: 최소 점수를 선택하면서 이미 저장된 점수보다 큰 점수의 노드가 나오면 제외하는 것 베타 컷오프: 최대 점수를 선택하면서 이미 저장된 점수보다 작은 점수의 노드가 나오면 제외하는 것 몬테카를로 트리 탐색 몬테카를로: 무작위(Random)라는 의미를 가짐 플레이아웃(Playout): 현상태에서 게임 종료 시까지 무작위 플레이를 수행하는 것 시뮬레이션 알파고와 같은 프로그램에서 사용 3-6 제약 조건 만족 문제 주어진 제약 조건을 만족하는 해를 찾는 것 Constant Satisf.. 탐색과 최적화 기법 (2) 3-4 정보 이용 탐색 상태 공간에 대한 정보를 이용해 효율을 높이는 탐색 휴리스틱 탐색(Heuristic Search) 언덕 오르기 방법 탐욕 알고리즘(Greedy Algorithm) 현상태를 바탕으로 연결된 이웃 상태만을 고려하므로 지역 탐색(Local Search) 휴리스틱을 사용 가장 좋은 것을 선택 최상우선 탐색 언덕 오르기 방법이 최곳값을 찾아 내지 못하는 단점을 극복하고자 개발된 방법 탐색 과정 1단계: 시작점에서 인접한 노드 중 가장 큰 값을 선택 2단계: 선택된 큰 값에 인접한 노드와 앞서 선택한 노드들 중 가장 큰 값을 선택 3단계: 선택된 큰 값에 인접한 노드와 앞서 선택한 노드들 중 가장 큰 값을 선택 4단계: 선택된 큰 값에 인접한 노드와 앞서 선택한 노드들 중 가장 큰 값을 선택.. 탐색과 최적화 기법 (1) 3-1 상태 공간과 탐색 탐색 상태의 변화를 통해 문제의 해를 찾는 과정 상태 공간과 탐색의 중요 개념 상태 공간(State Space): 문제의 초기 상태부터 도달할 수 있는 모든 상태의 집합 또는 문제의 해가 될 가능성이 있는 상태들의 집합 탐색으로 해 구하기: 상태 공간을 체계적으로 탐색해 목표 상태에 도달하게 하는 일련의 동작을 찾거나 문제의 해가 되는 상태 자체를 찾는 것 상태 공간 그래프: 변하는 상태를 표현한 그래프 상태 공간 그래프의 예 3-2 탐색의 종류 맹목적 탐색(Blind Search) 문제의 상태 공간 정보를 이용하지 않고 정해진 순서에 따라 상태 공간 그래프를 생성하면서 순서대로 모든 경우를 탐색해 해를 찾는 것 깊이우선 탐색(Depth-First Search, DFS) 너비우선.. 이전 1 ··· 42 43 44 45 46 47 48 ··· 97 다음
