집밖은 위험해

mini-max

- 예상되는 최대의 손실 maximum loss를 최소화 minimize 시키기 위해 사용하는 의사결정 방법

의사 결정 이론 decision theory

- 불확실성에 직면하여 결정을 내려야할때, 어떤 결정을 할것이며, 어떤 정보를 어떻게 이용해야하는가를 다루는 이론

-> 기대 효용이 최대가 되도록 판단해야함

=> 정보 가치가 높은 정보는 무엇인지 찾고, 이것으로 어떻게 구체적을 내리는가 제시해야함

의사 결정 이론

- 효용성으로 표현되는 선호 preference는 결정이론 decision theory라고 불리는 합리적 의사 결정의 일반 이론에서 확률과 결합

- 결정 이론 decision theory = 확률 이론 probability theory + 효용 이론 utility theory

결정 이론 기본 개념

- 행동의 모든 가능한 결과에 대해 평균해서, 만일 가장 높은 기대 효용 expected uitility를 낳는 행동을 선택한다면 그 떄에만 그 에이전트는 합리적

=> 기대 효용 최대화 Maximum Expected Uitility, MEU의 원리

A* 탐색 알고리즘 A s* search algorithm 개요

- 초기 노드에서 목표 노드까지 경로 찾는 그래프 탐색 알고리즘

- 목표 노드까지 가장 좋은 경로 estimate of the best route 하기 위해 각 노드에 랭킹 부여하는 heuristic estimate를 사용하고, 그 순서를따라 노드 방문

A* 알고리즘의 장점

- 최단 거리 찾기 문제에서 다른 알고리즘(다익스트라, best-first search)보다 훨씬 빠름

A* 알고리즘 개발 배경

- 휴리스틱 방법(의사 결정시 해당 문제에 대한 정보를 이용하는것)

+ 형식적 방법(formal method : 문제 관련 정보를 사용하지 않지만 정형 분서이 될수있는것)을 결합하기 위해 1968년 개발

A* 알고리즘의 구조

- 그래프 탐색 알고리즘

- 타 그래프 탐색 알고리즘과 차이는 목표에 얼마나 근접한지 평가하기위해 휴리스틱 함수를 사용함

-> 휴리스틱에 의해 먼저 바람직한 방향을 탐색, 그 방향이 실패하면 다른 경로를 찾음

A*의 활용

- 경로 탐색기로 많이 사용

- 공간안 특정 상태에서 인접한 상태를 조사해 나가면서 목표 상태까지 가장 싼 비용의 경로를 찾음

분기 한정법 branch and bound

- 분기 한정법은 여러 최적화 문제, 특히 이산 discrete와 조합 최적화 combinational optimization에서 최적해를 찾기위한 일반적인 방법

- 인수 x(가능영역 feasible region)에 대해 함수 f(x)의 최소 값을 찾는 것

분기 한정 과정

1. 분기 branching

- 여러개 작은 하부 가능영역feasible subregion들이 가능 영역 feasible region을 구성하는 방법

- 하부영역 각각에 대해 재귀 반복을 거치고, 만들어진 하부영역들이 자연스럽게 탐색 트리나 분기 한정 트리 branch-and-bound-tree 구조를 형성함 -> 노드가 각자 subregion이 됨

2. 한정 bounding

- 가능 하부공간 내에 최적해를 찾기 위한 상승 한정 하강한정 upper and low bound를 빠르게 차즌ㄴ 방법

분기 한정법의 핵심

- 탐색 트리에서 subregion A의 lower bound가 이미 검사된 다른 subregion B의 upper bound보다 크다면 A를 탐색에서 폐가함 -> 절단 pruning이라 함.

- 분기한정법은 탐색 노드의 모든 노드가 절단 되거나 해결되면 종료됨.

언덕 오르기 탐색 hill climbing search

- 깊이 우선 탐색 depth first search에 기초하며, 탐색 효율을 높이기 위해 휴리스틱이 사용

-> 각 단계에서 선택이 다른것보다 나은지 측정하고 계속하여 다른것을 선택

언덕 오르기 탐색 알고리즘

1. 루트 노드를 큐 q에 넣어 첫번째 요소로 한다. 이후 깊이 우선 탐색 수행

2. Q가 비어있거나 목표를 이룰때 까지 수행. Q에 있는 첫번째 요소가 목표 (remaining distance가 0인 상태) 인지를 결정

-> 목표가 아니라면 Q에서 첫 번째 요소를 제거하고, 그 자식 노드들을 잔여 거리 remaining distance에 따라 정렬하고, 정렬된 리스트를 Q 앞쪽에 배치. 목표가 아닌 상태에서 자식 노드가 없으면 부모노드로 간다.

3. 목표 노드에 도달하면 성공, 아니면 실패

언덕 오르기 방법 단점

- 유사한 상황의 발생 가능성이 있음

- 작은 언덕 foothill에서 시작시 거기서 너무많은 시간을 소비함

- 고원의 평지 plateaus와 같이 평탄한 곳에서 비교대상을 찾지 못해 어느 방향을 갈지 못하여 방황할수 있음

언덕 오르기 방법의 특징

- 완전 탐색 complete search

- 다양한 탐색방법중 어느것이 효율성을 증가시켜 search cost를 낮출수 있을지는 모름

- 휴리스틱이 언덕 오르기의 단점을 보완해주는 좋은 방법

-> 언덕 오르기가 상태 공간에서 가장 효율적인 경로를 반드시 찾는것은 아님

언덕 오르기 hill climbing의 개요

- 낯선 영역에서 흔한 문제 해결 방법은 현재 상태와 목표 상태 간의 차이를 줄이는것

-> 차이 감소법 difference reduction

언덕 오르기 hill climbing

- 차이 감소법 difference reduction과 동일

- 목표가 땅에서 가장 높은 지점이라 가정할때, 거기에 도달하는 방법은 항상 위로올라가는 단계를 밟는것

- 목표와 현재 상태간 차이를 줄이면서 문제 해결자는 목표를 향해 더 높은 단계를 밟아감

- 언덕 오르기는 계속 하다보면 가장 높은 지점 (전역 최대치, global maximum)인 목표보다 낮은 어떤 언덕의 꼭대기(지역 최대치, local maxima)에 도달할지 모르는 잠재적 위험을 가짐

=> 차이 감소가 반드시 문제 해결을 보장하는 것은 아님

평가 함수 evaluation function

- heuristic evaluation function 또는 static evaluation fuction 이라고도 함

- 체스 같은 게임에서 돌의 위치가 얼마나 좋은지 최소 최대 mini-max 알고리즘에서 사용

- 평가 함수는 빠른 결정이 되도록 설계하며 정확성은 주요 관심사가 아님.

- 탐색시 순서를 정하거나 재조정시 노드의 바람직한 정도를 평가하기 위한 척도

평가 함수 만들기 전략

- 여러 요인들의 가중치 함 weighted sum of various factors

평가 함수의 목표

- 확장 시킬 노드들에게 우선순위를 부여하여 어느것이 목표노드까지 최상경로에 있는지 결정

평가 함수

- f(n) = g(n) + h(n)

- f(n) : 노드 n에서 함수값. 출발 노드로부터 노드 n을 통해 목표 노드까지 가는 최소 비용 예측치

- g(n) : 출발노드로부터 노드 n까지 최적경로(최소비용경로) 비용 예측치

- h(n) : 노드 n에서 목표 노드까지 최적경로 비용 예측치

무정보 탐색의 한계

- 무정보 탐색(깊이/너비 우선 탐색)은 목적지까지 경로를 찾는데 상당히 소모적임 

-> 해는 찾지만 너무 많은 노드를 확장하여 실용적이지 못함

휴리스틱 탐색 heuristic search, 정보 탐색 infromed search

- 탐색 작업을 축소시키기 위해 대부분 경우에 잘맞는 경험에 의한 규칙(rules of thumb, 주먹구구식)을 이용

- 그래프로 표현된 문제에 특별한 정보(휴리스틱 정보)를 이용하여 탐색을 빠르게 진행하는 방식을 휴리스틱 탐색 모델이라함.

무정보 탐색 예시

- 너비 우선 탐색

- 깊이 우선 탐색

- 양방향 탐색

휴리스틱 탐색 예시

- 언덕 오르기 hill climbing

- 분기 한정법 branch and bound

- A* 알고리즘

- 최상 우선 탐색 best-first search

휴리스틱 탐색과 평가 함수

- 새로 생성된 후계 노드들은 휴리스틱 정보에 의한 기준에 따라 순서를 정하거나 재조정하여 탐색을 확장시켜나감

- 평가 함수 evaluation function : 순서를 재조정하기 위해 노드의 바람직한 정도를 평가하기 위한 척도

컴퓨터 과학에서의 탐색 알고리즘

- 문제를 입력해서 그 문제에 대한 해 solution을 얻는 알고리즘

- 대부분의 문제 해결알고리즘들이 탐색 알고리즘

탐색 공간 search space, 상태공간 state space

- 문제를 푸는 가능한 해를 모두 모아둔 집합

탐색 일고리즘

1. 무정보 탐색 uninformed search

- 문제의 독특한 성질을 고려하지 않은 알고리즘으로 탐색 공간을 가장 단순하고 직관적인 방법으로 탐색.

- 쉽게 구현 가능, 똑같은 구현 방식을 추상화하여 넓은 문제 범위들에 사용 가능

-> 대부분의 상태공간이 매우 커짐. 무정보 탐색은 탐색 공간이 작은 경우에만 합리적인 시간 소요

=> 탐색 시간을 빠르게 하기 위해 정보 탐색을 주로 사용

2. 리스트 탐색 list search

- 가장 기본적인 탐색 알고리즘

- 키에 의해 집합의 한 요소를 찾음

- linear search, binary search, self-balancing binary search tree

3. 트리 탐색 tree search

- 탐색 기술의 핵심으로 트리 노드를 검색

- 너비 우선 탐색 breadth first search : 레벨 별로 탐색하거나

- 깊이 우선 탐색 depth first search : 리프 노드에 도달하고나서 백트래킹

* 그래프 이론의 많은 문제들이 트리 알고리즘의 확장으로 해결 가능

=> 다익스트라 알고리즘, 크루스칼 알고리즘, 최근접 이웃 알고리즘, 프림 알고리즘

정보 탐색 informed search, 휴리스틱 탐색 heuristic search

- 그 문제의 독특한 휴리스틱이 가이드로 사용됨

- 좋은 휴리스틱은 정보 탐색을 드라마틱하게 하여 무정보 탐색보다 능가하는 성능을 냄

- 대부분 정보 탐색 알고리즘은 트리에서 사용

-> 최상 우선 탐색 best-first search, A* 알고리즘

그래프 이론 graph theory

- 유한개의 정점 node, vertex 와 변 edge의 결합에 관한 이론

- 정점 사이의 질적 관계를 표현하는 분야

그래프 이론 관련 문제

- 순회 판매원 문제

- 쾨니히스베르크의 다리 건너기 문제

- 해밀턴 사이클 문제

- 최단경로 찾기 문제

- 탐색 문제