스튜어드 러셀의 인공지능을 읽어보자(8) : 해답 검색

startagainbornagain.tistory.com/84

스튜어드 러셀의 인공지능을 읽어보자(7) : 문제 형식화

저번 글이고요

 

해답의 검색

문제를 형식화했다면, 다음으로 할 일은 문제를 푸는 것입니다. 해답은 하나의 동작 열이므로, 검색 알고리즘은 가능한 여러 동작 열들을 살펴보는 식으로 작동한다. 초기 상태에서 시작하는 가능한 동작 열들은 하나의 검색 트리(search tree)를 형성한다. 이 트리(나무)에서 뿌리는 초기 상태이고 가지는 동작, 그리고 마디(node)가 존재합니다.

다양한 동작들을 고려해야 하는데, 이를 위해 현재 상태를 확장(expanding)합니다. 즉, 각각의 적법한 동작을 현재 상태에 적용해서 상태들의 새로운 집합을 생성(generating)하는 것입니다. 

 

출처 https://galid1.tistory.com/174

그리고 현재 E라는 노드에 있다고 해봅시다. 그 때 B노드는 부모 노드(parent node) B의 기준에서는 E는 자식 노드(child node)라고 합니다. 자세한 노드 설명은 출처를 통해 보시면 더욱 깊게 이해하실 수 있습니다.

이후 트리 구조에 대해서는 알고리즘을 해보자에서 알아보도록 하겠습니다.

 

정보 없는 검색 전략

이번 절에서는 정보 없는 검색(uniformed search; 맹목적 검색(blind search)이라고도 한다)에 속하는 여러 검색 전략을 살펴봅시다. 지금 알아보는 전략은 정보를 제공받지 못하는 상황을 가정했을 때 말하는 것입니다.  그러한 상황에서 할 수 있는 일은 후행자들을 생성하고 목표 상태와 비 목표 상태(non-goal state)

 를 구분하는 것 뿐입니다. 모든 검색 전략은 노드들을 확장하는 순서로 구분됩니다. 한 비 목표 상태가 다른 어떤 비 목표 상태보다 "더 유망한 지"의 여부를 알 수 있는 전략들은 정보 있는 검색(informed search) 또는 발견법적 검색(heuristiic search)에 속합니다.

 

크게 6가지가 존재합니다

• 너비 우선 검색 : 뿌리 노드를 먼저 확장하고, 뿌리 노드의 모든 후행자를 확장하고, 그 후행자들의 후행자들을 확장하는 식
• 균일 비용 검색 : 임의의 단계 비용 함수에 대해 최적인 알고리즘을 찾아낼 수 있다. 
• 깊이 우선 검색 : 항상 검색트리의 가장 깊은 수준, 즉 노드들에 후행자가 전혀 없는 수준으로 직접 나아간다.
• 깊이 제한 검색 : 무한 경로를 해결하기 위한 검색
• 반복 심화 깊이 우선 검색 : 최상의 깊이 한계를 찾아내는 일반적 전략
• 양방향 검색 : 초기 상태에서 시작하는 전방(순방향) 검색과 목표에서 시작하는 후방(역방향) 검색을 동시에 진행한다는 전략

정보 있는(발견법적) 검색 전략들

이번에는 반대로 정보가 있는 전략들에 대해서 알아보겠습니다.

여기 노드들은 평가 함수(evaluation funtion) 와 발견법적 함수(heuristic function)가 포함됩니다.

• 탐욕적 최선 우선 검색 : 목표에 가장 가까운 노드를 확장하면 해답에 빨리 도달할 가능성이 크다는 가정하에서 목표에 가장 가까운 노드를 선택합니다.
• 메모리 제한 발견법적 검색 : 메모리 요구량을 줄이는 가장 간단한 방법은 반복 심화를 발견법적 검색에 맞게 적용하는 것으로서 그렇게 나온 알고리즘이 이 알고리즘입니다.
• 학습을 통한 검색 향상 : 학습을 하여 더 최적에 전략을 찾아내는 방법입니다.

발견법적 함수

• 완화된 문제로부터 허용가능 발견법적 함수 생성 : 인화된 문제는 상태 공간에 간선들을 추가하므로, 원래 문제의 임의의 최적해는 정의에 의해 완화된 문제의 한 해답이기도 합니다. 그러나 완화된 문제에는 더 나은 해답들이 있을 수 있다. 추가된 간선들 때문에 지름길이 생길 수 있기 때문입니다. 따라서 완화된 문제의 최적 해의 비용을 구하는 함수는 원래 문제에 대한 허용 가능 발견법적 함수입니다.
• 부분 문제로부터 허용가능 발견법적 함수 생성(패턴 데이터베이스) : 허용 가능 발견법적 함수를 주어진 문제의 부분 문제(subproblem)의 해답 비용에서 도출할 수도 있습니다.
• 경험을 통한 발견법적 함수의 학습 : 경험으로부터 배우는 것으로 발견해 내는 것.

오늘은 이렇게 여기까지고요 고급 검색 기법에 대해 알아보도록 하겠습니다.