인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 탐색 (Search) 컴퓨터가 문제를 자율적으로 해결하기 위해 해 혹은 해 에 이르기 위한 경로를 찾아가는 과정 컴퓨터가 문제를 자율적으로 해결하기 위해 해 혹은 해 에 이르기 위한 경로를 찾아가는 과정  탐색은 인공 지능적 문제해결에서 주요한 수단  해를 찾는 과정의 효율성과 찾은 해의 적합성까지 포함  인공지능 시스템에서 적용할 규칙을 선택하는 제어시스템의 행 위는 일종의 탐색과정

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 문제 해결 문제 해결  인간의 지적 문제해결 ‘1+2’ : 인공지능적 문제 해결로 볼 수 없다. 하노이 탑 문제 : 인공지능적 탐색이 필요  직접적 기법 문제 해를 위한 순차적 수행을 위한 프로그래밍 초기상태가 다르면 프로그램 수정 필요 인공지능적 방법이 아님 ( 거의 모든 기존의 프로그램에 의한 문제 해 결방식 )  인공지능적 해법 문제 상태와 요구하는 목표 상태만으로 컴퓨터가 문제 해결

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 예제 : 하노이 타워 예제 : 하노이 타워 (a) 초기상태 d1 d2 p1 p2p3 (b) 목표상태 p1 p2 p3 동작 작용 m(d1,p1) d1 을 p1 으로 옮긴다. m(d1,p2) d1 을 p2 로 옮긴다. m(d1,p3) d1 을 p3 로 옮긴다. m(d2,p1) d2 를 p1 으로 옮긴다. m(d2,p2) d2 를 p2 로 옮긴다. m(d2,p3) d2 를 p3 로 옮긴다. 문제해결을 위한 동작의 정의

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 탐색에 의한 문제 해결 탐색에 의한 문제 해결  문제의 해에 도달하기 위한 탐색과정을 직접 수행함으로써 보 다 포괄적이며 자동화된 해결방안  문제해결 과정 중에 지적 판단이 요구되는 경우 탐색기법이 유 용  완벽한 의미의 지능적 기계보다는 인간의 지능이 어느 정도 개 입하는 시스템 개발이 보다 현실적이다  문제해결의 최적의 방법보다 적당한 방법을 찾는 것이 쉽고, 인 간과 상통하는 바가 있다.

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 상태공간 (state space) 상태공간 (state space)  상태 : 문제의 풀이과정중의 고유한 요소 ( 상황 )  상태의 집합을 상태공간  상태공간의 도입은 문제의 형식화에 유리  트리 구조 초기상태 := ((d1,d2)()()) 목표상태 := (()()(d1,d2)) 초기상태에 연산자 ( 규칙 ) 적용  상태 변이  목표상태  뿌리노드에서 목표노드까지 도달하는 과정 트리의 크기가 문제해결의 효율성과 관련  트리에서의 노드의 재생성은 문제 야기  그래프구조 탐색의 효율을 저하, 무한루프에 빠질 가능성

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 상태 트리 예 상태 트리 예 ((d1,d2)()())((d2)()(d1))(()(d1)(d2))((d2)(d1)())((d1,d2)()())(()(d2)(d1)) ((d2)(d1)())((d2)()(d1)) ((d1,d2)()()) m(d1,p2) m(d1,p3) m(d1,p1) m(d1,p3) m(d2,p3) m(d1,p1) m(d1,p2) m(d2,p2)

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 상태 그래프 예 상태 그래프 예 ((d1,d2)()()) ((d2)(d1)()) (()(d1)(d2)) ((d2)()(d1)) (()(d2)(d1)) m(d1,p2) m(d1,p3) m(d1,p1) m(d1,p3) m(d1,p1) m(d2,p1)m(d2,p3) m(d2,p2)m(d2,p1)

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 탐색기법 기본적 탐색기법 기본적 탐색기법  경로 선택의 고려사항 해의 경로는 짧아야 한다. 탐색의 소요 경비는 적어야 한다. 해가 있다면 탐색으로 반드시 찾아야 한다.  탐색 기법으로 해결할 수 있는 문제 분류 경로 발견 (path finding) 문제 –8-puzzle 게임 (game) 문제 –chess/ 바둑 제약조건 만족 (constraint satisfaction) 문제 –8-queen

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 탐색기법  무작위 탐색 (random search or blind search) 무작위로 경로 선택 영국박물관 알고리즘 (BMA) 일반적으로 최악의 방법이라고 생각되지만, 탐색 영역이 작은 ( 축소될 수 있는 ) 문제에는 유용할 수도 있다.  트리에 의한 탐색 일반적인 탐색기법 깊이우선 (depth-first) 탐색, 너비우선탐색 (breadth-first) 탐색 a bc defg a bc defg

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저  깊이우선 탐색 (depth-first search: DFS) 탐색 트리의 수직방향으로 점차 깊은 곳까지 목표노드를 찾아 탐색 해 나가는 기법 (backtracking 이 존재 ) 장점 – 저장공간의 수요가 비교적 작다 – 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수도 있다 단점 – 해가 없는 경로에 깊이 빠질 우려 (depth bound 설정 ) – 해에 이르는 경로가 다수인 경우 얻어진 해가 최단 경로가 된다는 보장 이 없다 평균 탐색 노드 수 ( 가지 : b 개, 목표노드 깊이 : d) – 목표가 최좌측 : d (1) – 목표가 최우측 : 1+b+b 2 + … +b d = (b d+1 -1)/(b-1) (2) – 평균 : {(1) + (2)} / 2

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저  너비우선 탐색 (breadth-first search : BFS) 탐색트리의 루트노드부터 목표노드를 만날 때까지 단계별로 횡방 향으로 탐색을 진행해 나가는 방식 장점 – 해에 이르는 경로가 다수인 경우에도 최단경로를 보장 – 해가 존재하면 반드시 찾을 수 있다 – 노드의 수가 적고 얕은 깊이에 해가 존재할 때 유리 단점 – 노드의 수가 늘어나면 탐색시간이 비현실적이다 – 기억공간에 대한 요구가 과중 평균 탐색 노드 수 ( 가지 : b 개, 목표노드 깊이 : d) –d 깊이 목표를 위한 평균 노드 수 = (d-1 깊이까지 총 노드수 ) + (d 깊이에서의 노드 평균수 ) –d-1 까지의 총수 : 1+b+b 2 + … +b d-1 = (b d -1)/(b-1) --- (1) –d 에서의 평균 수 : (1+ b d )/2 --- (2)

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 탐색의 방향 탐색의 방향  전향추론 (forward reasoning) 초기상태에서 목표상태로 탐색  후향추론 (backward reasoning) 목표상태에서 초기상태로 탐색  주어진 문제의 성격에 따라 좌우된다 시작 상태의 단순성과 복잡성 비교 예 : 런던을 거쳐 도버로 여행가는 길 찾기 런던 캔터베리 마케트 도버 코벤트리 노스앰톤 옥스포드 브리스톨 솔즈베리 사우스앰톤 포츠머스 헤이스팅즈 노리지 캠브리지 콜체스트

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 휴리스틱 기법 휴리스틱 (heuristic) 기법 휴리스틱 (heuristic) 기법  논리적으로 혹은 수학적으로 증명할 수 없으나 경험이나 직관 에 의해 효율적으로 해를 얻을 수 있으리라는 기대를 갖게 하는 어떤 근거에 의한 방법  용도 정의하기 힘든 문제 예 ) 직업선택, 예산지출 맹목적인 기법 (blind search) 으로 풀기에는 비현실적인 문제  인간의 사고형태는 대부분 휴리스틱이다  해법이 유일하지 않으며, 최적의 해를 보장할 수 없다  해의 결정에 허용치를 부과하는 방법이 유용하다 예 ) TSP(Traveling Salesman Problem) –n 개의 도시 순회 방문  (n-1)!/2 –n=3  3, n=20  60,822,550,204,416,000 휴리스틱 – 현재 위치에서 가장 가까운 도시부터 먼저 방문

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 언덕등반기법 (hill-climbing) 언덕등반기법 (hill-climbing)  평가함수 (evaluation function or objective function) 사용 평가함수값을 증가 ( 감소 ) 시키는 방향으로 나가는 탐색전략 계곡하강법 (valley declining)  깊이우선 탐색기법에 평가함수를 활용한 형태  최단의 경로에 대한 보장이 없다  국부최대가 존재할 수 있다 (plateau, ridge, local maxima)  과정 회복 불가능 (irrevocable) 예 ) 8- 퍼즐 문제 초기상태목표상태 a sequence of tile moving actions

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 8- 퍼즐문제의 탐색 8- 퍼즐문제의 탐색  평가함수값 : 목표상태와 같은 위치에 있는 타일 수 초기상태목표상태 비교

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저  언덕등반기법의 실패 최고우선탐색 (best-first) 최고우선탐색 (best-first)  모든 말단 노드를 대상으로 평가함수 값을 비교하는 방법 선택 안 된 노드도 추후 선택 가능  국부최대를 만나도 탐색이 계속된다  너비우선 방식에 비해 탐색비용이 절감된다  최적의 경로를 보장할 수 없다 아직 선택 안 된 노드를 또 확장해 보면 더 나은 해를 발견 가능

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저  최고우선 탐색법 예 s 2 a 4 b 1 c 5 s 2 a 4 b 1 c 5 d 2 e 3 s 2 a 4 b 1 c 5 d 2 e 3 f 5 g 6 s 2 a 4 b 1 c 5 d 2 e 3 f 5 g 6 h 5 i 3 j 8

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 빔 탐색 (beam search) 빔 탐색 (beam search)  최고우선기법에서 기억노드의 수를 제한하는 방법  기억공간이 축소되지만 너무 빠른 가지치기를 초래 A- 알고리즘 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) : 평가함수

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 A* 알고리즘 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) 은 목표상태와 틀린 위치의 타일의 갯수

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 게임트리 탐색 게임을 위한 탐색 게임을 위한 탐색  다수 (2 인 ) 가 상호 배타적인 환경에서 승리하기 위한 경로를 탐 색  앞을 내다봄으로써 현재 상태의 선택을 결정한다  대부분의 게임에서 완벽한 평가함수의 정의가 불가능  휴리 스틱한 기준에 의한 추정치 만을 제공 말패 (last-one-loses) 게임 말패 (last-one-loses) 게임  평가함수 그림 2.13 참조

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 게임트리 탐색 최소최대 (minimax) 탐색법 최소최대 (minimax) 탐색법  최소화자와 최대화자로 구성되어 있다고 가정하고 탐색해 나가 는 전략  몇 수 앞을 내다보느냐가 탐색의 양에 영향  최소최대법을 사용하면 탐색의 영역을 축소 가능 어떤 노드가 그 함수값을 구하거나 확장하지 않아도 판단을 내리 는데 지장이 없는 경우에 이 노드를 고려 대상에서 제외   -  pruning( 알파 - 베타 가지치기 )

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 최소최대 탐색 예 최소최대 탐색 예 평가함수 값을 최대화 시키려는 최대화자 A 의 탐색 최소화자 B 의 의도를 고려한 A 의 선택 A [c 1 ] f=0.8 [c 2 ] f=0.3 [c 3 ] f=-0.2 A [c 1 ] f=0.8 [c 2 ] f=0.3 [c 3 ] f=-0.2 [c 11 ] f=0.9 [c 12 ] f=0.1 [c 13 ] f=-0.6 [c 21 ] f=0.1 [c 22 ] f=-0.7 [c 31 ] f=-0.1 [c 32 ] f=-0.3 최소화자 (B) 단계

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 알파베타 가지치기 알파베타 가지치기  최대화 노드에서 가능한 최소의 값 ( 알파  ) 과 최소화의 노드에 서 가능한 최대의 값 ( 베타  ) 를 사용한 게임 탐색법  기본적으로 DFS 로 탐색 진행 [c 0 ]  =0.2 [c 2 ] f= -0.1 [c 1 ] f=0.2 [c 21 ] f= -0.1 [c 22 ][c 23 ] [c 11 ] f=0.2 [c 12 ] f=0.7 C21 의 평가값 -0.1 이 C2 에 올려지면 나머지 노드들 (C22, C23) 을 더 이상 탐색할 필요가 없음

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 다음 법칙을 이용하여 아래의 알파 - 베타 탐색 트리를 완성하라 알파베타 탐색 문제 가지치기가 일어나는 법칙 : 1. 깊이우선 방식으로 탐색 진행 2. 어떤 최소화노드의 베타값이 자신보다 상위 ( 선조노드 ) 에 있는 어떤 최대화 노드의 알 파값보다 작거나 같을 때, 이 최소화 노드는 가지치기 된다. 3. 어떤 최대화노드의 알파값이 자신보다 상위 ( 선조노드 ) 에 있는 어떤 최소화 노드의 베 타값보다 크거나 같을 때, 이 최대화 노드는 가지치기 된다. 4. 최상위의 최대화노드의 알파값은 최종적으로 올려진 값 (backed-up value) 로 주어진다.

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 n 개의 변수로 구성된 CSP 정의 n 개의 변수로 구성된 CSP 정의  유한하고 이산적인 영역들인 D 1, D 2, …,D n 으로부터 값을 취하고 그 값들 간에는 제약조건 p k (x k1,x k2,…x kl ) 이 존재하는 문제  일종의 NP-complete 문제  8-Queen 문제 여왕 x i, x j 의 위치사이의 제약조건 제약조건만족 문제 (Constraint Satisfaction P) x 2 = 7

인공지능 : 개념 및 응용 Artificial Intelligence: Concepts and Applications 2. 탐색 도용태 김일곤 김종완 박창현 공저 [c 21 ] f=-0.1 [c 22 ][c 23 ] [c 11 ] f=0.2 [c 12 ] f=-0.7 탐색기법의 활용 탐색기법의 활용  공장자동화, 로보트의 경로계획 NASA 의 GPSS(ground processing scheduling system)  비행기 좌석예약 시스템  게임 chess - Deep Thought 바둑 - 아직 수준이 요원 (?)  다자가 공동의 공간에서 자신의 이익을 달성하려는 경제적 문제  실제 게임의 경우 탐색의 양이 폭증  지식 활용에 대한 연구가 많이 요구됨