탐색 (Search)
탐색 (Search) 이란
•
컴퓨터가 문제를 자율적으로 해결하기 위해 해(Solution 또는 Goal) 혹은 해에 이르기 위한 경로를 찾아가는 과정
•
탐색은 인공지능적 문제해결에서 중요한 수단
◦
초기연구 - 단순 규칙을 이용한 서양장기 문제에 적용 연구
◦
상업분야에서 항공표 예약시스템에 활용됨
•
단지 가능한 해를 찾는 것만의 문제가 아니라, 해를 찾는 과정의 효율성과 찾은 해의 적합성까지 포함한다.
◦
탐색량
◦
해에 이르는 경로의 비용 (길이 등)
•
인공지능 시스템에서 적용할 규칙을 선택하는 제어시스템의 행위는 일종의 탐색과정
문제 해결
•
문제 해결을 위한 지적 활동은 여러가지이다.
◦
그 중 일부는 탐색에 의한 해법이 유용하다.
직접적 기법
•
1 + 2 의 계산
◦
인간의 지적 활동에 의한 문제해결
◦
계산을 컴퓨터로 한다고 해서 인공지능적 문제 해결로 볼 수 없다.
◦
탐색 과정이 전혀 불필요하다 (컴퓨터의 우월한 연산능력 이용)
•
하노이 탑 문제 → 일련의 탐색 과정이 필요
◦
직접적 기법
▪
초기 상태가가 주어지면 항상 목표 상태까지 도달할 수 있는 동작들을 순차적 프로그래밍한다
•
탐색 과정이 필요하지만 인간의 두뇌로 탐색 과정을 프로그래밍하는 것
▪
초기 상태가 다르면 더 이상 유효하지 않다 → 프로그램 수정 필요
◦
인공지능적 해법
▪
문제 상태와 요구하는 목표 상태만으로 컴퓨터가 문제 해결
▪
탐색과정은 컴퓨터가 스스로 수행
탐색에 의한 문제 해결 기법의 특성
◦
문제의 해에 도달하기기 위한 탐색 과정을 스스로 수행함으로써 보다 포괄적이며 자동화된 해결방안을 얻는다.
▪
직접적 방법보다 효율면에서 우월하다고 볼 수는 없다.
◦
다양한 가변성을 가지는 큰 영역의 문제해결 과정 중에 지적 판단이 요구되는 경우 탐색기법이 유용하다.
▪
탐색에 의한 문제해결법과 직접적 방식의 활용영역이 다르다.
▪
직접적 방식은 문제와 해법이 명백하게 정의되는 문제에 적용한다.
◦
탐색에 의해 스스로 해를 찾도록 프로그램 되더라도 탐색 방식 결정은 프로그래머의 몫이다.
▪
완벽한 의미의 지능적 기계보다는 인간의 지능이 어느정도 개입하는 시스템 개발이 보다 현실적이다.
◦
문제해결의 최적의 방법보다 적당한 방법 (제시된 기준을 만족하는 해 중의 하나)을 찾는 것이 쉽고, 인간과 상통하는 바가 있다.
상태공간 (State Space)
◦
상태 : 문제의 풀이과정 중의 고유한 요소 (상황)
◦
상태의 집합 → 상태공간
◦
상태공간의 도입은 문제의 형식화에 유리 → 트리 구조
◦
뿌리노드부터 확장하여 목표노드까지 도달하는 과정
▪
노드확장 : 노드의 자식 노드를 찾는 것
•
OPEN 노드 : 노드의 확장을 마치기 전까지는 그 노드는 OPEN 노드
•
CLOSE 노드 : 이미 확장을 마친 노드
▪
트리의 크기가 문제해결의 효율성과 관련
◦
트리에서의 동일 노드의 재생성은 문제 야기
▪
탐색의 효율을 저하, 무한루프에 빠질 가능성이 있다
•
그래프 구조가 용이할 수 있음
기본적인 탐색 기법
탐색 기법 개요
•
경로 선택의 고려사항
◦
해의 경로는 짧아야 한다
◦
탐색의 소요 경비는 적어야 한다
◦
해가 있다면 탐색으로 반드시 찾아야 한다
•
탐색 기법으로 해결할 수 있는 문제 분류
◦
경로 발견 (Path Finding) 문제
▪
경로 찾기 (미로 찾기)
▪
8-Puzzle (문제 해결 경로)
◦
게임 문제
▪
Chess / 바둑
◦
제약조건 만족 (Constraint Satisfaction) 문제
▪
8-Queen
•
무작위 탐색 (Random Search)
◦
무작위로 경로 선택
◦
영국박물관 알고리즘 (BMA)
◦
일반적으로 최악의 방법이라고 생각되지만, 탐색 영역이 작은 (축소될 수 있는) 문제에는 유용할 수도 있다
•
트리에 의한 탐색
◦
일반적인 탐색기법
◦
깊이 우선 (Depth-Frist) 탐색
◦
너비우선 (Breadth-First) 탐색
8-puzzle
•
탐색 문제에 가장 많이 사용되는 예제
깊이우선탐색(Depth-First Search, DFS)
•
탐색 트리의 수직방향으로 점차 깊은 곳까지 목표노드를 찾아 탐색해 나가는 기법 (BackTracking이 존재)
•
장점
◦
저장공간의 수요가 비교적 작다
◦
목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수도 있다
•
단점
◦
해가 없는 경로에 깊이 빠질 우려 (Depth Bound 설정)
◦
해에 이르는 경로가 다수인 경우 얻어진 해가 최단 경로가 된다는 보장이 없다
•
평균 탐색 노드 수 (가지 : b개, 목표노드 깊이 : d)
너비우선탐색 (Breadth-First Search, BFS)
•
탐색 트리의 루트노드부터 목표노드를 만날 때까지 단계(레벨)별로 횡방향으로 탐색을 진행해 나가는 방식
•
장점
◦
해에 이르는 경로가 다수인 경우에도 최단 경로를 보장
◦
해가 존재하면 반드시 찾을 수 있다
◦
노드의 수가 적고 얇은 깊이에 해가 존재할 때 유리
•
단점
◦
노드의 수가 늘어나면 탐색시간이 비현실적이다
◦
기억공간에 대한 요구과 과중
•
평균 탐색 노드 수 (가지 : b개, 목표노드 깊이 : d)
탐색의 방향
•
전향추론 (Forward Reasoning)
◦
초기상태에서 목표상태로 탐색
•
후향추론 (Backward Reasoning)
◦
목표상태에서 초기상태로 탐색
•
주어진 문제의 성격에 따라 좌우된다
◦
시작 상태의 단순성과 복잡성 비교
◦
예) 런던을 거쳐 도버로 여행가는 길 찾기
휴리스틱 (Heuristic) 기법
•
논리적으로 또는 수학적으로 증명할 수는 없으나, 경험이나 직관에 의해 효율적으로 해를 얻을 수 있으리라는 기대를 갖게 하는 어떤 근거에 의한 방법
•
용도
◦
정의하기 힘든 문제
▪
ex) 직업선택, 예산지출
◦
맹목적인 기법 (Blind Search) 으로 풀기에는 비현실적인 문제
•
인간의 사고형태는 대부분 휴리스틱이다.
•
해법이 유일하지 않으며, 최적의 해를 보장할 수 없다.
•
목표로의 경로 결정에 허용성(Admissibility)을 부과하는 방법이 유용하다.
예) TSP (Traveling Salesman Problem)
•
n개의 도시 순회 방문 →
•
n=3 → 3
•
n=20 → 60, 822, 550, 204, 416, 000
◦
휴리스틱
▪
현재 위치에서 가장 가까운 도시부터 먼저 방문
언덕등반 기법 (Hill-Climbing)
•
다음 상태의 선택을 위해 평가함수(Evaluation Function 또는 Objective Function) 사용
◦
평가함수값을 증가(감소)시키는 방향으로 진행하는 탐색전략
◦
계곡하강법 (Valley Declining)
•
깊이우선 탐색기법에 평가함수를 활용한 형태
•
최단의 경로에 대한 보장이 없다.
•
국부최대가 존재할 수 있다. (Plateau, Ridge; Local Maxima)
•
과정 회복 불가능 (Irrevocable)
•
8-퍼즐 문제 : 상태공간
◦
각 칸에 들어갈 수 있는 수가 9개 : 9! = 362,880
◦
각 상태에서 가능한 다음 상태의 수
▪
모서리에 빈 칸(0)이 있는 경우 : 2개
▪
변두리에 빈 칸(0)이 있는 경우 : 3개
▪
가운데에 빈 칸(0)이 있는 경우 : 4개
◦
모든 상태들은 서로 이동 가능한가? = Connected Graph 인가?
•
Hill-Climbing 은 실제 문제의 적용 불가
◦
목표에 이르지 못하고 중단되는 경우가 대부분이다.
◦
휴리스틱 탐색의 기반을 제시한다.
•
개선
◦
국부최대를 만나도 탐색이 계속되도록 한다.
◦
이전 단계에서 선택이 안된 노드들도 추후 선택 가능하게 해야한다.
⇒ Best-First Search
최고우선탐색 (Best-First Search)
◦
모든 말단 노드를 대상으로 평가함수 값을 비교하는 방법이다.
▪
선택되지 않았던 노드들도 추후 선택이 가능하다.
▪
국부최대를 만나도 탐색이 계속된다.
◦
최적의 경로를 보장할 수 없다.
▪
기본적으로 깊이우선탐색(DFS) + 평가함수 이다.
▪
아직 선택되지 않은 노드를 또 확장해보면 더 나은 해를 발견 가능하다.
◦
모든 말단 노드들의 평가 함수 비교
▪
탐색이 계속 진행됨에 따라 기억용량이 가중될 수가 있다.
▪
너비우선탐색(BFS) 보다는 기억용량 부담이 매우 작다.
◦
탐색 도중 다음에 나아갈 노드를 선택할 때 가능하면 목표까지 추정 비용이 작은 노드를 선택 (탐색 비용을 추정한다)
▪
추정 비용을 정확히 알 수 없으므로 휴리스틱 사용
h(n) : 현재 노드부터 목표 노드까지의 평가된 비용
◦
최적해는 보증할 수 없지만 최고해가 되도록 탐색을 수행
◦
문제 해결을 유효시간 안에 수행
◦
현재 노드까지의 확정된 비용과 목표까지의 추정 비용을 함께 고려
최고우선 탐색 - 알고리즘
1.
Start 노드를 Open 리스트에 넣는다.
2.
만약 Open 리스트가 비어있으면, Stop하고 Failure 리턴한다.
3.
h(n)의 가장 낮은 값을 Open리스트에서 제거하고, Close리스트에 추가.
4.
노드 n을 확장하고, 노드 n의 successors을 생성.
5.
노드 n의 각 successor을 체크하고, 이 노드가 목표노드인지 아닌지 찾는다.
만약 이 successor 노드가 목표노드라면, 성공을 return하고 탐색 종료.
그게 아니라면 step 6 진행
6.
각 successor 노드들에 대해, 평가함수 f(n) 을 체크하고,
그리고 이 노드가 Open 또는 Close 리스트에 있는지 체크.
만약 노드가 두 리스트 모두에 없으면, 그 노드를 Open리스트에 추가
7.
step 2로 이동
최고우선탐색 - 예제)
각 미로 셀들을 우선순위 큐안에 저장해 놓고, 휴리스틱 값은 출구로부터 셀들의 “Manhattan distance” 가 될것이다
Manhatten Distance 은 fast-to-compute 하고, 가장 정확한 수치이다.
+
빔 탐색 (Beam Search)
◦
최고우선기법에서 기억노드의 수를 제한하는 방법
◦
기억공간이 축소되지만 너무 빠른 가지치기를 초래
A - 알고리즘
•
최적의 경로 : 초기노드에서 목표노드까지의 최단 경로
•
임의의 노드 N의 평가함수를 정의
g(N) : 초기노드에서 N 노드까지의 최단거리
h(N) : N노드에서 목표노드까지 최단거리
- h(N)은 해가 주어지지 않으면 알 수 없으므로
⇒ h(N) 대신에 목표에 대한 추정치 h*(N) 을 사용
h*(N) : 평가 함수의 휴리스틱 part → 휴리스틱 함수
A 탐색 (알고리즘) 은
•
을 평가함수로 사용하여 탐색 진행
•
최단 경로 개념을 가지므로 가장 작은 평가함수를 가지는 노드를 먼저 선택
•
휴리스틱 함수 도 목표쪽으로 갈수록 줄어들도록 만들어야 함
A* 알고리즘
•
A 알고리즘에서 모든 N에 대해 ≤ 가 성립되도록 하면 허용성을 가진다 → A* 알고리즘
◦
허용성(admissibility) : 최적의 경로를 보장하는 조건
◦
로 두면 ( = 0), 허용성 조건을 만족
▪
평가함수로 초기노드와의 거리만을 고려한다
•
낮은 깊이 노드를 우선 탐색 → BFS
▪
BFS가 최단 경로를 발견한다는 것으로 입증됨
•
A* 알고리즘은 A - 알고리즘이다.
•
A* 탐색은 에서 허용성을 만족하는 h* 함수를 사용함으로써 항상 최적의 경로를 찾음
◦
8-puzzle에서 상태 N에서의 평가함수 →
- 여기서 W(N)은 목표상태와 틀린 위치의 타일의 개수 (허용성 만족)
- : ‘틀린 타일의 목표와의 거리의 합'으로 하는 함수도 사용가능
A, A* 활용
게임을 위한 탐색
•
게임을 위한 탐색
◦
다수(2인)가 상호 배타적인 환경에서 승리하기 위한 경로를 탐색
◦
몇 수 앞을 내다본 후, 현재 상태의 선택을 결정한다
◦
대부분의 게임에서 완벽한 평가함수의 정의가 불가능
▪
휴리스틱한 기준에 의한 추정치 만을 제공
•
말패 (last-on-loses) 게임
◦
쌓인 칩을 번갈아 가면 1~3개씩 빼내는 경기 → 마지막 1개를 잡으면 패배
◦
평가함수
▪
N개의 쌓인 칩에서 n개를 뺄 때 (단, n = 1, 2, or 3)
최소최대(minimax) 탐색법
•
최소화자(minimizer) 와 최대화자(maximizer)로 구성되어 있다고 가정하고 탐색해 나가는 전략
•
평가함수의 활용(예시)
◦
f : 1.0 ~ -1.0 범위의 값을 가짐
▪
1.0에 가까울수록 최대화자 승리 가능성 높음
▪
-1.0에 가까울수록 최소화자 승리 가능성 높음
▪
0은 둘에게 비슷한 상황
◦
최대화자는 다음 상태들 중 1에 가장 가까운 상태를 선택
◦
최소화자는 그 반대로 선택
•
몇 수 앞을 내다보느냐가 탐색의 양에 영향
•
최소최대법을 사용하면서 탐색의 영역을 축소 가능
◦
어떤 노드가 그 함수값을 구하거나 확장하지 않아도 판단을 내리는데 지장이 없는 경우에 이 노드를 고려 대상에서 제외
→ pruning (알파 - 베타 가지치기)
최소최대 탐색 예
•
평가함수 값을 최대화 시키려는 최대화자 A의 탐색
◦
한 수 앞을 보는 경우
◦
두 수 앞을 내다보는 경우
▪
최소화자 B의 의도를 고려한 A의 선택
▪
DFS 사용, 평가 함수는 마지막에서 올려져야 함 → backup value
tic-tac-toe (삼목게임)
pruning (알파 - 베타 가지치기)
◦
최대화 노드에 올려진 값(알파값, ) 과 최소화의 노드에 올려진 값(베타값, ) 를 사용한 게임 탐색법
◦
기본적으로 DFS로 탐색 진행
▪
어떤 노드에 값이 올려질 때, 상위(조상노드 들)의 상대노드의 값과 비교하여 가지치기를 결정하는 방식
