📎최적해 vs 좋은해
- 최적 해 (Optimal Solution)
- 제약 조건을 만족하는 해 중 가장 우수한 해 (유일성을 갖는다)
- 종종 소모적인 탐색이 필요하다.
- 최적 해로 판단하기 위한 절차가 필요하다.
- 좋은 해 (Good Solution)
- 제약 조건을 만족하는 하나의 해
- 보다 우수한 해의 존재 여부와 관계가 없다.
탐색 속도는 해의 경로 & 방문한 노드 수에 비례한다.
📎탐색 방법의 분류
- 망라적 탐색 : 미래 정보를 사용하지 않는다.
- 너비 우선 탐색
- 깊이 우선 탐색
- 균일 비용 탐색
- 휴리스틱 탐색 : 미래 정보를 사용한다.
- 언덕오르기 탐색
- 최적우선 탐색
- A* 알고리즘
📎망라적 탐색
: 초기상태, 목표상태, 연산자가 주어진다.
- 너비우선 탐색
- 최적 해가 필요한 경우 유용하다.
- 낮은 레벨에 해가 존재할 것으로 추정될 때 유용하다.
- 최단경로를 보장한다.
- 각 노드의 모든 후계 노드를 탐색한다.
- 급격한 노드 증가의 가능성이 있다.
- 깊이 우선 탐색
- 해가 트리 왼쪽 깊은 곳에 존재할 것으로 추정될 때 유용하다.
- 좋은 해라도 무방할 때 유용하다.
- 노드가 많은 상태공간에서 유용하다.
- 백트레킹이 필요하다.
- 가장 깊은 노드까지 확장된다
- 깊이 제한이 필요하다.
- 균일 비용 탐색
- 최소 비용의 경로 탐색에 유용하다.
- 경로 비용이 최소인 노드로 확장한다.
- 비용 개념을 고려한다.
망라적 탐색의 문제점
- 너무 많은 노드가 생성된다.
- 연산 시간 및 메모리 문제가 발생한다.
- 대규모 문제에 비실용적이다.
>> 휴리스틱이 필요하다.🍊휴리스틱(Heuristic)
- 경험적 지식
- 완벽한 정보는 아니지만, 많은 경우에 유용하게 사용할 수 있는 경험적으로 얻은 지식이다. (= 감🍊)
📎휴리스틱 탐색
: 휴리스틱을 이용해 효율적으로 탐색하는 방법
📎휴리스틱 특징
- 성공 가능성 증가
- 부정확
- 해가 보장 안됨
- 일반화 불가능
📎휴리스틱을 이용한 탐색 방법
: 평가함수를 이용
- 노드의 가능성을 수치화
- 최상의 경로에 있을 확률
- 목표노드와의 차
📎휴리스틱 탐색의 종류
- 언덕오르기 탐색
- 깊이 우선 탐색 + 휴리스틱 탐색
깊이우선 : 진행 중인 경로를 우선적으로 탐색한다.
휴리스틱 : 현 상태까지의 비용은 무시하고, 현 상태에서 목표 상태까지의 예측 비용을 평가함수로 사용한다.
언덕 오르기 탐색에서 한 번 선택되지 않은 노드는 이후에 다시 나오면 선택에 고려하지 않는다.
휴리스틱이 우수할 수록 깊이우선 탐색보다 우수하다.
- 최적 우선 탐색
최적 우선 탐색에서는 한 번 선택되지 않은 노드가 다시 나오면 탐색의 대상으로 고려는 한다.
- A* 알고리즘
- 평가함수를 사용한다.
f(n) = g(n)+h(n)
(g(n)은 출발 노드에서 노드 n까지의 경로비용 , h(n)은 n에서 목표노드 까지의 예측 경로비용이다.
언덕오르기와 최적우선 탐색은 예측 경로 비용만 고려하지만,
A*알고리즘은 지나온 경로의 비용과 예측 경로 비용을 고려한다.
📎게임에서의 탐색
: 경험적 탐색이 필요하다.
- MINIMAX 프로시저
- 평가함수를 사용한다.
- 평가 값을 상위 노드로 전달한다.
- but 너무 많은 노드가 생성될 수 있다.
- 연산 시간 & 메모리 문제가 발생할 수 있다.
- 실제 문제에 적용이 곤란하다.
-> 노드의 절단이 필요하다
-> a-b 프로시저 (알파 베타 프로시저)
🥔 한 덩이