검색을 통한 문제해결

에이전트가 목표를 달성하기 위한 여러 동작의 순차열을 찾아내는 방법

문제 해결 에이전트

문제 형식화: 주어진 목표를 달성하기 위해 고려할 동작들과 상태들을 결정하는 공정

에이전트는 궁극적으로 값이 알려진 상태들로 이어지는 향후 동작들을 먼저 조사함으로써 다음 동작을 결정할 수 있다.

지금 환경은, 관찰 가능, 이산적, 기지 환경, 결정론적

-> 이 가정에서 임의의 문제에 대한 해답은 동작들의 고정된 순차열이다.

• 검색(Search) : 목표로 도달하는 동작열을 찾는 공정을 가리킨다
• 해답(Solution): 검색 알고리즘은 문제를 입력 받고 동작열 형태이다
  • 실행 단계: 해답이 추천하는 동작들을 수행한다.

잘 정의된 문제와 해답

형식적으로, 문제는 다음 다섯 요소로 정의할 수 있다.

• 에이전트가 시작하는 초기 상태 (Initial State)
• 에이전트가 할 수 있는 동작들의 서술
• 각 동작이 하는 일에 대한 서술, 전이 모형 (Transition Model)
• 주어진 상태가 목표 상태인지 판정하는 목표 판정 (Goal Test)
• 경로 비용 (Path Cost)함수는 각 경로에 수치 비용을 배정한다

예)

• 현재 아라드에 있다.(초기 상태) -> In(Arad)
• 이동할 수 있는 곳과 이동방법(동작, 동작들) -> Go(Sibiu), Go(Timisoara), Go(Zeridn)
• 이동하고 난 후 상태(전이 모형) -> Result(In(Arad), Go(Zerind)) = In(Zerind)
• 초기 상태, 동작들, 전이 모형의 조합은 문제의 상태 공간
• 상태 공간 안에서 하나의 동작열에 의해 연결된 일련의 상태들은 하나의 경로(Path)를 형성

문제 해결문제 해결 에이전트의 경로 비용 함수는 에이전트의 성과 측정 방식을 반영

예)

한 경로의 비용을 해당 주행거리로 생각한다.

단계 비용은 상태 s에서 상태 s’로 가는 동작 a를 실행하는 비용을 뜻하며 c(s, a, s’)으로 표기한다.

-> 문제를 정의하는 요소들을 자료구조로 취합해서 문제 해결 알고리즘의 입력으로 넣을 수 있다.

 

문제의 해답은 초기 상태에서 목표 상태로 가는 동작열이다

최적해(Optimal Solution)는 모든 해답 중 경로 비용이 가장 낮은 것이다.

문제 형식화

추상화: 표현에서 세부사항을 제거하는 절차이다.

예) 장난감 문제 (Toy Problem)과 실세계 문제

진공청소기 세계

• 상태: 상태들은 에이전트 위치와 먼지들의 위치 모두에 의해 결정된다.
• 초기 상태: 어떤 상태라도 초기 상태로 지정될 수 있다.
• 동작들: Left, Right, Suck
• 전이 모형: 동작마다 기대 효과가 있다. 단, 왼쪽에서 Left, 오른쪽에서 Right, 깨끗한 사각형에서 Suck 동작에는 효과가 없다.
• 목표 판정: 모든 사각형이 깨끗하면 목표가 달성이다.
• 경로 비용: 각 단계의 비용을 1로 가정하므로 경로 비용은 경로의 단계 수 이다.

해답의 검색

- 해답은 하나의 동작열, 검색 알고리즘은 가능한 여러 동작열들을 살펴보는 식으로 작동한다.

- 초기 상태에서 시작하는 가능한 동작열들은 하나의 검색 트리 (Search Tree)를 형성

- 뿌리는 초기 상태, 가지는 동작, 그리고 마디(노드)

- 첫 단계는 현재 목표 상태인지 점검

- 확장: 다양한 동작들을 고려해야 하는데, 이를 위해 현재 상태 확장 (expanding)

- 생성: 각각의 적법한 동작을 현재 상태에 적용해서 상태들의 새로운 집합을 생성 (generating)

 

여러 동작 중 하나를 선택해서 따라가되 나중에 그 동작이 해답으로 이어지지 않음을 알게 되었을 때를 대비해서 나머지 동작들도 보존해 두는것이 바로 검색의 핵심이다.

검색 알고리즘의 기반구조

• 검색 알고리즘에는 구축 중인 검색 트리를 추적하기 위한 자료구조가 필요하다. 트리의 각 노드n마다, 다음 네 성분을 담는 자료구조를 둔다.
• n.state: 이 노드에 해당하는 상태 공간 안에서의 상태
• n.parent: 검색 트리에서 이 노드를 생성한 노드
• n.action: 이 노드를 생성하기 위해 부모 노드에 적용한 동작
• n.path-cost: 초기 상태에서 이 노드로 가는 경로의 비용, 전통적으로 g(n)으로 표기

문제 해결 성능 측정

완결성: 해답이 존재할 때, 반드시 해답을 찾아내는 가?

최적성: 전략이 최적해를 찾아내는 가?

시간 복잡도: 시간이 얼마나 걸리는 가?

공간 복잡도: 메모리가 얼마나 필요한가?

정보 없는 검색 전략

맹목적 검색: 상태에 관한 문제 정의에 주어진 것 이상의 정보를 제공받지 못하는 상황

 

너비 우선 검색

균일 비용 검색

깊이 우선 검색

-> 깊이 제한 검색: 무한한 상태 공간에서 깊이 우선 검색이 실패하는 문제점은 미리 정해진 깊이 한계로 검색을 제
한함으로써 완화할 수 있다.

반복 심화 깊이 우선 검색

양방향 검색

정보 없는 검색 전략들의 비교

정보 있는 검색 전략들

문제 자체의 정의(문제에 관련된 지식도 활용)는 효율적으로 해답을 찾을 수 있다.

- 검색 전략이 정보 없는 전략보다

 

최선 우선 검색(best-first search)

확장할 노드를 평가 함수 (evaluation function) f(n)에 기초해서 선택한다는 것이 특징이다.

구현

- 균일 비용 검색의 것과 같되 우선순위 대기열을 정렬할 때 g 대신 f 를 사용한다는 점이 다르다.

- 대부분의 최선 우선 알고리즘에서 평가 함수 f에는 h(n)으로 표기하는 발견법적 함수(heuristic function)가 포함된다.

- h(n) = 노드 n에 해당하는 상태에서 목표 상태로의 가장 싼 경로의 추정 비용

탐욕적 최선 우선 검색

목표에서 가장 가까운 노드를 확장하면 해답에 빨리 도달할 가능성이 크다는 가정하에서 목표에 가장 가까운 노드를 선택한다.

- 발견법적 함수로 노드를 편가한다. f(n) = h(n)

예)

루마니아 여행 노선 찾기 문제에서 이 검색 방법이 어떻게 작동하는지?

직선거리 (straight-line distance, SLD) 를 발견법적 함수로 사용한다.

 

부카레스트까지의 직선거리를 뜻하는 h(SLD) 값

예)를 통해서 알 수 있는 탐욕적 최선 우선 검색

-> 림니쿠 빌차와 피테스티를 거쳐가는 경로보다 32키로 더 길다.

 

탐욕적으로 부를는 것은 이 알고리즘이 매 단계마다 가능한 한 목표에 가까워지려 한다.

만약, 이아시에서 파가라스로 가는 문제이면,

-> 발견법적 함수에 따르면 제일 먼저 네암트를 확장해야 한다. 그것이 파가라스에 가장 가깝기 때문이다. 그라나 그곳은 막다른 골목이다

해답: 바슬루이로 가고(발견법적 함수에 따르면 사실 이는 목표에서 멀어지는 것이다.), 그런 다음 우르지체니, 부카레스트, 파가라스로 가는 것

-> 하지만 알고리즘은 해답을 찾지 못한다.

A*검색

- 최선 우선 검색이다.

- 노드에 도달하는 비용을 뜻하는 g(n)과 노드에서 목표로 가는 비용을 뜻하는 h(n)을 결합해서 노드를 평가한다.

f(n) = g(n) + h(n)

예)

g(n)은 시작 노드에서 노드 n으로의 경로 비용을 돌려주므로, 그리고 h(n)은 n에서 목표로의 가장싼 경로의 추정 비용이므로, f(n) = n을 거쳐 가는 가장 싼 해답의 추정 비용

 

부카레스트까지의 직선거리를 뜻하는 h(SLD)값과 g(n)

메모리 제한 발견법적 검색

- 반복 심화, A* 알고리즘 (IDA*), 재귀적 최선 우선 검색이 있다.

- '메모리를 너무 적게 사용한다.'는 문제가 있다. 가용 메모리가 더 있더라도 활용하지 못한다.

-> 가용 메모리를 모두 사용할 수 있는 방법을 찾는 것이 좋다. 메모리 제한 A*, 단순화된 메모리 제한 A*

• 단순화된 메모리 제한 A*
  • A*처럼 그냥 최선의 잎 노드를 확장한다.
  • 그러다가 가용메모리를 다 쓰면 더는 검색 트리에 새 노드를 추가하지 못하게 되고 그때부터 f 값이 가장 큰 잎노드를 제거하면서 노드를 추가한다.
  • f 값이 가장 큰 잎노드를 제거하면서 노드를 추가한다.

- 문제를 계산 시간의 관점에서 처리 불가능한 문제로 만들 수 있다. 유일한 탈출구는 최적성 요구조권을 포기하는 것이다.

학습을 통한 검색 향상

개선 방법들은 메타 수준 상태 공간이라는 중요한 개념이 기초한다.

발견법적 함수

A*를 이용해서 최단 해답을 찾고자 한다면 목표로의 단계 수를 절대로 과대추정하지 않는 발견법적 함수가 필요하다.

h1 = 8, 잘못 놓인 타일의 개수

h2 = 3+1+2+2+3+2+2+3 = 18 ,모든 타일의 목표 위치와의 거리들의 총합