 탐색에 의한 문제 해결

탐색 (Search)

 컴퓨터가 문제를 자율적으로 해결하기 위해 해 혹은 해에 이르기 위한 경로를 찾아가는 과정

 탐색은 인공 지능적 문제해결에서 주요한 수단

 해를 찾는 과정의 효율성과 찾은 해의 적합성까지 포함

 인공지능 시스템에서 적용할 규칙을 선택하는 제어시스템의 행 위는 일종의 탐색과정

 문제 해결

인간의 지적 문제해결

 ‘1+2’ : 인공지능적 문제 해결로 볼 수 없다.

 하노이 탑 문제 : 인공지능적 탐색이 필요

직접적 기법

 문제 해를 위한 순차적 수행을 위한 프로그래밍

 초기상태가 다르면 프로그램 수정 필요

 인공지능적 방법이 아님(거의 모든 기존의 프로그램에 의한 문제 해 결방식)

인공지능적 해법

 문제 상태와 요구하는 목표 상태만으로 컴퓨터가 문제 해결

 탐색에 의한 문제 해결

 문제의 해에 도달하기 위한 탐색과정을 직접 수행함으로써 보다 포괄적이며 자동화된 해결방안

 문제해결 과정 중에 지적 판단이 요구되는 경우 탐색기법이 유용

 완벽한 의미의 지능적 기계보다는 인간의 지능이 어느 정도 개입 하는 시스템 개발이 보다 현실적이다

 문제해결의 최적의 방법보다 적당한 방법을 찾는 것이 쉽고, 인 간과 상통하는 바가 있다.

 상태공간 (state space)

상태: 문제의 풀이과정중의 고유한 요소(상황)

상태의 집합을 상태공간

상태공간의 도입은 문제의 형식화에 유리트리 구조

 초기상태 := ((d1,d2)()()) 목표상태 := (()()(d1,d2))

 초기상태에 연산자(규칙) 적용  상태 변이  목표상태

뿌리노드에서 목표노드까지 도달하는 과정

 트리의 크기가 문제해결의 효율성과 관련

트리에서의 노드의 재생성은 문제 야기  그래프구조

 탐색의 효율을 저하, 무한루프에 빠질 가능성

탐색기법

 기본적 탐색기법

경로 선택의 고려사항

 해의 경로는 짧아야 한다.

 탐색의 소요 경비는 적어야 한다.

 해가 있다면 탐색으로 반드시 찾아야 한다.

탐색 기법으로 해결할 수 있는 문제 분류

 경로 발견(path finding) 문제

– 8-puzzle

 게임(game) 문제

– chess/바둑

 제약조건 만족(constraint satisfaction) 문제

– 8-queen

깊이우선 탐색(depth-first search: DFS)

 탐색 트리의 수직방향으로 점차 깊은 곳까지 목표노드를 찾아 탐색 해 나가는 기법(backtracking이 존재)

 장점

– 저장공간의 수요가 비교적 작다

– 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수도 있다

 단점

– 해가 없는 경로에 깊이 빠질 우려(depth bound설정)

– 해에 이르는 경로가 다수인 경우 얻어진 해가 최단 경로가 된다는 보장 이 없다

 평균 탐색 노드 수(가지: b개, 목표노드 깊이: d)

– 목표가 최좌측: d+1 - - - (1)

– 목표가 최우측: 1+b+b²+ … +b^d = (b^d+1-1)/(b-1) - - - (2) – 평균: {(1) + (2)} / 2

 너비우선 탐색(breadth-first search : BFS)

 탐색트리의 루트노드부터 목표노드를 만날 때까지 단계별로 횡방향 으로 탐색을 진행해 나가는 방식

 장점

– 해에 이르는 경로가 다수인 경우에도 최단경로를 보장 – 해가 존재하면 반드시 찾을 수 있다

– 노드의 수가 적고 얕은 깊이에 해가 존재할 때 유리

 단점

– 노드의 수가 늘어나면 탐색시간이 비현실적이다 – 기억공간에 대한 요구가 과중

 평균 탐색 노드 수(가지: b개, 목표노드 깊이: d)

– d 깊이 목표를 위한 평균 노드 수 =

(d-1깊이까지 총 노드수) + (d 깊이에서의 노드 평균수) – d-1까지의 총수: 1+b+b²+ … +b^d-1 = (b^d-1)/(b-1) --- (1) – d에서의 평균 수: (1+ b^d)/2 --- (2)

휴리스틱 기법

 휴리스틱 (heuristic)기법

 논리적으로 혹은 수학적으로 증명할 수 없으나 경험이나 직관에 의해 효율적으로 해를 얻을 수 있으리라는 기대를 갖게 하는 어 떤 근거에 의한 방법

 용도

 정의하기 힘든 문제 예) 직업선택, 예산지출

 맹목적인 기법(blind search)으로 풀기에는 비현실적인 문제

 인간의 사고형태는 대부분 휴리스틱이다

 해법이 유일하지 않으며, 최적의 해를 보장할 수 없다

 해의 결정에 허용치를 부과하는 방법이 유용하다 예) TSP(Traveling Salesman Problem)

n개의 도시 순회 방문  (n-1)!/2

n=3  3, n=20  60,822,550,204,416,000

 표 2.2 외판원 방문 예

 현재 위치에서 가장 가까운 도시부터 먼저 방문

 빔 탐색 (beam search)

 최고우선기법에서 기억노드의 수를 제한하는 방법

 기억공간이 축소되지만 너무 빠른 가지치기를 초래

 A-알고리즘

 최적의 경로 : 초기노드에서 목표노드까지의 최단 경로 임의의 노드 N의 평가함수를 정의

f(N) = g(N) + h(N)



g(N): 초기노드에서 N노드 까지의 최단거리



h(N): N노드에서 목표노드까지 최단 거리



h(N)은 해가 주어지지 않으면 알 수 없으므로, h(N)대신에 추정치 h*(N)을 사용



f(N) = g(N) + h* (N) : 평가함수

 A* 알고리즘

 A 알고리즘에서 모든 N에 대해 h*(N)  h(N)가 성립되도록 하면 허용성을 가짐  A* 알고리즘

 허용성(admissibility): 최적의 경로를 보장하는 조건



f(N) = g(N)로 두면(h*(N)=0), 허용성 조건을 만족

 평가함수로 초기노드와의 거리만을 고려  낮은 깊이 노드를 우선 탐색  BFS

 BFS가 최단 경로를 발견한다는 것을 다시 입증

 BFS를 해나가는 데 있어 각 노드에서 목표에 이르는 경로가 얼 마나 짧은 것인가의 추정치를 이용하는 방법

(cf. 8-puzzle에서 상태 n에서의 평가 함수)

f(N) = g(N) + W(N)

여기서 W(N)은 목표상태와 틀린 위치의 타일의 갯수

게임트리 탐색

 게임을 위한 탐색

 다수(2인)가 상호 배타적인 환경에서 승리하기 위한 경로를 탐색

 앞을 내다봄으로써 현재 상태의 선택을 결정한다

 대부분의 게임에서 완벽한 평가함수의 정의가 불가능  휴리스 틱한 기준에 의한 추정치 만을 제공

 말패 (last-one-loses) 게임

 평가함수

그림 2.13 참조

게임트리 탐색

 최소최대 (minimax) 탐색법

 최소화자와 최대화자로 구성되어 있다고 가정하고 탐색해 나가 는 전략

 몇 수 앞을 내다보느냐가 탐색의 양에 영향

 최소최대법을 사용하면 탐색의 영역을 축소 가능

 어떤 노드가 그 함수값을 구하거나 확장하지 않아도 판단을 내리는 데 지장이 없는 경우에 이 노드를 고려 대상에서 제외

 - pruning(알파-베타 가지치기)

[c

]

f=-0.1

[c

] [c

] [c

]

f=0.2

[c

]

f=-0.7

 탐색기법의 활용

공장자동화, 로보트의 경로계획

 NASA의 GPSS(ground processing scheduling system)

비행기 좌석예약 시스템

게임

 chess - Deep Thought

 바둑 - 아직 수준이 요원 (?)

다자가 공동의 공간에서 자신의 이익을 달성하려는 경제적 문제

실제 게임의 경우 탐색의 양이 폭증  지식 활용에 대한 연구가 많이 요구됨

참고문헌 및 강의자료 제공

인공지능: 개념 및 응용 Artificial Intelligence: Concepts and Applications (2001년 2월 개정판)