휴리스틱

휴리스틱 heuristic

- 이미 정립된 공식이 아니라 정보가 부족한 상황에서 시행착오나 경험을 통해 주먹구구식의 규칙(rule of thumb)을 통해 지식을 얻는 과정.

- 잘 추측하는 기술(art of good guessing)라고 하기도 한다.

 

휴리스틱의 예시

- 명의가 진단시 그동안 진료경험으로 진단을 한다. 하지만 조기 진단할 암을 발견하지 못해 곤란할때도 있다.

 

알고리즘과의 차이

- 휴리스틱은 해결책 발견을 보장하지 않음

- 하지만 알고리즘 보다 효율적임 -> 많은 쓸모없는 대안들을 실행하지 않고 배제할수 있기 때문

=> 대표적으로 순회 외판원 문제 Traveling Salesman Problem, 체스 Chess 등에서 알리고리즘은 극도의 비효율성을 보임

 

 

컴퓨터 공학에서 근본적인 목표 2가지

- 증명가능하면서도 좋은 실행시간 runtime을 가지는 알고리즘 찾는 것

- 증명 가능하면서도 (최적인) 좋은 질의 해 solution quality를 가지는 알고리즘 찾는것

 

휴리스틱과 컴퓨터 공학에서 목표의 차이

- 휴리스틱은 위 목표의 하나 또는 둘다 포기하는 알고리즘

-> 휴리스틱은 좋은 해를 찾지만 임의로 나쁜 해를 찾지 않는다는 증명이 없음.

-> 휴리스틱은 보통 합리적인 실행 시간을 가지지만 항상 그렇다는 추론 과정이 없음.

 

 

 

최단 경로 문제 shortest path problem에서 휴리스틱

- 휴리스틱은 탐색 트리 노드에서 정의된 함수 h(n)으로서 그 노드에서 목표 노드까지 가장 비용이 적게 드는 경로를 찾아 그 비용을 추정하는데 사용.

- 휴리스틱은 타색하기에 가장 좋은 노드 선택을 위해 탐욕 최우선 탐색 greedy best-first search과 A*같은 정보 탐색 informed search 알고리즘에 사용됨

- greedy best first search는 휴리스틱 함수가 가장 값싼 비용을 가지는 노드를 선택할 것임

- A*는 g(n) + h(n)이 가장 값싼 비용을 가지는 노드를 확장할것

* g(n)은 최초의 상태에서 현재 노드까지 정확한 exact 비용

=> h(n)이 받아들일만한 경우(h(n)이 목표에 이르는 비용을 과장하여 추정하지 않으면) A*는 최적 optimal 이라 증명될수있음.

 

 

 

컴퓨터 성능에서 휴리스틱의 효과

- 탐색 문제에서 각 노드에 대해 b개의 선택이 가능하고 d 깊이에 목표 노드가 존재 시

- 순진한 탐색 알고리즘에서 해를 찾기위해 b^d개의 노드들을 탐색해야힘.

- 휴리스틱은 branching factor를 b에서 low constant b*까지 감소시켜 탐색 알고리즘의 효율성을 증진