집밖은 위험해

분기 한정법 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의 결합에 관한 이론

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

그래프 이론 관련 문제

- 순회 판매원 문제

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

- 해밀턴 사이클 문제

- 최단경로 찾기 문제

- 탐색 문제

회귀 분석 regressioni analysis

- 변수들 간의 함수적인 관련성을 규명하기 위해 수학적 모형(통계 모형)을 가정하고, 관측된 자료로 이 모형을 추정하는 통계 분석 방법으로 주로 예측에 사용

- 주어진 데이터를 가장 잘 나타낼수 있는 수식을 찾아내는 방법

데이터 예시

회귀식 예시

- 위 데이터를 가장 잘 나타낼수 있는 다항식을 구함 -> 회귀 분석

- 1차 : y = ax + b

- 2차 : y = ax^2 + b x + c

- 3차 : y = ax^3 + b x^2 + c x + d

NP-hard

- Non-deterministic Polynomial-time hard

- 결정 문제의 분류로 모든 경우의 수를 확인해보는것 이외에는 답을 찾을수 업슨ㄴ 문제

NP-complete

- NP 중에서 가장 어려운 문제

NP-complete 해결을 위한 접근 방법

- 근사 approximation : 적절한 범위 내 차선의 suboptimal 해결책을 빠르게 찾는 알고리즘. 모든 np-complete 문제가 좋은 근사 알고리즘을 가진것이 아니며, 발견하더라도 문제 자체를 해결하기엔 충분치 않음

- 확률 probabilistic : 문제의 인스턴스에 대한 확률분포에 대해 좋은 평균 런타임 동작을 낳는다고 입증된 알고리즘

- 휴리스틱 : 많은 경우 잘 동작하지만, 항상 빠르다는 증명은 없는 알고리즘

- 스페셜 케이스 : 문제의 인스턴스가 특별한 경우라면 빠르다는 것이 입증된 알고리즘

새로운 문제의 NP-complete 증명 방법

- 이미 알려진 NP-complete 문제를 새로운 문제로 환원 reduce

NP-complete 문제 종류

- Boolean statisfiability problem SAT

- Fifteen puzzle

- 배낭 문제

- minesweeper

- tetris

- 해밀턴 사이클 문제

- 순회 판매원 문제

- subgraph isomorphism problem

계산 복잡도 이론

- 주어진 문제를 풀기 위해 계산 과정에 필요한 자원을 다루는 계산 이론의 일부

자원의 종류

- 시간 : 문제를 풀기 위해 얼마나 많은 단계를 거치는가

- 공간 : 문제를 풀기 위해 얼마나 많은 메모리가 필요한가

- 이외 : 얼마나 많은 병렬 프로세서가 필요한가 등

하나의 문제

- 관련 질문들의 전체 집합. 질문은 유한 길이의 문자열

계산 이론의 인스턴스

- 인스턴스 : 어느 특별한 질문

인스턴스의 예시

- "15의 인수를 해라"

시간 복잡도 time complexity

- 가장 효율적인(bit로 측정) 알고리즘으로 한 문제의 인스턴스를 푸는데 걸리는 단계 수

시간 복잡도의 예시

- n 비트 길이의 인스턴스가 n^2 단계 내에 풀린다면 n^2의 시간복잡도를 가짐

 -> 빅오 표기법 : 최악의 경우 시간 복잡도 -> O(n^2)

- 잡초 깍기는 두배의 면적을 깍는데 두배의 시간이 걸린다 -> 선형 복잡도

- 사전에 어떤것을 찾을때 두배 크기의 사전을 한번더 열어봐야한다. -> 지수 복잡도

P 문제와 NP 문제

- P 문제 (polynomial, 다항식) : 알고리즘의 속도가 다항식으로 표현되는 문제

- NP 문제 (nondeterministic polynomial, 비결정 다항식) : 다항식으로 표현될수 있는지 알려지지 않은 문제

=> P 문제는 컴퓨터로 적당한 시간내 해결가능한 쉬운 문제, NP는 어려운 문제

NP hard와 NP 완전 문제(NP complete)

- NP-hard : 모든 경우의 수를 확인해보는 방법 이외에는 정확한 답을 구할수 있는 방법이 없는 문제

- NP-complete : NP-hard 이면서 다항식 시간으로 표현될수 있는지 알려지지않은 문제